Part III · The Deep Theory

Chapter 7: Extremal Graph Theory

Created by Felipe Casadei

How much bulk must a graph have before a shape is forced to appear inside it? After this chapter you will know the exact answer for cliques, the asymptotic answer for every pattern at once, and you will be able to read the statement that every large dense graph is a small weighted graph plus noise.

One question in many disguises

Here is the entire chapter in one sentence. How much bulk must a graph have before a particular shape is forced to appear somewhere inside it?

Try the smallest interesting case by hand. Take five vertices and draw edges, as many as you like, but avoid making a triangle. Six edges is achievable: split the five vertices into a pair and a triple, and join every vertex of the pair to every vertex of the triple. Any three vertices must then include two from the same side, and two vertices on the same side are not joined, so no triangle exists. Seven edges is not achievable, as you can check by trying. On five vertices, six is exactly the triangle threshold: at six you can still dodge, at seven you cannot.

That experiment is the subject in miniature. Extremal graph theory studies such thresholds and the graphs sitting exactly at the boundary, with as much bulk as possible and still no forbidden shape. Those record holders are called extremal graphs, and the first surprise is how organised they are: pushing a graph to the limit of avoidance forces it into a rigid pattern.

"Bulk" will mean one of four things in this chapter: the total number of edges, the average degree \(d(G)\) (from Chapter 1: the average number of edges touching a vertex), the chromatic number \(\chi(G)\) (from Chapter 5: the fewest colours needed so that adjacent vertices differ), and the girth \(g(G)\) (the length of the shortest cycle). The last one is a strange kind of bulk, since large girth means an absence of short cycles, and yet it will turn out to force enormous structure.

"Shape" will mean one of three things, all from Chapter 1, and their differences run the whole chapter:

• Subgraph, written \(H \subseteq G\). A copy of \(H\) sits inside \(G\), using vertices and edges of \(G\). Extra edges among those vertices are allowed; this is not the induced notion.
• Topological minor, written \(TH \subseteq G\). A copy of \(H\) in which every edge may be stretched into a path, and the paths must avoid each other except at their ends. A subdivided triangle is a cycle of any length.
• Minor, written \(H \preccurlyeq G\). Find disjoint connected branch sets in \(G\), one per vertex of \(H\), with at least one edge of \(G\) between two branch sets whenever \(H\) has the corresponding edge. Squash each branch set to a point and you see \(H\).

These three nest in one direction. A subgraph copy is a topological copy whose paths have length 1, and a topological copy becomes a minor once each path is contracted. So subgraphs are hardest to find and minors easiest, and the forcing costs run the other way: subgraphs are expensive to force, minors cheap. Learners invert this constantly, so fix the direction now.

The chapter splits into two halves. The first answers the threshold question. Subgraph containment needs a constant fraction of all possible edges, the dense regime, where Turán's theorem is exact for cliques and the Erdős–Stone theorem is asymptotic for every pattern at once. Minor containment needs only a linear number of edges, the sparse regime, which closes with Hadwiger's conjecture, widely considered the deepest open problem in graph theory.

The second half teaches a technique: Szemerédi's regularity lemma, which says that every large graph, however wild, looks at coarse resolution like a small weighted graph plus noise. Two reusable tools follow, the counting lemma and the removal lemma, and then a result with no graphs in it at all: every set of integers that keeps a fixed percentage of the whole numbers contains three evenly spaced numbers. A theorem about arithmetic, proved by drawing a graph.

This is the hardest chapter in Part III. Take it in the order written. Everything after the regularity lemma depends on being comfortable with what that lemma says, and the plain-language version of it is given at length before a single \(\epsilon\) appears.

New notation in this chapter

Twelve symbols are genuinely new; the rest are recalled from earlier chapters and re-glossed where they appear. If \(X \subseteq A\) ("X is a subset of A") is still unfamiliar, Chapter 0 is the bootstrap.

Extremal numbers and the record holders

Fix a graph \(H\), the forbidden pattern, and a number \(n\) of vertices. Among all graphs on \(n\) vertices that contain no copy of \(H\), some have more edges than others. The record is what we want to name.

