The edge that forces a triangle

Six points, and edges drawn between some of them. How many edges can be drawn before three of them are forced to close a triangle?

The answer is nine — and once it is nine, there is essentially only one way to do it.

The graph that achieves it is the one where the points are split into two halves and every edge runs between them. That is not a coincidence and it is not one of several answers; it is the answer, and understanding why is the content of the theorem.

Why a two-part graph has no triangle #

Split the points into two groups and join every point in one group to every point in the other, with no edges inside either group. A triangle needs three points pairwise joined; by the pigeonhole principle two of any three points lie in the same group, and those two are not joined. So there is no triangle, for free, without checking anything.

That argument is more things than boxes in one line, and it is the only easy half of the theorem. The hard half is that no other construction does better.

How many edges does the split give? If the groups have $a$ and $b$ points with $a + b = n$, the count is $ab$, and $ab$ is largest when $a$ and $b$ are as equal as possible. For $n = 6$ that is $3 \times 3 = 9$; for $n = 5$ it is $3 \times 2 = 6$. In general the maximum is $\lfloor n^2/4 \rfloor$.

The half that has to be proved #

Mantel’s theorem, from 1907, says that $\lfloor n^2/4\rfloor$ is not merely achievable but optimal: any graph on $n$ points with more edges contains a triangle.

The cleanest proof is a counting argument over the edges. Take a triangle-free graph and let $u$ and $v$ be two points joined by an edge. No point can be adjacent to both — that would close a triangle — so the degrees satisfy $d(u) + d(v) \le n$. Add that inequality over all $m$ edges:

$$\sum_{uv \in E} (d(u) + d(v)) \le mn.$$

The left-hand side has another reading. Each point $u$ contributes $d(u)$ to the sum once for every edge at it, so it contributes $d(u)^2$ in total, and the sum is $\sum_u d(u)^2$. By Cauchy–Schwarz that is at least $(\sum_u d(u))^2/n = (2m)^2/n$. Putting the two together gives $4m^2/n \le mn$, so $m \le n^2/4$.

The move is counting the same sum two ways — once by edges, once by points — which is the habit half this field runs on. Seven bridges, and the invention of throwing things away counts edge-ends by vertices to get the handshake lemma; this counts a weighted version of the same thing.

Checked by exhaustion #

The proof above is short and correct and still worth checking, because the statement it proves is about a maximum over all graphs and the proof never looks at one.

The table extends the question. Instead of forbidding a triangle, forbid a complete graph on $r$ points. The construction generalises immediately: split the points into $r - 1$ groups and join everything between groups. A complete graph on $r$ points would need two of its points in the same group, so it cannot appear; and making the groups as equal as possible maximises the edge count.

That graph is the Turán graph, and Turán proved in 1941 that it is optimal — the same statement as Mantel’s with $r = 3$, thirty-four years later and considerably harder.

Why the extremal graph is unique #

Being able to name the best construction is one thing. Knowing that nothing else ties with it is another, and it is the part that makes the theorem useful downstream.

Look again at the search on six points. The maximum is nine, and it is not merely that some nine-edge triangle-free graph is a balanced two-part graph — every nine-edge triangle-free graph on six points is, up to relabelling the points. The figure reads the split off the graph it found rather than imposing it: it two-colours the points by walking the edges, and then checks that no edge has both ends the same colour.

That check is not decoration. A triangle-free graph need not be two-colourable at all — the five-cycle is triangle-free and needs three colours — so the fact that the extremal one is two-colourable is a property of being extremal rather than of being triangle-free.

So the five-cycle is the counterexample to the lazy statement “triangle-free graphs are bipartite”, and the theorem’s uniqueness claim survives it by a margin of exactly one edge. Adding any edge to the five-cycle produces a triangle-free graph on five points with six edges — and that graph is the complete bipartite one.

Where it sits among its neighbours #

Three results on this site ask what a graph is forced to contain, and they are forced by different quantities.

Six people at a party forces a monochromatic triangle by colouring: every two-colouring of the complete graph on six points has one, whatever the colouring is. That is Ramsey’s theorem, and the forcing quantity is the number of points.

This essay forces a triangle by density: enough edges, regardless of arrangement. The forcing quantity is the edge count, and the threshold is quadratic.

Two graphs that will not lie flat forbids a subgraph and asks what follows for drawing rather than for counting — although the edge bound there, $3n - 6$ for a planar graph, is an extremal statement of exactly this kind, proved by Euler’s formula instead of by counting degrees.

The three are the beginnings of three ladders and they should not be run together. Ramsey bounds grow exponentially and are mostly unknown; extremal bounds are quadratic and are known exactly for complete graphs; the planar bound is linear and elementary.

What happens for graphs other than complete ones #

Turán’s theorem settles the question when the forbidden subgraph is complete. For anything else the answer is harder and, in one large case, not known at all.

The Erdős–Stone theorem gives the general answer in terms of the forbidden graph’s chromatic number: if $H$ needs $k$ colours, then the most edges an $H$-free graph on $n$ points can have is $\left(1 - \frac{1}{k-1}\right)\frac{n^2}{2}$ plus a lower-order correction. For $H$ a triangle, $k = 3$ and the formula gives $n^2/4$, recovering Mantel.

