Motivation
An edge-density inequality can force a large clique without deciding clique existence for every graph. To identify the exact threshold, we need a graph attaining the bound and a proof that no clique-free graph has more edges. The finite rounding in the construction matters when the order is not divisible by the number of parts.
Complete multipartite graphs supply the candidates. Their cliques can choose at most one vertex from each part, and balancing the part sizes maximizes the cross-edges. A clique-removal induction proves that this candidate is optimal among all graphs, while equality reveals the entire multipartite structure.
The result strengthens a non-rounded density estimate into an exact count and classification.
Definitions
Definition 10.6.1
(Complete multipartite graphs and the balanced edge count)
Let and be integers. A complete -partite graph has a partition of its vertices into parts, with all cross-part edges and no within-part edges. Empty parts are allowed, which includes the case . It is balanced when any two part sizes differ by at most one.
Write with . The balanced sizes are parts of size and parts of size . Their edge count is
The expression is an integer because it counts unordered pairs in different parts. Graphs throughout are finite, simple and undirected.
A clique is a set of mutually adjacent vertices. A graph is -free when it has no clique of that size. Its independence number is the largest size of a set containing no edges. An extremal graph here means a clique-free graph with the largest possible number of edges at its specified order.
A graph isomorphism may relabel vertices. The equality classification determines the graph up to such relabeling; it does not force one particular labeled partition of an existing vertex set.
Theorem/Proposition
Theorem 10.6.2
(Balancing uniquely maximizes the multipartite edge count)
Among complete -partite graphs on vertices, the maximum edge count is , attained exactly by balanced part sizes. For ,
For and , one also has .
Theorem 10.6.3
(Exact clique-free threshold and all equality cases)
Every -free graph on vertices has at most edges. Equality holds exactly for a balanced complete -partite graph, up to vertex relabeling and empty parts.
Consequently more than edges forces a clique of size . The converse decision statement is false: a graph below the threshold can still contain that clique.
Theorem 10.6.4
(The complementary independence problem has an exact minimum)
A graph on vertices with independence number at most has at least edges. Equality holds exactly for a disjoint union of balanced cliques, allowing empty cliques.
Thus the same extremal count measures a largest edge set avoiding a large clique and a smallest edge set forbidding a large independent set, with graph complementation exchanging the problems.
Proof sketch or proof idea
Proof
(Balancing and the multipartite recurrence)
For part sizes summing to , the cross-edge count is . Suppose two sizes satisfy . Moving one vertex from the larger to the smaller changes their square sum from to , decreasing it by and increasing the edge count.
Repeat this finite balancing operation. Every unbalanced size pattern can be improved; every balanced one has the displayed sizes and hence the same count. This proves the maximum and all multipartite equality patterns. Expanding their square sum yields the two forms of the formula.
When , every balanced part is nonempty. Remove one vertex from each part. The remainder is balanced on vertices. The removed vertices form an -clique, and every surviving vertex has an edge to exactly of them. Counting the removed edges proves the recurrence in the theorem.
For strict increase in the part parameter, begin with a balanced -partite graph on vertices. At least one part has size at least two. Split that part into two nonempty parts, gaining their positive product of edges and using at most parts. Balancing can only increase the result further. Hence its old optimum count is strictly below .
Prove the extremal upper bound by two linked inductions
Proof
(Clique-removal induction)
The case is immediate: a graph with no two-clique has no edges, exactly the one-part construction. For larger , assume the theorem's upper bound has been proved for parameter at every order, and prove it for the current by induction on .
If , there are not enough vertices for the forbidden clique and the largest graph is complete, with edges. Now let . If the graph contains no -clique, the parameter- bound gives at most edges. This settles that branch with a strict inequality.
Otherwise choose a clique of size . Any vertex outside has at most neighbors in it, since adjacency to all of them would create an -clique. The graph on the remaining vertices is still -free. The order induction therefore bounds the total edges by
Every invocation has either a smaller part parameter or the same parameter at smaller order. Thus the two inductions are well-founded and prove the upper bound at every order. The balanced construction is clique-free because a clique uses at most one vertex per independent part, so it attains the bound.
Equality forces the graph itself to be balanced multipartite
Proof
(Equality reconstructs the parts)
For , equality is the edgeless graph. If , equality requires every possible edge, which is a complete graph represented by singleton parts and the remaining empty parts. Consider the remaining case .
The no--clique branch was strictly below the bound, so an equality graph has such a clique . Equality in the edge count forces every outside vertex to have exactly neighbors in . It therefore misses exactly one of those vertices.
Assign each outside vertex to the part of its unique missed vertex , putting in that part as well. Two outside vertices assigned to the same part cannot be adjacent. If they were, those two vertices together with the other vertices of would form an -clique. Neither is adjacent to its assigned by definition, so every resulting part is independent.
The original graph is consequently a subgraph of the complete -partite graph on these parts. That complete graph has at most edges by the balancing theorem, while the original already has exactly that many. Hence every permitted cross-edge must be present and the parts must be balanced. This proves the complete equality classification, without assuming that the smaller induced graph's classification automatically controls how the removed clique attaches.
Proof X-ray
How the clique-removal induction is tight enough to classify
Two inductions run together: on the part parameter for the branch with no -clique, and on the order for the branch with one. The first branch needs the strict inequality from the balancing theorem, and that strictness is what later excludes it from every equality case. In the second branch the hypothesis that the graph is -free is used once per outside vertex: it caps the edges into at . The identity then makes the three counts add up exactly to .
Equality needs more than the numerical induction. Tightness at the chosen clique gives each outside vertex exactly one missed vertex of , and that pattern names the parts. The forbidden clique is used a second time, inside each proposed part, to make it independent. Only then does the balancing theorem convert containment in a complete -partite graph into equality with a balanced one; no classification of the smaller induced graph is needed to control how attaches.
Transfer the exact statement to independent sets
Proof
(Complementation)
A set is independent in a graph precisely when it is a clique in the simple complement. Therefore independence number at most means that the complement is -free. Apply the upper bound to its edges and rearrange to obtain the lower bound on .
Complementing the equality graph removes all cross-part edges and fills every part internally, producing disjoint balanced cliques. Conversely that union has independence number at most the number of its nonempty cliques, hence at most , and it attains the stated count. This proves both directions of the complementary equality claim, including where the extremal graph is edgeless.
What the threshold can and cannot decide
Computing from integer division is straightforward, and a graph with more edges has a certified large clique. The theorem does not say that every graph with fewer edges is clique-free. Detecting the actual clique or interpreting a failed density test requires another argument.
For fixed , enumerating all -vertex sets and checking their pairs is a finite polynomial-in- search, with an exponent depending on . That observation is not a polynomial bound uniform in a binary-encoded variable threshold. The extremal theorem is a precise structural statement, and its existence proof does not remove the input-model distinction in general clique algorithms.
Worked examples
Worked example 10.6.5
(Eight vertices and a forbidden four-clique give twenty-one edges)
Take . The balanced sizes are three, three and two. Their cross-edge count is . Every four-clique-free graph has at most twenty-one edges, and equality requires precisely this complete tripartite shape.
Thus twenty-two edges force a four-clique. In the complementary independence problem, at least edges are needed to force independence number at most three; the balanced clique union has sizes three, three and two and edge count .
Worked example 10.6.6
(The odd-order triangle-free bound keeps its rounding)
For seven vertices and , balanced parts have sizes four and three, giving twelve edges. The unrounded density term would be , while the correction is one quarter, leaving the integer optimum twelve.
Every triangle-free graph with twelve edges is the complete bipartite graph up to relabeling. Thirteen edges force a triangle. The exact classification gives more information than merely flooring a rough estimate after its equality conditions have been forgotten.
Worked example 10.6.7
(More available parts than vertices causes no exceptional formula)
For three vertices and , take three singleton parts and two empty parts. The balanced graph is , with three edges, and cannot contain the forbidden six-clique.
The formula has quotient zero and remainder three and gives three as well. Its complement is three isolated vertices, representable as five balanced clique parts of sizes one, one, one, zero and zero. Its independence number is three, which is indeed at most five. Allowing empty parts makes both equality statements consistent at this boundary.
Concept lensCombinatorial
Maximizing allowed edges also reveals the forbidden-clique boundary
The balanced multipartite construction spends edges between parts while preventing a clique from taking two vertices inside one part. The induction proves no different arrangement can spend more. At equality, every outside vertex's single missing neighbor in a chosen -clique reconstructs those parts, making the extremal shape a conclusion rather than a guessed drawing.
Common mistakes
Counterexample mode
Being below the threshold does not mean the graph is clique-free
A triangle together with three isolated vertices has only three edges, far below , but it still contains a triangle. The theorem says triangle-free graphs cannot exceed nine edges, or equivalently that more than nine forces a triangle. It does not turn every smaller edge count into a certificate that no triangle exists.
Common mistake
(Exactly the threshold does not force a clique)
Keep the strict inequality in the forcing statement and the non-strict inequality in the extremal bound. has exactly edges and no triangle, so “twelve edges on seven vertices force a triangle” is false; only thirteen or more do.
Common mistake
(An edge count alone does not identify the graph)
Equality classification applies only after clique-freeness is known. A triangle with one pendant edge has four vertices and edges, yet it is not , because it contains a triangle.
Common mistake
(Multipartite graphs and clique unions answer different questions)
Balanced complete multipartite graphs are not the same as disjoint clique unions; complementation exchanges those two structures. On four vertices with , has four edges and is the largest triangle-free graph, while two disjoint edges form the smallest graph with independence number at most two, with edges. Exchanging the two answers gives a graph that is not extremal for either problem.
Summary
Balancing part sizes gives an exact integer candidate and its correction term. A clique-removal induction proves the global extremal bound, and tight attachment to the chosen clique forces every equality graph to be balanced multipartite. Complementation gives the exact minimum-edge independent-set counterpart, while negative density tests remain inconclusive.
Exercises
Quick check
(Find the exact edge bound for four-clique-free graphs on ten vertices. State the equality shape and the complementary minimum for independence number at most three.)
Divide ten into three balanced parts.
Solution · Answer
The bound is . Equality requires the complete tripartite graph with those sizes. Thirty-four edges force a four-clique.
The complementary minimum is , attained exactly by disjoint cliques of sizes four, three and three. Their internal edge counts are six, three and three, totaling twelve, and any independent set uses at most one vertex from each clique.
Quick check
(Explain the recurrence for by removing one vertex from every balanced part. Check it for , .)
Count the removed clique and all its edges to surviving vertices.
Solution · Answer
The removed vertices form a clique with edges. Each of the remaining vertices is adjacent to all removed vertices except the one from its own part, contributing cross-edges. The remainder is still balanced, giving the recurrence.
At eight and three, and , whose difference is thirteen. The counted categories give , as required.
Quick check
(In the equality proof, why are two outside vertices missing the same clique vertex forced to be nonadjacent? Why does the final edge count force all cross-part edges?)
Use the other clique vertices before invoking balancing.
Solution · Answer
If two such outside vertices were adjacent, they and the other clique vertices would be mutually adjacent, producing the forbidden clique of size . Their assigned part, including its one missed clique vertex, is therefore independent.
The graph lies inside the complete multipartite graph on these parts. Its edge count already equals the largest possible count for any such part sizes. If a permitted cross-edge were missing, the containing multipartite graph would have strictly more edges than this maximum. Thus none is missing, and equality in the balancing result forces the sizes to differ by at most one.