A weaker property sounds like the same thing and is not. Call a graph edge-maximal without \(H\) if it contains no \(H\) but adding any single new edge creates one. Edge-maximal means locally stuck. Extremal means globally best. Every extremal graph is edge-maximal, since if you could add an edge you would not have been at the record. The converse fails, and Figure 7.1 shows the standard example.

Turán's theorem: the exact answer for cliques

Now fix the forbidden pattern to be the complete graph \(K^r\), that is, \(r\) vertices with all \(\binom{r}{2}\) edges among them. How many edges can an \(n\)-vertex graph carry with no \(r\) vertices all mutually joined?

There is an obvious way to dodge a \(K^r\). Split the \(n\) vertices into \(r-1\) teams, and join two vertices exactly when they are on different teams. Any \(r\) vertices must then contain two teammates, by the pigeonhole principle, and teammates are not joined, so no \(K^r\) appears. To make this construction as dense as possible you want the teams as equal in size as you can manage, because moving one vertex from a large team to a small team strictly gains edges. That balanced construction has a name.

Turán's theorem says that this obvious construction is not merely good, it is the unique best.

The smallest case, \(r = 3\), is Mantel's theorem from 1907: a triangle-free graph on \(n\) vertices has at most \(\lfloor n^2/4 \rfloor\) edges, achieved by the balanced complete bipartite graph. Figure 7.3 runs the five-vertex version of the opening experiment.

Diestel gives two proofs.^[1] The first is an induction on \(n\). An extremal graph \(G\) contains a \(K^{r-1}\), call it \(K\), since otherwise edges could be added. Delete the \(r-1\) vertices of \(K\); what is left must itself be extremal on \(n - r + 1\) vertices. Each remaining vertex sends at most \(r - 2\) edges into \(K\), since a vertex joined to all of \(K\) would complete a \(K^r\). Adding the three contributions gives exactly \(t_{r-1}(n)\), and equality everywhere forces the outside to be a Turán graph whose parts line up with \(K\), reassembling \(T^{r-1}(n)\).

The second proof is shorter and worth seeing, because it introduces a move that recurs in the subject.

How dense is the record holder, as a fraction of everything possible? Write the edge density of a graph as \(\lVert G\rVert / \binom{|G|}{2}\), the share of all possible pairs that are actually joined. For the Turán graph this share settles down.

This number is the yardstick for everything dense in this chapter. Half of all possible edges is the exact price of triangle-freeness. Any more, in the long run, and a triangle appears.

Erdős–Stone: one theorem for every pattern at once

Turán's theorem answers the threshold question for cliques. What about every other forbidden pattern: a five-cycle, the Petersen graph, a tree, some graph you drew on a napkin? One theorem covers them all, and the answer turns out to depend on exactly one feature of the pattern.

The bridge is a family of graphs that sit between \(K^r\) and enormous size.

Feed that theorem a general pattern \(H\) and something clean falls out. Every \(H\) sits inside a big enough blown-up clique: if \(H\) needs \(\chi(H)\) colours, then colouring \(H\) sorts its vertices into \(\chi(H)\) groups with no edges inside a group, so \(H\) fits into \(K^{\chi(H)}_s\) once \(s\) is at least the size of the largest colour group. And in the other direction, the Turán graph \(T^{\chi(H)-1}(n)\) contains no \(H\) at all, since that graph can be coloured with \(\chi(H) - 1\) colours while \(H\) cannot. Squeeze the two bounds together.

The formula has a blind spot, and it is honest about it. If \(H\) is bipartite then \(\chi(H) = 2\) and the limit is 0. That says only that \(\mathrm{ex}(n, H)\) grows more slowly than \(n^2\); it does not say how fast. For \(H = K_{r,r}\) the truth is pinned only between \(c_1 n^{2 - 2/(r+1)}\) and \(c_2 n^{2 - 1/r}\), and even the exponent is open in general.^[1] If \(H\) is a forest, \(\mathrm{ex}(n, H)\) is at most linear in \(n\). The Erdős–Sós conjecture from 1963 guesses the exact shape there: \(\mathrm{ex}(n, T) \leq \frac{1}{2}(k-1)n\) for every tree \(T\) with \(k\) edges, which would say average degree above \(k-1\) forces every \(k\)-edge tree. It is known for stars and paths, open in general.

