Moves that only ever add edges

The edge that forces a triangle found Mantel’s bound by examining every graph on six points, and it named the general case without proving it. Forbid a complete graph on $r + 1$ points instead of a triangle; then the most edges a graph on $n$ points can have is achieved by splitting the points into $r$ parts as equal as possible and joining every pair in different parts. That is Turán’s theorem, from 1941, and the graph it names is the Turán graph.

The table in that essay checked the claim up to six points by brute force, which is persuasive and proves nothing beyond six. A proof has to work for every graph, and the proof drawn here, due to Alexander Zykov in 1949, works by never looking at the whole family of graphs at all. It takes one graph that avoids the forbidden clique and improves it, one move at a time, until it becomes the Turán graph — with the edge count rising at every move.

The move: become a copy of a non-neighbour #

The move is simple enough to state in a line. Pick two points $u$ and $v$ that are not joined. Delete all of $u$’s edges and give $u$ exactly the neighbours $v$ has. Now $u$ is a copy of $v$ — a twin, joined to the same points, and still not joined to $v$.

Two things are true of this move whatever graph it is applied to.

It cannot create the forbidden clique. A complete subgraph can contain at most one of $u$ and $v$, because they are not joined. If it contains $u$, swap $u$ for $v$: since $u$ now has exactly $v$’s neighbours, the swapped set is also complete, and it was already there before the move. So any clique after the move is a clique that existed before it, perhaps with $u$ in place of $v$ — and the move creates nothing new.

It changes the edge count by $\deg v - \deg u$. $u$ loses its old edges and gains $v$’s. So if $v$ has more neighbours than $u$, the move strictly adds edges.

That is enough to drive a graph towards the Turán graph, provided there is always a move that helps. The first figure shows one run: the graph begins with ten edges, somewhat arbitrary, and each panel names its move and prints its count. By the fourth move the graph has become complete multipartite — its points fall into groups, with no edges inside a group and every edge between groups — and a last move evens out the group sizes.

When there is no helpful move #

The moves stop when no move adds edges, and the question is what the graph looks like then.

Suppose “not joined” fails to be transitive: there are points $u$, $v$, $w$ with $u$ not joined to $v$, $v$ not joined to $w$, but $u$ joined to $w$. If $v$ has fewer neighbours than $u$, turn $v$ into a copy of $u$ — a gain. If $v$ has fewer than $w$, turn $v$ into a copy of $w$ — a gain. Otherwise $v$ has at least as many neighbours as each of $u$ and $w$, and turning both $u$ and $w$ into copies of $v$ changes the count by

$$2\deg v - (\deg u + \deg w - 1) \ge 1,$$

because the edge between $u$ and $w$ was counted in both of their degrees and is lost only once. A gain again. So whenever non-adjacency is not transitive, some move strictly adds edges.

When the moves run out, then, non-adjacency is transitive, which makes it an equivalence relation: the points fall into classes of mutually non-joined points, and points in different classes are always joined. That is a complete multipartite graph. And it still avoids the forbidden clique, so it has at most $r$ classes — one point from each of $r + 1$ classes would be $r + 1$ mutually joined points.

The second figure runs the same moves with a triangle forbidden, so the end is a graph with two classes, and the number it reaches is Mantel’s. Nothing in the moves knew what the answer would be; the answer is where they stop. One detail worth noticing is that the moves do not proceed monotonically towards the final shape — at one step a point takes on a completely different set of neighbours — and yet the count never falls. The count is the invariant that makes the argument a proof, in the same way a measure that never rises made the surface reductions terminate.

Why the parts should be equal #

The moves deliver a complete multipartite graph with at most $r$ parts. The last step is to see which one has the most edges, and that is pure arithmetic.

The table shows the answer and the argument is one line. If one part has $a$ points and another has $b \le a - 2$, move one point from the first to the second. The moved point loses its $b$ neighbours in the second part and gains the $a - 1$ other points of the first; everything else is unchanged. The count changes by $(a - 1) - b \ge 1$. So any split with two parts differing by two or more can be improved, and the only splits that cannot are those whose parts differ by at most one — the balanced ones.

That finishes Turán’s theorem. Start from any graph with no complete graph on $r + 1$ points. Zykov’s moves raise its edge count to that of some complete graph with at most $r$ parts; balancing raises it further to the Turán graph’s. So the original graph had at most as many edges as the Turán graph, which is the theorem, and the Turán graph itself avoids the clique, which shows the bound is achieved.

