Turán's theorem

Theorem

Turán's theorem

T-113Home MU-307Threads structure · number

Statement

Let \(r,n \in \mathbb{N}\) with \(r \geq 1\), and let \(G\) be a simple graph on \(n\) vertices that contains no subgraph isomorphic to the complete graph \(K_{r+1}\) (i.e. \(G\) is \(K_{r+1}\)-free). Then \[ e(G) \;\leq\; \left(1-\frac{1}{r}\right)\frac{n^2}{2}, \] and in fact \(e(G) \leq e(T(n,r))\), where \(T(n,r)\) is the Turán graph: the complete \(r\)-partite graph on \(n\) vertices whose parts are as equal in size as possible (sizes \(\lceil n/r\rceil\) or \(\lfloor n/r\rfloor\)). Equality holds if and only if \(G \cong T(n,r)\).

Why it matters

Turán's theorem is the founding result of extremal graph theory: it answers the most natural possible question — "how many edges force a given substructure?" — for the simplest possible substructure, a clique. It converts a purely combinatorial forbidden-subgraph condition into a sharp quantitative bound, and it is the prototype for an entire field: essentially every extremal result of the form "\(H\)-free graphs have at most \(f(n)\) edges" (the Erdős–Stone theorem, the Kővári–Sós–Turán theorem, Ramsey-type stability results) is either a generalisation of, or directly built on, this theorem.

It also has a strikingly clean extremal object: not merely an upper bound, but an exact, uniquely-optimal construction (the balanced complete multipartite graph), which is unusual in extremal combinatorics and is what makes the theorem a genuine structural classification rather than just an inequality.

Hypotheses

\(G\) is a simple, finite graph (no loops, no multiple edges). Counterexample if dropped: allow a multigraph with two vertices joined by \(N\) parallel edges and no third vertex — it contains no \(K_3\) at all (a triangle needs three vertices) yet has \(N\) edges, unboundedly many; the bound \((1-1/r)n^2/2\) is meaningless without simplicity.

\(r \geq 1\) is a fixed positive integer, and "\(K_{r+1}\)-free" means literally no \(r+1\) mutually adjacent vertices. If \(r=0\) the statement degenerates (\(K_1\)-free forces \(G\) to have no vertices at all); the theorem is stated for \(r\geq 1\), where \(K_2\)-free (\(r=1\)) correctly forces \(e(G)=0\), matching the bound \((1-1/1)n^2/2=0\).

\(G\) is \(K_{r+1}\)-free, not merely "sparse" or "\(K_{r+1}\)-avoiding on average". Counterexample if dropped: the complete graph \(K_n\) has \(\binom{n}{2}\) edges, far exceeding \((1-1/r)n^2/2\) for any fixed \(r \lt n-1\); without the forbidden-subgraph hypothesis there is no upper bound below \(\binom n2\).

Uniqueness of the extremal graph requires taking \(G\) to be a graph attaining equality, and "as equal as possible" partition sizes to be forced, not merely achievable. Counterexample if dropped: for \(n=6,r=2\) the complete bipartite graph \(K_{2,4}\) is \(K_3\)-free with \(8\) edges, while \(T(6,2)=K_{3,3}\) has \(9\) edges — so an unbalanced complete bipartite graph is \(K_3\)-free but strictly sub-extremal; equality is achieved only by the balanced partition.

Proof

Among all \(K_{r+1}\)-free graphs on the fixed vertex set \([n]\), let \(G\) be one with the maximum possible number of edges.

Existence: there are only finitely many labelled graphs on \(n\) vertices (at most \(2^{\binom n2}\)), and the empty graph is \(K_{r+1}\)-free, so the set of \(K_{r+1}\)-free graphs on \([n]\) is non-empty and finite; a maximiser of the edge count exists. A