Minors: a bounded average degree is enough

Everything so far needed a quadratic number of edges. Now relax the pattern from subgraph to minor, and the price collapses. The reason is that a minor may use long detours: a branch set of a hundred vertices, contracted, counts as one vertex of the pattern. Once detours are legal, a graph does not need to be dense, it only needs to be dense enough somewhere to keep branch sets connected.

The proof idea is a neat induction.^[2] Among all minors of \(G\) whose edge-to-vertex ratio is still high, take one, call it \(H\), that is minimal: contracting any further edge would spoil the ratio. Minimality means every edge of \(H\) is "expensive" to contract, which forces any two adjacent vertices to share many neighbours. Fix a vertex \(x\); its neighbourhood then induces a graph in which every vertex has high degree, so induction supplies a \(K^{r-1}\) minor inside the neighbourhood. Add \(x\) itself, joined to all of it, and you have \(K^r\).

Three sharper results follow, and the numbers are worth a table because the comparison is the actual content of the section.

Read the table as a price list. Subgraph containment costs a quadratic number of edges, which no bounded average degree can ever pay. Subdivisions cost about \(r^2\) average degree, minors only about \(r\sqrt{\log r}\). The sharp bound for subdivisions reuses earlier machinery: pull out a highly connected subgraph using the result from Chapter 1 that large average degree yields a highly connected piece, then use the linkage theorem from Chapter 3 to join designated pairs of vertices by disjoint paths, one path per edge of \(K^r\).^[2] Kostochka's theorem is stated without proof in Diestel and here; random graphs supply the matching lower bound, so its growth rate cannot be improved.^[2]

Now the strangest result of the chapter. Girth is the length of the shortest cycle, so large girth means the graph looks locally like a tree, which feels like the opposite of structure. It forces structure anyway.

Two theorems follow. Thomassen's theorem: minimum degree 3 plus girth at least \(f(r)\), with \(f(r)\) growing like \(8\log r\), forces a \(K^r\) minor. The proof pumps the minimum degree up with the lemma above, then calls Kostochka's theorem.^[2] The Kühn–Osthus theorem is stronger for subdivisions: one universal girth bound, the same for every \(r\), together with minimum degree at least \(r-1\), forces a subdivided \(K^r\). That degree condition is needed anyway, just to give the branch vertices somewhere to send their paths.^[2]

Figure 7.6 shows the phenomenon at the smallest scale on a graph you have already met.

Hadwiger's conjecture: colours and minors

Chapter 5 left a question hanging. A graph that needs many colours must be complicated somehow, but how? The naive guess, that a graph needing \(r\) colours contains \(r\) mutually adjacent vertices, is false and spectacularly so: there are triangle-free graphs needing as many colours as you like. Hadwiger's guess from 1943 replaces "contains" by "contains as a minor", and it has resisted everything since.

The small cases are proved through structure theorems, and they follow one template: describe exactly how the graphs with no \(K^r\) minor are built, then colour the building blocks. Start with \(r = 4\).

The case \(r = 5\) is where the four colour theorem enters. Wagner proved in 1937 that every edge-maximal graph with no \(K^5\) minor is built, by pasting along triangles and along single edges, from two kinds of blocks: plane triangulations, and copies of one specific eight-vertex graph.^[3]

Two consequences follow. First, a graph with no \(K^5\) minor has at most \(3n - 6\) edges, the same bound planar graphs obey (from Chapter 4). Second, Hadwiger's conjecture holds for \(r = 5\): plane triangulations need at most four colours by the four colour theorem, the Wagner graph needs three, and pasting along complete subgraphs never raises the number of colours above the worst block. Run the argument backwards and you see the equivalence: since planar graphs have no \(K^5\) minor, Hadwiger for \(r = 5\) would say every planar graph is 4-colourable, which is the four colour theorem itself.^[3]