The trouble is $k = 2$. A bipartite $H$ makes the leading term vanish, and the theorem says only that the answer is smaller than quadratic without saying what it is. For $H$ a four-cycle the truth is about $\frac{1}{2}n^{3/2}$; for a complete bipartite graph with three points on each side it is about $n^{5/3}$; for the eight-cycle nobody knows the exponent. The whole difficulty of extremal graph theory is concentrated in the bipartite case, which is exactly the case Turán’s construction has nothing to say about, because a bipartite forbidden graph cannot be avoided by splitting into two parts.

What happens just past the threshold #

A theorem that says “more than $n^2/4$ edges forces a triangle” leaves an obvious follow-up unanswered: how many triangles?

The naive guess is one. Adding a single edge to the balanced two-part graph on six points closes exactly three triangles — the new edge joins two points in the same half, and each of the three points in the other half completes one. So the true answer is at least three there, and the question is what it is in general.

Rademacher answered it, for one edge past the threshold, in the 1940s: $\lfloor n^2/4 \rfloor + 1$ edges force at least $\lfloor n/2 \rfloor$ triangles. Not one, not a bounded number — a count growing with $n$. The threshold is not a wall that is scraped past; it is a wall that, once crossed, is well and truly behind.

Erdős pushed the same question further: $\lfloor n^2/4\rfloor + k$ edges force at least $k\lfloor n/2\rfloor$ triangles, for $k$ up to about $n/2$. That is the phenomenon called supersaturation, and it is a general one: for essentially any forbidden subgraph, exceeding the extremal count by a constant fraction forces not one copy but a constant fraction of all possible copies.

The reason it happens is worth seeing on the six-point case, because it is entirely visible there. The extremal graph is missing exactly six edges, and the figure at the top of this essay checks that every one of them would complete a triangle. There is no slack anywhere: the extremal graph is saturated, in the sense that it is a maximal triangle-free graph and not merely a maximum one. Any edge added lands in a place that was already the third side of something.

So the “and each of the six missing edges would complete a triangle” line in that first caption is not a decorative check. It is the local form of Rademacher’s theorem, and it is why the count jumps rather than creeping.

The other direction: maximal but not maximum #

Being unable to add an edge is a weaker property than having the most edges, and the gap between the two is instructive.

A maximal triangle-free graph is one where adding any edge creates a triangle. A maximum one has the most edges. Every maximum graph is maximal — otherwise it would not be maximum — and the converse fails badly.

The five-cycle is maximal: adding any of its five missing edges creates a triangle. It has five edges, against the maximum of six. On $n$ points the smallest maximal triangle-free graph has about $n^{3/2}$ edges rather than $n^2/4$, which is a different order of magnitude, so “cannot be improved locally” and “cannot be improved at all” are separated by a gulf.

This is the standard hazard of greedy reasoning about extremal problems, and it is worth naming because it recurs. Adding edges one at a time until nothing can be added does not find the maximum; it finds a maximal graph, and maximal graphs come in a wide range of sizes. The exhaustive searches in this essay avoid the trap by construction — they examine every graph rather than growing one — which is the whole reason the field’s small cases are done by machine.

Where it came from #

Mantel published the triangle case in 1907 in a Dutch problem journal, as a solved problem rather than a theorem, and it went largely unnoticed.

Turán proved the general case in 1941, while in a labour camp, working without access to a library and writing on whatever paper was available. He remarked afterwards that the isolation had one advantage: with nothing to read, there was nothing to be told the problem was hard. The paper founded extremal graph theory as a subject, and the Turán graph is now the standard example against which every extremal question is first tested.

Erdős’s contribution, over the following decades, was to ask the question for every forbidden graph rather than for complete ones, and to notice that the chromatic number is what governs the answer — which is not visible from Turán’s proof at all.

What the pictures cannot show #

The searches here run on five and six points, where every graph can be examined: 1,024 and 32,768 of them. At seven points there are two million and at ten points over thirty-five billion, so the exhaustive method stops almost immediately. Nothing in a picture of the six-point case indicates that the method does not scale, and the theorem is about all $n$.

The extremal graph is drawn with its points on a circle, which makes the two halves interleave rather than sit apart. That is a drawing choice; the split is real and the geometry is not. A drawing with the halves separated would make the structure more obvious and would suggest, falsely, that the graph knows where its halves are before the search finds them.

And the uniqueness claim — that every extremal graph is the balanced two-part one — is checked here only for the graph the search happened to return first. The search finds a maximum, not the family of all maxima, and the two-colouring check confirms the returned graph’s structure rather than every optimal graph’s.

The ladder from here #

Below: six people at a party, which forces a triangle by a different quantity, and more things than boxes, the counting step in the easy half. Sideways: one bottleneck and nothing else, another theorem about bipartite graphs where a single obstruction is the whole story, and counting the colourings, which counts what a graph admits rather than what it forces. Above: Turán’s theorem proved in general, the Erdős–Stone theorem, the Kővári–Sós–Turán bound for bipartite forbidden graphs, and the stability theorems that say a near-extremal graph is nearly the extremal one.

What is worth carrying away #

The bound is $n^2/4$ and the construction achieving it is the most obvious one anybody would try. That combination is rarer than it sounds: in most extremal problems the best construction is strange, and in this one it is the first thing to come to mind.

What the theorem adds is that there is nothing else. Knowing the answer to an extremal question is worth much less than knowing that the answer is unique, because uniqueness is what lets a later argument say “and therefore the graph looks like this” rather than “and therefore it has at most this many edges”. Turán’s construction is used far more often as a description than as a count.