If \(x,y\) are non-adjacent vertices of \(G\) with \(\deg(x) \lt \deg(y)\), form \(G'\) by deleting every edge at \(x\) and joining \(x\) instead to every vertex of \(N_G(y)\). Then \(e(G') \gt e(G)\) and \(G'\) is still \(K_{r+1}\)-free.

(Zykov symmetrisation lemma.) Edge count: \(e(G')-e(G) = \deg(y)-\deg(x) \gt 0\) since only the edges at \(x\) changed and \(x\) now has the same degree as \(y\) (note \(y \notin N_G(y)\), so \(x\) still is not made adjacent to \(y\), consistent with \(xy\notin E\)). \(K_{r+1}\)-freeness: any clique of \(G'\) avoiding \(x\) is a clique of \(G\setminus x \subseteq G\); any clique \(C\) of \(G'\) containing \(x\) has \(C\setminus\{x\}\subseteq N_{G'}(x)=N_G(y)\), so \((C\setminus\{x\})\cup\{y\}\) is a clique of \(G\) of the same size (using \(x\notin C\setminus\{x\}\) and \(y \notin C\setminus\{x\}\) — the latter because \(N_G(y)\) does not contain \(y\)); if \(|C|=r+1\) this gives a \(K_{r+1}\) in \(G\), contradiction. B

Since \(G\) itself already has the maximum number of edges among \(K_{r+1}\)-free graphs on \([n]\), no application of Step 2 to \(G\) can strictly increase the edge count. Hence for every non-adjacent pair \(x,y\) in \(G\), \(\deg(x)=\deg(y)\), and moreover \(N_G(x)\setminus\{y\} = N_G(y)\setminus\{x\}\) (else the swap in Step 2, applied with the roles chosen so as not to decrease edges, would strictly increase them).

A maximiser is a fixed point of every edge-non-decreasing local move; if Step 2 produced strictly more edges for some non-adjacent pair with unequal neighbourhoods, that would contradict maximality of \(e(G)\) from Step 1. B

Define \(u \sim v\) for \(u\neq v\) to mean "\(u,v\) non-adjacent in \(G\)". Then \(\sim\) is transitive: if \(u\sim v\) and \(v \sim w\) with \(u \neq w\), then \(u \sim w\).

By Step 3, \(N_G(u)\setminus\{v\}=N_G(v)\setminus\{u\}\) and \(N_G(v)\setminus\{w\}=N_G(w)\setminus\{v\}\), so \(u\) and \(w\) have (up to the point \(v\) itself) identical neighbourhoods; in particular \(w \in N_G(u) \iff w\in N_G(v)\setminus\{u\}\cup\{u\text{-exception}\}\), and tracing through, if \(uw\) were an edge then \(w \in N_G(u)=N_G(v)\cup\{u\}\setminus\{v\}\) forces \(w=u\) or \(w\in N_G(v)\), the latter contradicting \(v\sim w\) (non-adjacency of \(v,w\)); hence \(uw\notin E(G)\), i.e. \(u \sim w\). C

\(\sim\) together with equality is an equivalence relation on \(V(G)\), so \(V(G)\) partitions into classes \(V_1,\dots,V_k\) that are pairwise completely non-adjacent internally, and \(G\) is the complete multipartite graph with parts \(V_1,\dots,V_k\): \(G = K_{|V_1|,\dots,|V_k|}\).

Reflexivity/symmetry of \(\sim\) are immediate from the definition (non-adjacency is symmetric; each class is by construction an independent set); Step 4 gives transitivity, so \(\sim\) is an equivalence relation. Two vertices in different classes are, by definition of the classes (maximal sets of mutually "chained" non-adjacency), adjacent — this is exactly the definition of a complete multipartite graph. B

The number of parts satisfies \(k \leq r\).

Choosing one vertex from each of \(k\) distinct parts of a complete multipartite graph yields a clique of size \(k\) (any two chosen vertices lie in different parts, hence are adjacent by definition of complete multipartite). If \(k\geq r+1\) this produces a \(K_{r+1}\) in \(G\), contradicting the hypothesis that \(G\) is \(K_{r+1}\)-free. A

For a complete multipartite graph with part sizes \(n_1,\dots,n_k\) (\(\sum n_i = n\)), \[ e(G) = \binom{n}{2} - \sum_{i=1}^{k} \binom{n_i}{2} = \frac{1}{2}\left(n^2 - \sum_{i=1}^k n_i^2\right). \]

The complement of a complete multipartite graph is exactly the disjoint union of cliques \(K_{n_1},\dots,K_{n_k}\) on the parts (all and only within-part pairs are non-edges); so \(e(G) = \binom n2 - e(\overline G) = \binom n2 - \sum_i \binom{n_i}2\), and expanding \(\binom{m}{2}=m(m-1)/2\) with \(\sum n_i=n\) gives the stated identity. A

Subject to \(\sum_{i=1}^{k} n_i = n\), \(n_i \geq 0\) integers, \(k\leq r\) parts (pad with zero parts up to exactly \(r\) parts if \(k \lt r\), which does not change \(\sum n_i^2\)), the quantity \(\sum_{i=1}^r n_i^2\) is minimised — uniquely up to permutation — when the \(n_i\) are as equal as possible: each \(n_i \in \{\lfloor n/r\rfloor, \lceil n/r\rceil\}\).

(Smoothing / balancing argument.) If some \(n_i - n_j \geq 2\), move one unit from part \(i\) to part \(j\): the new sum of squares changes by \((n_i-1)^2+(n_j+1)^2-n_i^2-n_j^2 = -2n_i+2n_j+2 = -2(n_i-n_j-1) \leq -2 \lt 0\), a strict decrease. So any minimiser must have all part sizes within \(1\) of each other, which (given \(\sum n_i=n\) fixed) forces the balanced partition, unique up to which parts get the extra \(+1\). B

Combining Steps 5–8: the extremal \(G\) equals \(T(n,r)\), the balanced complete \(r\)-partite graph, and \[ e(G) = \frac{n^2 - \sum n_i^2}{2} \leq \frac{n^2 - n^2/r}{2} = \left(1-\frac{1}{r}\right)\frac{n^2}{2}, \] with the middle inequality (\(\sum n_i^2 \geq n^2/r\) for any partition of \(n\) into \(r\) nonnegative parts) an instance of the Cauchy–Schwarz / power-mean inequality, tight exactly at the balanced partition.

Cauchy–Schwarz: \(\left(\sum_{i=1}^r n_i\right)^2 \leq r\sum_{i=1}^r n_i^2\), i.e. \(n^2 \leq r\sum n_i^2\), with equality iff all \(n_i\) are equal; combined with Step 8's integer-balancing this pins down \(T(n,r)\) as the unique maximiser among all \(K_{r+1}\)-free graphs on \([n]\), completing the proof of both the bound and the equality case. C t3

Result

\( G \text{ is } K_{r+1}\text{-free on } n \text{ vertices} \;\Longrightarrow\; e(G) \leq e(T(n,r)) \leq \left(1-\frac{1}{r}\right)\frac{n^2}{2}, \) with equality iff \(G \cong T(n,r)\)

Reading. Among all graphs on \(n\) vertices that avoid a clique of size \(r+1\), the one with the most edges is the balanced complete \(r\)-partite graph — split the vertices into \(r\) groups of nearly equal size and join every pair of vertices in different groups. No other \(K_{r+1}\)-free graph on \(n\) vertices has as many edges, and none ties it except by being literally the same graph.

Scope. Applies to any finite simple graph and any fixed integer \(r\geq1\); it is a statement about the single number \(e(G)\), giving no information about other graph parameters (chromatic number, diameter, etc.) beyond what is forced by edge count. It does not bound the number of \(K_{r+1}\)-free graphs, nor does it extend as stated to hypergraphs or to forbidding a graph other than a clique (that generalisation is the Erdős–Stone theorem, and for non-complete forbidden graphs the extremal number can have a different growth rate).

Corollaries & converses

Mantel's theorem is the case \(r=2\): every triangle-free graph on \(n\) vertices has at most \(\lfloor n^2/4\rfloor\) edges, attained uniquely by \(K_{\lceil n/2\rceil,\lfloor n/2\rfloor}\).
Chromatic lower bound. Since \(T(n,r)\) is \(r\)-colourable and \(K_{r+1}\)-free, and it is the unique edge-maximiser, any graph with more than \((1-1/r)n^2/2\) edges must contain \(K_{r+1}\); equivalently, edge-density above the Turán threshold forces a clique of the "expected" size for that density.
Integer/exact form. Writing \(n=qr+s\) with \(0\leq s\lt r\), the exact extremal count is \(e(T(n,r)) = \binom{n}{2} - s\binom{q+1}{2} - (r-s)\binom{q}{2} = \left\lfloor \left(1-\frac1r\right)\frac{n^2}{2} \right\rfloor\).
Converse direction (the theorem's own tightness). The bound is sharp for every \(n,r\): \(T(n,r)\) itself witnesses it, so the inequality cannot be improved for any fixed \((n,r)\) — there is no stronger universal bound.
Does NOT converse to "\(e(G) \leq (1-1/r)n^2/2 \Rightarrow G\) is \(K_{r+1}\)-free": e.g. \(K_{r+2}\) minus a perfect matching-type sparsification can have few edges while still containing \(K_{r+1}\); low edge count alone never certifies clique-freeness, only the reverse implication holds.

Fails without

Drop \(K_{r+1}\)-freeness: take \(G=K_n\) itself (which trivially contains every clique up to size \(n\)); then \(e(G)=\binom n2 = n(n-1)/2\), which exceeds \((1-1/r)n^2/2\) as soon as \(r \lt n-1\) — e.g. \(n=10,r=3\): \(\binom{10}{2}=45 \gt 33 = (1-1/3)\cdot100/2\). The bound simply does not hold for graphs that do contain \(K_{r+1}\).
Drop simplicity (allow multi-edges): take two vertices joined by \(N\) parallel edges, no other vertices/edges. This graph contains no \(K_3\) as a simple subgraph (there are only 2 vertices), yet has \(N\) edges for arbitrarily large \(N\), violating any bound of the form \(cn^2\) for fixed small \(n\).
Drop uniqueness of the extremizer's balance (use an arbitrary, non-balanced multipartite split): for \(n=9,r=3\), the unbalanced split \(K_{7,1,1}\) is \(K_4\)-free with \(7\cdot1+7\cdot1+1\cdot1=15\) edges, strictly less than \(e(T(9,3))=e(K_{3,3,3})=27\); dropping the balance requirement loses optimality even though \(K_{r+1}\)-freeness is preserved.

Common errors

Confusing "\(K_{r+1}\)-free" with "\(r\)-colourable" — every \(r\)-colourable graph is \(K_{r+1}\)-free, but the converse is false (odd cycles \(C_{2k+1}\) with \(k\geq2\) are \(K_4\)-free yet not 2- or even 3-colourable in general — actually \(C_5\) is \(K_3\)-free but needs 3 colours), so students wrongly assume the extremal graph's colourability is the whole content of the theorem rather than a byproduct.
Applying the formula with \(r\) meaning "clique number forbidden" instead of "one less than the clique forbidden": writing the bound for "\(K_r\)-free" graphs as \((1-1/r)n^2/2\) instead of \((1-1/(r-1))n^2/2\) — an off-by-one that inverts which Turán graph is extremal.
Forgetting the floor/integer correction: quoting \(e(T(n,r))=(1-1/r)n^2/2\) as exact when \(r \nmid n\); the true value is \(\lfloor (1-1/r)n^2/2\rfloor\) and can differ from the naive real-number formula.
Believing any complete multipartite graph with \(r\) parts is extremal, forgetting the balance condition of Step 8 — only the most-equal partition maximises edges among all \(K_{r+1}\)-free graphs.
Misapplying the theorem to non-simple or infinite graphs, or to hypergraphs, where no such clean extremal number is known (the analogous hypergraph Turán problem is a famous open area, e.g. the Turán density of \(K_4^{(3)}\) is unknown).

Discussion

Turán proved this result in 1941, reportedly while confined in a forced-labour camp during World War II, motivated by exactly the question in the theorem's title; his 1941 paper is usually credited as the starting point of extremal graph theory as a systematic discipline, though the special case \(r=2\) (Mantel's theorem) had been known since 1907. The proof given here, via Zykov's 1949 symmetrisation trick, is one of at least half a dozen genuinely different known proofs — others use induction on \(n\) removing a maximum clique, a weighted/Lagrangian argument (closely related to the Motzkin–Straus theorem relating clique number to the maximum of a quadratic form on the simplex), and a probabilistic deletion-and-permutation argument. The existence of so many structurally different proofs is itself notable: each generalises in a different direction, which is why the theorem sits at the root of so many later results.

The deepest generalisation is the Erdős–Stone theorem (1946), which shows that for any fixed graph \(H\) with chromatic number \(\chi(H)=r+1\), the extremal number for \(H\)-free graphs has the same leading-order growth as for \(K_{r+1}\)-free graphs: \(\mathrm{ex}(n,H) = \left(1-\frac1r\right)\frac{n^2}{2} + o(n^2)\). This says that, at the level of edge density, forbidding any non-bipartite graph is asymptotically "as restrictive as" forbidding the clique of the same chromatic number — a remarkable collapse of an infinite family of extremal problems onto Turán's clique answer. Only the lower-order term distinguishes different forbidden graphs of the same chromatic number, which is itself a rich area (e.g. forbidding \(C_5\) versus \(K_3\), both giving leading term \(n^2/4\)).

The Zykov symmetrisation argument used here is worth dwelling on because it is a "compactness by local moves" argument: rather than directly guessing the extremal graph, one shows any maximiser must be invariant under an edge-non-decreasing local perturbation, and invariance forces a rigid structural form (complete multipartite). This template — maximise a functional over a finite or compact space, then show any maximiser is a fixed point of a well-chosen improving move, then classify the fixed points — recurs throughout extremal combinatorics (e.g. in stability proofs, in flag algebra arguments, and in the proof of the Kruskal–Katona theorem via compressions).

Common misconception: that Turán's theorem says every dense graph contains the Turán graph \(T(n,r)\) as a subgraph. It does not — it says no \(K_{r+1}\)-free graph can have more edges than \(T(n,r)\) has. A graph can have many edges, avoid \(K_{r+1}\), and still fail to contain \(T(n,r)\) itself as a subgraph (subgraph containment of the whole extremal graph is a much stronger, generally false, statement).

Worked examples

Find the maximum number of edges in a \(K_4\)-free graph on \(n=10\) vertices, and exhibit an extremal graph.

Here "\(K_4\)-free" means \(K_{r+1}\)-free with \(r+1=4\), i.e. \(r=3\). A

Write \(n=10=3\cdot3+1\), so \(q=3,s=1\): \(T(10,3)\) has part sizes \(4,3,3\).

Balanced partition of \(10\) into \(3\) parts as in Step 8 of the proof: one part gets the extra vertex. A

\[ e(T(10,3)) = \binom{10}{2} - \binom{4}{2}-\binom{3}{2}-\binom{3}{2} = 45 - 6 - 3 - 3 = 33. \]

Direct application of the identity from Step 7 of the proof. A

Cross-check with the closed-form bound: \(\left(1-\frac13\right)\frac{10^2}{2} = \frac23\cdot50 = 33.\overline{3}\), and \(\lfloor 33.\overline3 \rfloor = 33\), matching.

Consistency check against the theorem's stated formula; here \(3\mid\) remainder so the floor is exactly attained without needing the refined \(s,q\) formula. A

\(\mathrm{ex}(10,K_4) = 33\), attained uniquely by \(K_{4,3,3}\)

Reading. Any graph on 10 vertices with 34 or more edges must contain a tetrahedron \(K_4\); no \(K_4\)-free graph on 10 vertices beats \(K_{4,3,3}\)'s 33 edges.

A network engineer wants to design a graph on \(n=101\) nodes with no clique of \(6\) mutually-linked nodes (\(K_6\)-free, so \(r+1=6\), \(r=5\)), maximising the number of links. Determine the maximum.

Direct instance of Turán's theorem with \(r=5\). A

\(101 = 20\cdot5+1\), so \(q=20,\, s=1\): \(T(101,5)\) has one part of size \(21\) and four parts of size \(20\).

Balanced partition as in Step 8 of the proof. A

\[ e(T(101,5)) = \binom{101}{2} - \binom{21}{2} - 4\binom{20}{2} = 5050 - 210 - 4(190) = 5050 - 210 - 760 = 4080. \]

Identity of Step 7, with one part of size \(21\) contributing \(\binom{21}{2}=210\) and each of the four size-\(20\) parts contributing \(\binom{20}{2}=190\). A

Cross-check: \(\left(1-\frac15\right)\frac{101^2}{2} = \frac45\cdot\frac{10201}{2} = \frac{4\cdot10201}{10} = 4080.4\), and \(\lfloor4080.4\rfloor=4080\), matching Step 3 exactly.

Confirms the exact integer computation agrees with the closed-form asymptotic bound after flooring. A

\(\mathrm{ex}(101,K_6) = 4080\), attained uniquely by the complete 5-partite graph with parts \(21,20,20,20,20\)

Reading. The engineer can build at most 4080 links while guaranteeing no group of 6 nodes is fully interconnected, and the unique optimal design groups the 101 nodes into 5 near-equal clusters, linking every pair of nodes in different clusters (and none within a cluster).

Problems

Compute \(\mathrm{ex}(7,K_3)\) (the maximum number of edges in a triangle-free graph on 7 vertices) and give an extremal graph.
Solution
Here \(r=2\), so we need \(T(7,2)\): balanced bipartition of 7 into 2 parts is \(4,3\). Then \(e(T(7,2)) = \binom72 - \binom42-\binom32 = 21-6-3=12\); equivalently, directly, \(e(K_{4,3})=4\cdot3=12\). Cross-check: \((1-\frac12)\frac{49}{2}=12.25\), floor \(=12\). So \(\mathrm{ex}(7,K_3)=12\), attained uniquely by \(K_{4,3}\).
Verify directly (without citing the theorem) that the Turán graph \(T(n,r)\) is \(K_{r+1}\)-free for every \(n,r\).
Solution
\(T(n,r)\) has \(r\) parts \(V_1,\dots,V_r\), and vertices within the same part are non-adjacent by construction (it is \(r\)-partite). Any set of \(r+1\) vertices, by pigeonhole, must place two vertices in the same part \(V_i\) (since there are only \(r\) parts). Those two vertices are non-adjacent, so the set of \(r+1\) vertices cannot be a clique. Hence \(T(n,r)\) contains no \(K_{r+1}\).
For \(n=12,r=3\), compute \(\sum n_i^2\) for the partitions \((6,3,3)\), \((5,4,3)\), and \((4,4,4)\), and confirm the balanced partition minimises it (equivalently maximises the edge count), matching Step 8 of the proof.
Solution
\((6,3,3)\): \(36+9+9=54\). \((5,4,3)\): \(25+16+9=50\). \((4,4,4)\): \(16+16+16=48\). Indeed \(48 \lt 50 \lt 54\), so the balanced partition \((4,4,4)\) minimises \(\sum n_i^2\), confirming that \(K_{4,4,4}\) (with \(e=\frac{144-48}{2}=48\) edges) beats \(K_{5,4,3}\) (\(e=\frac{144-50}{2}=47\)) and \(K_{6,3,3}\) (\(e=\frac{144-54}{2}=45\)).
Derive Mantel's theorem (\(\mathrm{ex}(n,K_3) = \lfloor n^2/4\rfloor\)) as a direct corollary of Turán's theorem.
Solution
Set \(r=2\) in Turán's theorem: a \(K_3\)-free graph on \(n\) vertices has at most \(\left(1-\frac12\right)\frac{n^2}{2} = \frac{n^2}{4}\) edges, i.e. at most \(\lfloor n^2/4\rfloor\) edges since edge counts are integers, with equality for the balanced complete bipartite graph \(T(n,2) = K_{\lceil n/2\rceil,\lfloor n/2\rfloor}\). This is exactly Mantel's 1907 theorem, recovered as the \(r=2\) instance.
Let \(G\) be a graph on \(n=15\) vertices with \(e(G)=76\) edges. Show that \(G\) must contain a \(K_5\), and identify the smallest \(r\) for which the hypothesis of Turán's theorem (with \(K_{r+1}\)-freeness) is violated by this edge count.
Solution
We test \(r=4\) (forbidding \(K_5\)): \(\mathrm{ex}(15,K_5)\) uses \(T(15,4)\), partition \(15=3\cdot4+3\), so parts \(4,4,4,3\). Then \(\sum n_i^2 = 16+16+16+9=57\), so \(e(T(15,4)) = \frac{225-57}{2}=84\). Since \(76 \le 84\), this particular edge count does not by itself force a \(K_5\) — G could still be \(K_5\)-free. So test \(r=3\) (forbidding \(K_4\)): \(T(15,3)\) has parts \(5,5,5\), \(\sum n_i^2=75\), \(e(T(15,3))=\frac{225-75}{2}=75\). Since \(e(G)=76 \gt 75 = \mathrm{ex}(15,K_4)\), \(G\) cannot be \(K_4\)-free — it must contain a \(K_4\) (not necessarily \(K_5\)). Correcting the claim: with only \(76\) edges we can only guarantee a \(K_4\), not a \(K_5\) (since \(76\le84=\mathrm{ex}(15,K_5)\) leaves room for a \(K_5\)-free example). The smallest \(r\) for which the \(K_{r+1}\)-free hypothesis is contradicted by \(e(G)=76\) is \(r=3\) (i.e. \(G\) is forced to contain \(K_4\), by Turán's theorem contrapositive: \(e(G) \gt \mathrm{ex}(n,K_{r+1}) \Rightarrow G\) contains \(K_{r+1}\)).