Robertson, Seymour and Thomas proved the case \(r = 6\) in 1993, by showing that a minimal counterexample would have to be a planar graph plus one extra vertex, which the four colour theorem then colours with five colours.^[3] The case \(r = 7\) is open, and so is everything beyond. Kühn and Osthus proved the conjecture for all large \(r\) among graphs with no \(K_{s,s}\) subgraph, and it is also known for graphs of large girth, for line graphs, and for almost all graphs in the random sense of Chapter 11.^[3]

One tempting strengthening is dead. Hajós conjectured the same statement with subdivisions in place of minors, and Catlin disproved it in 1979. It survives only with an extra assumption: above one universal girth bound the subdivision version does hold, for every \(r\). That proof is a two-step chain, from chromatic number to minimum degree by the colouring lemma of Chapter 5^[8], then from minimum degree plus girth to a subdivided clique by the Kühn–Osthus theorem above.^[3]

The regularity lemma, before any epsilon

The rest of the chapter is one idea and its consequences. Read this section slowly; the symbols come later, on purpose.

Suppose someone hands you a graph with a million vertices and asks what it looks like. You cannot draw it. What you can do is summarise it: split the million vertices into, say, forty groups of twenty-five thousand, and report one number for each pair of groups, namely the share of possible edges between them that are actually present. That is a summary of forty numbers per row, a small weighted graph, a table you can print on one page.

Every summary loses information. The question is whether it must lose the information you care about. A line saying "groups 3 and 7 are joined at density one half" is compatible with two very different realities. In the first, the edges between the two groups are sprinkled evenly, so any large sample from group 3 sees about half of any large sample from group 7. In the second, half of group 3 is joined completely to half of group 7 and the other halves are joined to nothing. Both report one half. Only the first lets you predict anything about pieces you did not sample.

Szemerédi's regularity lemma says that a summary of the good kind always exists. For any graph at all, with no assumptions whatsoever, you can split the vertices into equal groups so that nearly every pair of groups behaves like reality A: the edges between them are spread so evenly that any large window on one side sees about the same density towards any large window on the other. The number of groups needed is bounded by a number that depends only on how strict "about the same" is, and not on the graph. A million vertices or a trillion: the same bounded summary size.

Now the symbols. Two definitions carry the weight.

Two design choices in that definition deserve a sentence each. The size thresholds \(\epsilon|A|\) and \(\epsilon|B|\) are unavoidable. Without them you could take \(X\) and \(Y\) to be single vertices, whose density is 0 or 1 by definition, and no pair on earth would qualify. And smaller \(\epsilon\) makes the condition harder in two ways at once: smaller windows come under scrutiny, and less deviation is tolerated inside them. Figure 7.9 contrasts an evenly spread pair with a conspiratorial one.

The bin \(V_0\) is bookkeeping, not pathology. It exists because \(n\) need not divide evenly into \(k\) parts, and the proof wants the parts exactly equal. Its vertices are not bad, just unassigned, and there are few of them. Allowing a few irregular pairs is also necessary: some graphs cannot avoid them.

That argument also explains the lemma's price. Each round can multiply the number of parts by a factor like \(4^{k+1}\), and there can be \(2/\epsilon^5\) rounds, so the bound \(M\) is a tower of exponentials in \(1/\epsilon\). Nobody applies the lemma numerically. It is an existence statement used inside proofs, and the constants it produces are astronomically large.

Using the lemma: the summary graph and the way back down

A summary is only useful if you can argue in it and then return. Two constructions do the returning.

The technical fact that makes the return trip work is this. Inside a regular pair, almost every vertex on one side has roughly its fair share of neighbours in any large target set on the other side. Precisely: if \((A,B)\) is \(\epsilon\)-regular with density \(d\), and \(Y \subseteq B\) has \(|Y| \geq \epsilon|B|\), then fewer than \(\epsilon|A|\) vertices of \(A\) have fewer than \((d - \epsilon)|Y|\) neighbours inside \(Y\).^[5] Almost nobody is starved of the target set. That is what lets you build a copy of a pattern one vertex at a time without painting yourself into a corner.