The count has a clean asymptotic form. With $r$ equal parts of size $n/r$, each point is joined to the $n - n/r$ points outside its part, so the edge count is about

$$\left(1 - \frac{1}{r}\right)\frac{n^2}{2}.$$

A fraction $1 - 1/r$ of all possible edges: half for triangles, two-thirds when four mutually joined points are forbidden, and so on, approaching every edge as the forbidden clique grows.

A second proof, by spreading weight #

There is a completely different proof, found by Theodore Motzkin and Ernst Straus in 1965, and it turns the question into a problem of the kind calculus solves.

Spread one unit of weight over the points of a graph: give point $i$ a weight $x_i \ge 0$, with the weights adding to $1$. Score the weighting by adding $x_i x_j$ over every edge. The question is how high the score can go.

If the weight is spread evenly over a complete subgraph of $k$ points, each of the $\binom{k}{2}$ edges contributes $1/k^2$, so the score is $\binom{k}{2}/k^2 = \tfrac12(1 - 1/k)$. The Motzkin–Straus theorem says that nothing does better: the best score is exactly $\tfrac12(1 - 1/\omega)$, where $\omega$ is the size of the largest complete subgraph. On the five-cycle, $\omega = 2$ and the best is a quarter; the search in the figure, started from four hundred random weightings, reaches a quarter every time and never more.

Now Turán’s theorem is one line. Take a graph with no complete graph on $r + 1$ points, so $\omega \le r$, and weight every point equally, $x_i = 1/n$. The score is $e/n^2$, where $e$ is the number of edges. It cannot exceed the best possible score, so

$$\frac{e}{n^2} \le \frac12\left(1 - \frac{1}{r}\right), \qquad e \le \left(1 - \frac1r\right)\frac{n^2}{2}.$$

That is Turán’s bound in its asymptotic form, and the even weighting is the natural one to try, because the Turán graph’s own best weighting is the even one.

The third example makes a point about the search. Starting from random weightings, some runs settle on the triangle and score a third, others find the complete subgraph on four points and score three-eighths. The strict local maxima of the score sit on cliques that cannot be extended, and the global maximum on a largest one — so the continuous problem inherits the difficulty of finding the largest clique, which is one of the standard hard problems of computation. The theorem converts a question about graphs into one about maximising a quadratic over a triangle-shaped region of weightings, and the conversion runs both ways: maximising such quadratics is exactly as hard as finding large cliques.

Where the theorem turns up without being asked #

Turán’s theorem is quoted far outside graph theory, because many questions that do not mention graphs have a forbidden clique hiding in them. The cleanest example is geometric, and it is a result of Erdős from 1955.

Scatter $n$ points in the plane so that no two are more than distance $1$ apart. How many of the pairs can be far apart — more than $1/\sqrt2$? Join two points when their distance exceeds $1/\sqrt2$, and ask whether this graph can contain four mutually joined points.

It cannot. Among any four points in the plane, some three form a triangle with an angle of at least $90°$: either the four are the corners of a convex quadrilateral, whose four angles add to $360°$ so one is at least $90°$, or one lies inside the triangle of the other three, where the three angles around it add to $360°$ and one is at least $120°$. In a triangle with an angle of at least $90°$, the square of the side opposite that angle is at least the sum of the squares of the other two — Pythagoras, with an inequality where the right angle was. If both other sides exceeded $1/\sqrt2$, the opposite side would exceed $1$, which is forbidden. So among any four points some pair is within $1/\sqrt2$, and the graph of far pairs has no complete subgraph on four points.

Turán’s theorem then caps the far pairs at about $n^2/3$, the edge count of the balanced three-part graph. And the bound is achieved: put the points in three tight clusters at the corners of an equilateral triangle of side just under $1$. Pairs within a cluster are close, pairs across clusters are far, and the far pairs form exactly the complete three-part graph. The extremal configuration of a question about distances is the extremal graph of a question about cliques, turned into geometry.

A second everyday consequence is the theorem read backwards. Turn every edge into a non-edge and vice versa: a graph with no large complete subgraph becomes a graph with no large set of mutually non-joined points, and Turán’s bound becomes a guarantee that every graph with average degree $d$ contains $n/(d + 1)$ points no two of which are joined. That is the form in which it is used for scheduling and colouring, where the question is how many tasks can run together without conflict, and it sits beside the party of six as the other basic way a graph is forced to contain structure — by density rather than by colouring.