The proof embeds the vertices of \(H\) one at a time.^[5] Each vertex of \(H\) not yet placed carries a shrinking "still allowed" set inside the chunk it is assigned to. Every time one of its neighbours gets placed, the allowed set shrinks to the neighbourhood of the chosen image, and the fact above says it shrinks only by a factor of about \(d\). A vertex of degree at most \(\Delta\) suffers at most \(\Delta\) such shrinkings, so its allowed set never drops below about \(d^{\Delta}\ell\), which stays large enough to keep choosing fresh vertices. Bounded degree is what bounds the damage.

Now the Erdős–Stone theorem can be proved, and its proof is the template for the whole method.^[5] Start with a graph having \(t_{r-1}(n) + \epsilon n^2\) edges and apply the regularity lemma. Then ask where the surplus edges could hide. Edges touching the bin are few, because the bin is small. Edges inside a single chunk are few, because chunks are small. Edges in irregular pairs are few, because at most \(\epsilon k^2\) pairs are irregular. Edges in pairs of density below the threshold \(d\) are few, because the threshold is low. Everything else lies in regular pairs of decent density, and so appears as an edge of the summary graph \(R\). The four "few" terms cannot absorb the surplus, so \(R\) itself carries more than \(t_{r-1}(k)\) edges. Turán's theorem, applied to the tiny graph \(R\), hands you a \(K^r\) inside it; blow it up to \(K^r_s\) inside \(R_s\), and the blow-up lemma drops it back into \(G\).

Two off-the-shelf tools: counting and removal

The blow-up lemma answers "does a copy exist?". The next tool answers "how many copies are there?", and the answer is the one a coin-flipping random graph would give.

Counting is easier if you count maps rather than copies. A homomorphism from \(H\) to \(G\) is a map sending each vertex of \(H\) to a vertex of \(G\) such that every edge of \(H\) lands on an edge of \(G\). Non-adjacent vertices of \(H\) may collapse to the same vertex of \(G\); the injective homomorphisms, the ones that never collapse, are exactly the labelled copies of \(H\) inside \(G\). The count is written \(\hom(H, G)\). Counting maps keeps the algebra clean, and when \(G\) is large the collapsing maps are too few to matter.

One caveat: the counting lemma is stated for a variant of regularity called uniformity, which compares every non-empty window against a chosen target density with an allowance that grows as the window shrinks.^[6] Nothing is lost. Regular pairs are uniform, and uniform pairs are regular after replacing \(\epsilon\) by its cube root, so the two notions are interchangeable up to renaming the parameter.

The proof is one paragraph once the tools are in place.^[6] Take a regular partition and delete every edge that touches the bin, lies inside a chunk, lies in an irregular pair, or lies in a pair of density below \(\varrho\). The same four-term count as before shows this is at most \(\varrho n^2\) edges. Now suppose a copy of \(H\) survived. All of its edges then live in regular pairs of decent density, so the chunks it occupies form a seating plan of exactly the kind the counting lemma handles, and the counting lemma manufactures far more copies of \(H\) than the hypothesis allowed. Contradiction, so no copy survived.

Thin spreading squeezes from both sides. Because no edge is in many copies, copies are rare enough for the removal lemma to apply, and it returns a small set of edges meeting every copy. Because every edge is in some copy, and each deleted edge destroys only a bounded number of copies, the whole edge set can be only a bounded multiple of that small set. So the graph is sparse.^[6]

The payoff: a theorem about numbers, proved with a graph

Leave graphs for a moment. An arithmetic progression is a run of numbers with a constant gap: 3, 7, 11 is one of length 3 with gap 4. A set of whole numbers has positive upper density if there is a fixed share \(\delta > 0\) such that the set claims at least \(\delta n\) of the first \(n\) whole numbers, for infinitely many \(n\). The even numbers have upper density \(1/2\). The powers of 2 have upper density 0.

Write \(r_k(n)\) for the largest size of a subset of \(\{0, 1, \dots, n-1\}\) that contains no arithmetic progression of length \(k\). For example \(r_3(5) = 4\): the set \(\{0, 1, 3, 4\}\) has no three evenly spaced members, while any five-element subset of \(\{0,\dots,4\}\) is everything and contains 0, 1, 2.

The proof of the general case is far beyond this course, and beyond Diestel's book, which states it and moves on.^[7] The historical point is worth knowing: the regularity lemma was invented as a step inside that proof. What Diestel does prove, in a single page, is the first non-trivial case, \(k = 3\), which is Roth's theorem from 1953. The proof is a graph argument, and it is the cleanest demonstration in the book that the regularity method reaches outside graph theory.

Here is the construction, and it is worth following move by move. Let \(D\) be a set of numbers below \(n\) with no three-term progression. Build a graph on three rows of vertices: a row \(X\) holding \(1, \dots, n\), a row \(Y\) holding \(1, \dots, 2n\), and a row \(Z\) holding \(1, \dots, 3n\). For every \(x\) in \(X\) and every \(d\) in \(D\), draw a triangle on the three vertices \(x\) in \(X\), \(x + d\) in \(Y\), and \(2x + d\) in \(Z\). Call it the defining triangle \(K(x, d)\). The graph consists of exactly the edges of these triangles, and nothing else.

Two observations finish the proof. First, the defining triangles are edge-disjoint. Given two of the three vertices, the third is forced: from \(x\) and \(x+d\) you recover \(d\); from \(x\) and \(2x+d\) you recover \(d\) again; from \(x+d\) and \(2x+d\) you recover \(x\) by subtracting. So no edge lies in two defining triangles, and the edge count is exactly \(3n|D|\), three edges for each of the \(n|D|\) triangles.

Second, there are no other triangles. Suppose some triangle of the graph is not one of the defining ones. Its three edges must then come from three different defining triangles, say \(K(x,a)\), \(K(x,b)\) and \(K(x',c)\), and matching up the shared vertices gives \(x + a = x' + c\) and \(2x + b = 2x' + c\). Subtracting and rearranging turns those two equations into \(a = c + (x' - x)\) and \(b = c + 2(x' - x)\), which says that \(c, a, b\) are three numbers of \(D\) with a constant gap. That is a three-term progression inside \(D\), which we forbade. So no such triangle exists.

Put the two observations together: every edge of this graph lies in exactly one triangle. The corollary of the previous section then applies. The graph has \(6n\) vertices in total, so for any \(\gamma\) chosen in advance and \(n\) large, \[ 3n|D| = \lVert G\rVert \leq \gamma (6n)^2 = 36 \gamma n^2, \] which gives \(|D| \leq 12\gamma n\). Since \(\gamma\) was arbitrary, the share \(|D|/n\) can be forced below any positive number, which is precisely the statement \(r_3(n)/n \to 0\).^[7]

What is proved here, and what is not

This chapter has stated more than it has proved. Diestel proves in full, and the sketches here follow him, on: Turán's theorem in two ways, the Turán density limit, the propositions forcing complete minors and subdivisions from average degree, the structure theorems for graphs without a \(K^4\) or \(K^5\) minor, the regularity lemma with its scoring argument, the blow-up lemma, the Erdős–Stone theorem, the counting and removal lemmas, and Roth's theorem.^[1][7] Stated without proof, there and here: Kostochka's theorem, the two Kühn–Osthus theorems, Hadwiger's conjecture for \(r = 6\), and Szemerédi's theorem for progressions of length four and beyond. The section numbers are the map for the real thing: §7.2 for the minor bounds, §7.3 for Hadwiger, §7.4 and §7.5 for regularity, §7.6 for the two tools, §7.7 for the arithmetic.^[2][3]

The spine, in one paragraph. Bulk forces patterns, and the exchange rate depends on how loosely the pattern may sit inside the host. Subgraphs are expensive, and the price is exactly known: Turán for cliques, Erdős–Stone for everything else, with chromatic number the only feature of the pattern that survives to the limit. Minors are cheap, and the open question there is not the price but whether chromatic number can pay it, which is Hadwiger's conjecture. In between sits a technique that turns any large dense graph into a bounded summary, and it reaches far enough to prove theorems about integers. The subject is not finished: it is where several recent advances in combinatorics have happened, including the first exponential improvement in almost ninety years on the bound for the diagonal Ramsey numbers, a close cousin of the questions asked here.^[14]