Two proofs, and what each explains #

The two proofs have different virtues, and it is worth being clear about which explains what.

Zykov’s moves explain why the extremal graph has the shape it has. The moves push towards complete multipartite graphs because non-adjacency must become transitive, and towards equal parts because unequal parts can be balanced for a gain. They also give uniqueness with a little more care: a graph that ties the Turán count must admit no strictly improving move, so it must already be complete multipartite and balanced — which is the uniqueness the first essay on this subject checked only on six points.

The Motzkin–Straus proof explains why the bound has the number it has. The fraction $1 - 1/r$ is the score of the even weighting on $r$ mutually joined points, doubled, and the theorem is the statement that a graph cannot concentrate its edges better than a complete graph of its clique size. It also connects the subject to optimisation: the density of a graph is an average of the score under the even weighting, and the density can never exceed the best score, which is decided by the largest clique.

That second connection is a small surprise worth stating plainly. A question about counting edges — a discrete, combinatorial quantity — is answered by maximising a smooth function over a continuous region, and the answer is exact. The same kind of translation, a combinatorial maximum recovered from a continuous one, is what the linear programs of the duality essays do for flows and assignments, and what a convex function read through its tangents does for optimisation in general.

There is a third thing the moves suggest and neither proof states: near the top, the shape is forced too. A graph that avoids the forbidden clique and has almost the Turán number of edges can only be a few moves away from the Turán graph, since every move gains at least one edge and there are few edges left to gain. Made precise, that is the stability theorem of Erdős and Simonovits from the 1960s: a $K_{r+1}$-free graph whose edge count is within a small fraction of Turán’s can be turned into the Turán graph by changing a small fraction of its edges. Stability is what makes extremal results usable in other proofs, because it says that a near-optimal object has a known structure — and the moves are a picture of why, since a graph that cannot gain much cannot be far from where the gaining stops.

What the pictures cannot show #

That the moves always finish. Each run drawn here ends after a handful of moves, and the proof that every run ends is that the edge count rises by at least one each time and cannot exceed $\binom{n}{2}$. The figures illustrate the moves; the termination is the counting argument, not something any finite set of runs could establish.

That the search found the true maximum. The weighting figures report the best of four hundred climbs from random starting points, compared with $\tfrac12(1 - 1/\omega)$ where $\omega$ was found by checking every set of points. The agreement is a check of the theorem on three graphs, not a proof of it; the proof is an argument about the score that moves weight between two non-adjacent points without lowering it, which is Zykov’s move again in continuous form.

The general forbidden graph. Everything here forbids a complete graph. For any other forbidden graph the moves can create it — a copy of a point can complete a cycle that was not there — and the whole argument fails. That is where the Erdős–Stone theorem takes over for graphs that need three or more colours, and where, for graphs that need only two, a different kind of argument is needed altogether.

Still open: the graphs that need only two colours #

Turán’s theorem and its extension by Erdős and Stone settle the extremal count, to leading order, for every forbidden graph whose chromatic number is at least three. For bipartite forbidden graphs the leading term vanishes and the true order of growth is a power of $n$ between $1$ and $2$ that is known only in special cases. The four-cycle is the first of them: its extremal count is of order $n^{3/2}$, established by counting pairs of neighbours from above and by a construction from a finite projective plane from below — a graph drawn from a plane that comes within a whisker of the bound.

For the cycle of length eight, and for the complete bipartite graph with four points on each side, the exponent is not known. Whether every rational number between $1$ and $2$ occurs as such an exponent was a question of Erdős and Simonovits. Bukh and Conlon showed in 2018 that every one of them is the exponent for some finite family of forbidden bipartite graphs; whether each is the exponent for a single forbidden graph is still open.

The count as the thing that never falls #

Zykov’s proof is an argument in which the object changes almost beyond recognition and one number never goes down. A graph with ten edges and no discernible structure becomes, one move at a time, the most symmetric graph that avoids the forbidden clique, and at no point does the forbidden clique appear or an edge get lost.

The Motzkin–Straus proof reaches the same number from another direction, by asking how weight should be spread over a graph to make its edges count for most. The best spread sits on a largest clique and scores $\tfrac12(1 - 1/\omega)$, and a graph’s density can never beat it. Two proofs that share nothing in method agree on one number, which is $1 - 1/r$ of all the edges there could be.