Extremal Graph Theory

Tristan Shin

4 Jan 2020

If you have any questions/comments or find any mistakes, please contact me at shint@mit.edu.
This handout is linked at web.mit.edu/shint/www/handouts/ExtremalGraphTheory.pdf.

Contents
1 Introduction 2

2 Avoiding cliques 3
2.1 Mantel’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Turán’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Remarks on Turán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3 Avoiding general subgraphs 7

3.1 Remarks on extremal numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 8

4 Avoiding bipartite graphs 8

4.1 Lower-bounding ex(n, Ks,t ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.2 Avoiding sparse bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . 11

5 Concluding remarks 14

1
Extremal Graph Theory Tristan Shin

1 Introduction

Extremal graph theory is a rich branch of combinatorics which deals with how general
properties of a graph (eg. number of vertices and edges) controls the local structure of the
graph.

Other parts of graph theory including regularity and pseudorandomness are built upon
extremal graph theory and can be extended into the world of additive combinatorics.
Compare, for example, the following two statements:

Theorem: Mantel
1 n
Every graph on n vertices with edge density greater than 2
· n−1
contains a triangle.

Theorem: Roth
Every subset of N with density greater than 0 contains a 3-term arithmetic progression.

These theorems are samples of extremal graph theory and additive combinatorics, respec-
tively, and have similar-looking statements.

In this handout, we will examine some key results in extremal graph theory. The main
question we will look at is:

Given a positive integer n and graph H, what is the maximum possible number of
edges in a graph on n vertices with no copies of H (such a graph is called H-free)?

Here is a slightly different question in the same spirit:

Question. Given a positive integer n, what is the maximum number of edges in a graph on
n vertices with no cycles?

Instead of looking at H-free graphs for a specific H, we are looking for cycle-free graphs in
general.

We know by definition that a cycle-free graph is a forest. This has some number of connected
components, each of which has one less edge than number of vertices. Convince yourself that
the number of edges is maximized when our forest is in fact a tree, so the answer is n − 1.

This is perhaps the simplest example of an “extremal graph theory question.” In the next
few sections, we look at similar and more advanced questions.

2
Extremal Graph Theory Tristan Shin

2 Avoiding cliques

An important question with applications in many other parts of math is how to avoid cliques.

2.1 Mantel’s theorem

The first result in this manner is Mantel’s Theorem.

Theorem 2.1: Mantel (1907)

2
Any triangle-free graph on n vertices has at most b n4 c edges.

Proof. Let G be a triangle-free graph with n vertices.

Observation. For any edge uv, u and v have no common neighbors. Thus (deg u − 1) +
(deg v − 1) ≤ n − 2.

u v
Figure 1: A common neighbor would imply the existence of a triangle.

So X
deg u + deg v ≤ e(G)n.
uv∈E

But the sum counts deg v for each neighbor u of v, for a total of deg v times. Thus
X X
deg u + deg v = (deg v)2 .
uv∈E v∈V

Combining these and using Cauchy-Schwarz,

! ! !2
X X X X
e(G)n2 ≥ n deg u + deg v = 1 (deg v)2 ≥ deg v = (2e(G))2
uv∈E v∈V v∈V v∈V

n2
by the Handshake Lemma. Thus e(G) ≤ 4
. 

This proof is straightforward and elegant, but it doesn’t provide an immediate equality
case (though one can work through the conditions to deduce it). The main reason for this is
because the proof’s main part is algebraic, revealing little about the graph theoretic structure
of an equality case. Here is a “better” proof:

3
Extremal Graph Theory Tristan Shin

Proof. Let A ⊆ V be a maximum independent set1 .

Observation. The neighborhood of any vertex is independent. Thus deg v ≤ |A|.

v
Figure 2: Two neighbors being adjacent would imply the existence of a triangle.

Consider the complement B = V \ A of A. Every edge must have a vertex in B because A

is independent. Thus
2
n2

X |A| + |B|
e(G) ≤ deg v ≤ |A||B| ≤ =
v∈B
2 4

by AM-GM. 

If we try analyzing the equality case now, we get:

• |A| = |B| from AM-GM

X
• e(G) = deg v implies no edge is from B to B, so all edges are between A and B
v∈B

• deg v = |A| for all v ∈ B

Together, these conditions immediately imply that equality only occurs at the complete
bipartite graph T n2 , n2 .

Figure 3: The triangle-free graph on 8 vertices with maximal number of edges.

Remark. If n is odd, the same argument with a bit more work implies that the edge count
2 2
is maximized at T n−1 , n+1 with n 4−1 = b n4 c edges.
2 2

Remark. That is not to discount the first proof, however. In addition to being quite
straightforward, we can modify the proof a bit to deduce the following result:
1
An independent set is a set of vertices with no edges between them.

4
Extremal Graph Theory Tristan Shin

Fact 2.2
4m n2
A graph with n vertices and m edges has at least 3n
(m − 4
) triangles.

2.2 Turán’s theorem

Motivated by Mantel’s theorem, one might guess that the maximum number of edges in a
graph with no Kr+1 would be an “equitable complete r-partite graph.” We first provide
some definitions to formalize what we mean.

Definition. An k-partite graph is one whose vertex set V can be partitioned into sets
V1 t · · · t Vk such that every edge has vertices in different parts. A complete k-partite
graph Ks1 ,...,sk is the graph on s1 + · · · + sk vertices formed by partitioning the vertices into
sets Vi with |Vi | = si and creating edges between every pair of vertices in different parts.

Remark. For the same reasons as before, a graph G is k-partite if and only if χ(G) ≤ k.

If the sets have roughly the same size, the partition is called equitable. These graphs have
a name:

Definition. The Turán graph Tn,r is the complete r-partite graph Ks1 ,...,sr with s1 + · · · +
sr = n and each si being either b nr c or d nr e.

Example 2.1
We have T8,3 = K2,3,3 and T15,5 = K3,3,3,3,3 .

Figure 4: The Turán graph T8,3 .

As we have hypothesized, the Turán graphs give the most edges in a Kr+1 -free graph:

Theorem 2.3: Turán (1941)

2
Any Kr+1 -free graph on n vertices has at most e(Tn,r ) ≤ (1 − 1r ) n2 edges.

Proof. We proceed by strong induction on n. If n ≤ r, then Tn,r = K1,...,1 = Kn . Now

assume that n > r and that the theorem holds for all graphs with less than n vertices. Let

5
Extremal Graph Theory Tristan Shin

G be a Kr+1 -free graph with n vertices, and let us assume G has the maximal number of
edges. This implies that G has a copy of Kr — if not, then we can add an edge without
creating Kr+1 , contradicting maximality. Let A be a set of vertices that form a Kr , and look
at its complement B = V \ A.

Observation. Every vertex v ∈ B has at most r − 1 neighbors in A.

Thus
   
|A| r
e(G) ≤ + (r − 1)|B| + e(B) ≤ + (r − 1)(n − r) + e(Tn−r,r ) ≤ e(Tn,r ). 
2 2

Notice how this proof examined a specific substructure of the graph, removed it, and con-
tinues after this reduction. This is an example of a local approach. Proofs that use local
methods often employ induction to repeatedly remove substructures.

Contrast this with our global proofs of Mantel’s theorem which (mostly) looked at the graph
as a whole and used inequalities in that form. But noticeably, the local approach provides
more graph theoretical information. Our first proof of Mantel was almost entirely global
and algebraic and told us little information. The second proof was less global (looks at
one substructure and distinguishes it, but uses this information directly) and provided good
information on the equality case and the underlying graph structure. And finally, our proof
of Turán directly gives us the equality case by induction.

2.3 Remarks on Turán

As we might expect, Kr+1 -free graphs that are close to the Turán bound are nearly r-partite.

Theorem 2.4: Erdős-Simonovits (1991)

Every Kr+1 -free graph on n vertices with at least e(Tn,r ) − k edges can be made r-
partite by removing at most k edges.

The triangle case is not too hard and follows from ideas above, but the theorem is trickier
to prove for general cliques.

If we have passed the Turán bound, we might get many copies of the clique. As an example,
adding one edge to Tn,2 produces b n2 c triangles. In fact, this is true as long as we have the
correct edge count, regardless of the structure of the graph.

Theorem 2.5: Rademacher (1941)

2
Every graph on n vertices and b n4 c + 1 edges contains at least b n2 c triangles.

6
Extremal Graph Theory Tristan Shin

This can be proven by induction on n by deleting either a single vertex with small degree or
two vertices with combined small degree.

3 Avoiding general subgraphs

A natural question to ask is what happens if we try to forbid other subgraphs besides cliques.

Definition. Given a positive integer n and graph H, define the extremal number of H
(on graphs with n vertices), denoted ex(n, H), to be the maximum possible number of edges
in a H-free graph on n vertices.

We will generally only care about the asymptotics of ex(n, H) as n grows large. So Turán
states that   
1 n
ex(n, Kr+1 ) = e(Tn,r ) = 1 − + o(1) .
r 2
Now, suppose that the chromatic number χ(H) = r + 1 for some graph H. Then Tn,r is
H-free — since χ(Tn,r ) = r, we can r-color Tn,r , and if H is a subgraph of Tn,r then this
induces an r-coloring of H too. Thus
  
1 n
ex(n, H) ≥ e(Tn,r ) = 1 − + o(1) .
r 2
One might think that we can do better, because we wastefully tack on extra edges to avoid.
But in fact, this is the best asymptotic.

Theorem 3.1: Erdős-Stone-Simonovits (1946)

  
1 n
ex(n, H) = 1 − + o(1)
χ(H) − 1 2

There are many proofs of this theorem (for example by a graph counting lemma derived by
Szemerédi’s graph regularity lemma), but all are either quite long or quite advanced so we
will black-box the result here.

Remark. Erdős-Stone-Simonovits can be written as

ex(n, H) 1
lim n

=1− .
n→∞
2
χ(H) − 1
This can be interpreted as the statement that asymptotically, the maximum possible edge
1
density in graphs that avoid H is 1 − χ(H)−1 .

This result is quite surprising. For example, consider the Petersen graph with chromatic
number 3. The threshold of edge density to mandate a certain subgraph is the same for
triangles as it is for such a complicated graph as the Petersen graph.

7
Extremal Graph Theory Tristan Shin

Figure 5: The complicated Petersen graph, with chromatic number 3.

3.1 Remarks on extremal numbers

As before, if we have passed the extremal bound, we will get many copies of the graph. This
idea is known as supersaturation.

Theorem 3.2: Erdős-Simonovits (1983)

For all graphs H and real numbers  > 0, there exists a constant c >
0 such that for
all sufficiently large n ∈ N, every graph with at least ex(n, H) +  n2 edges contains
n


at least c |V (H)| copies of H.

4 Avoiding bipartite graphs

The Erdős-Stone-Simonovits resolves the question of (asymptotically) determining ex(n, H)

for many graphs H, but says nothing about bipartite graphs H. Indeed, if χ(H) = 2 then
the result is that ex(n, H) = o(n2 ), which is very imprecise. What is the correct asymptotic
order of ex(n, H)?

Before we start, we state an easy result which will allow us to compare the extremal numbers
of related graphs.

Lemma 4.1
If H1 is a subgraph of H2 , then ex(n, H1 ) ≤ ex(n, H2 ).

Proof. Suppose this is false. Let G be an H1 -free graph on n vertices with maximal number
of edges. Then e(G) = ex(n, H1 ) > ex(n, H2 ), so G has a copy of H2 . But H1 is a subgraph
of H2 , so G has a copy of H1 , contradiction. 

We can start our analysis by tackling complete bipartite graphs. That is the subject of the
Zarankiewicz problem, which asks for precise asymptotic orders of ex(n, Ks,t ) for s ≤ t.
This problem is still open, but many levels of progress have been made.

8
Extremal Graph Theory Tristan Shin

Theorem 4.2: Kővári-Sós-Turán (1954)

1
ex(n, Ks,t ) = O(n2− s )

Proof. Let G be a Ks,t -free graph with n vertices and m edges.

First, assume that all vertices in G have degree at least s − 1. We will count the number of
K1,s , e.g. if s = 4, in G.

First, for any set A of s vertices, count the number of K1,s which use A as the part of size
s. There is one for each common neighbor of A. But A has less than t common neighbors,
otherwise A and t of their common neighbors form a Ks,t . So there are at most t − 1 of these
s
K1,s implying #K1,s ≤ ns (t − 1) ≤ n (t−1)


s!
.

Now, for each vertex v, count the number of K1,s which
use v as the part of size 1. There is
one for each set of s neighbors of v for a total of degs v . Thus

n( 2m − s + 1)s
X deg v  1 P   
n
deg v 2m/n n
#K1,s = ≥n =n ≥
v∈V
s s s s!

by convexity2 and the Handshake Lemma.

Combining these two bounds gives

1 1 1 1 1
m ≤ (t − 1) s n2− s + (s − 1)n = O(n2− s ).
2 2
Now, assume that G has vertices of degree less than s − 1. Consider the graph G0 formed
by adding arbitrary edges to each vertex v with deg v < s − 1 until deg v = s − 1. The new
1
graph G0 is Ks,t -free (how could a Ks,t be formed?) so it satisfies e(G0 ) = O(n2− s ) from the
previous work. Since e(G) ≤ e(G0 ), we are done. 

Remark. Because every bipartite graph is a subgraph of a complete bipartite graph, Kővári-
Sós-Turán gives an upper bound on ex(n, H) for every bipartite graph H.

This has implications in areas besides graph theory. For example, here is a geometric appli-
cation.

Fact 4.3
3
Given n points in the plane, at most 2n 2 pairs are distance 1 apart.

Proof. The graph on the points with edges indicating unit distance is K2,3 -free because
circles only intersect twice. So apply the bound obtained in Kővári-Sós-Turán. 
2 x

x(x−1)···(x−s+1)
The function s = s! is convex for x ≥ s − 1.

9
Extremal Graph Theory Tristan Shin

Figure 6: The unit distance graph is K2,3 -free.

3 3
Kővári-Sós-Turán actually gives the upper bound of √1 n 2 + 12 n = ( √12 + o(1))n 2 . The best
2
4
known upper bound, due to Spencer-Szemerédi-Trotter (1984), is O(n 3 ). For reference, the
current best lower bound (i.e. an upper bound cannot be improved past this point), due to
−1
Erdős (1946), is n1+Ω((log log n) ) .

4.1 Lower-bounding ex(n, Ks,t )

It is believed that the bound in Kővári-Sós-Turán is tight.

Conjecture 4.1: KST Conjecture

1
ex(n, Ks,t ) = Θ(n2− s )

This is proven for some values of s, t but still open for most cases where t is not too much
bigger than s.

Theorem 4.4: Erdős-Rényi-Sós (1966)

 
1 3
ex(n, K2,2 ) ≥ − o(1) n 2
2

√ √
Proof. Let p = (1 − o(1)) n be a prime in the interval [x − x0.525 , x] for x = n (possible
due to a result of Baker-Harman-Pintz in 2001). Construct the graph G on n vertices with
p2 − 1 vertices labeled with coordinates (a, b) for a, b = 0, 1, . . . , p − 1 except for (0, 0), as well
as n − p2 + 1 other vertices. Put an edge between (a, b) and (x, y) if ax + by ≡ 1 (mod p)
(the n − p2 + 1 other vertices have degree 0). If (x, y) is a common neighbor of (a, b) and
(c, d), then

ax + by ≡ 1 (mod p)
cx + dy ≡ 1 (mod p)

which has at most one solution for (x, y)3 . So G is K2,2 free. But each vertex with a
3
If there are multiple, then the linear map (x, y) → (ax + by, cx + dy) in F2p is not injective so its image is
a one-dimensional subspace of F2p . This subspace must be when both coordinates are equal, so (a, b) = (c, d).

10
Extremal Graph Theory Tristan Shin

coordinate has degree at least p − 14 , so

   
1X 1 1 1 3
e(G) = deg v ≥ (p2 − 1)(p − 1) = 3
− o(1) p = − o(1) n 2 . 
2 v∈V 2 2 2

Theorem 4.5: Brown (1966)

 
1 5
ex(n, K3,3 ) ≥ − o(1) n 3
2

The proof is similar to that of Erdős-Rényi-Sós but with more details and is omitted here.

These theorems imply that the KST conjecture is true for s = 2, 3. But what about s ≥ 4?

It turns out that the KST conjecture for K4,4 is still open. But we have results for all t ≥ f (s)
for some function f .

Theorem 4.6: Alon-Kollár-Rónyai-Szabó (1996)

1
ex(n, Ks,t ) = Θ(n2− s ) if t ≥ (s − 1)! + 1

The proof of this theorem uses a graph formed by the norm map of the finite field Fps ; this
graph provides a construction implying the desired lower bound5 .

4.2 Avoiding sparse bipartite graphs

Kővári-Sós-Turán provides an upper bound on ex(n, H) for every bipartite graph H, but the
bound is quite wasteful for bipartite H that are not close to complete. For example, trees
are far from complete.

First, let us get a lower bound on the extremal numbers of trees. If we consider the graph
n
with k−1 connected components, each of which is a copy of Kk−1 , then there is no copy of T
where T is a tree on k vertices. This graph has k−2
2
n edges. Thus ex(n, T ) ≥ k−22
n.

Theorem 4.7

ex(n, T ) ≤ (k − 2)n − 1

4
It should have degree p by counting solutions to ax + by ≡ 1 (mod p), but sometimes (x, y) = (a, b) is a
solution (corresponding to a self-loop) so we might need to subtract one.
5
This method actually only works for t ≥ s! + 1 but can be modified to prove the theorem by using a
projective norm map on Fps−1 × F× p instead.

11
Extremal Graph Theory Tristan Shin

We first prove a lemma.

Lemma 4.8
Every graph G contains a subgraph with minimum degree more than half of the average
degree of G.

Figure 7: The colored subgraph has the desired property.

Proof. Let t = |Ve(G)

(G)|
be half the average degree of G (by the Handshake Lemma). Define
a sequence of graphs as follows: Let G0 = G. If Gi is empty (no vertices) or has minimum
degree more than t, stop. Otherwise, remove a vertex of minimal degree from Gi (and all its
edges) and call the new graph Gi+1 . The average degree of Gi+1 is at least that of Gi .

If we stop at an empty graph, then we stop at G|V (G)| because Gi has |V (G)| − i vertices.
At each step, we remove at most t edges, with the last step removing no edges (because a
graph on 1 vertex has no edges). So we remove at most (|V (G)| − 1)t edges, but there are
|V (G)|t edges, contradiction. Thus we stop at a non-empty graph.

So the graph that we stopped at has minimum degree more than t as desired. 

Now we prove the inequality on trees.

Proof. Let G be a graph with at least (k − 2)n edges. By the lemma, G has a subgraph
H with minimal degree more than k − 2, so every vertex in H has degree at least k − 1. It
suffices to show that H has a copy of T .

Root the tree T and let v1 , . . . , vk be a topological sort of T . Choose any vertex u1 of H. For
i = 2, . . . , k, do the following recursion: Let vj be the parent of vi , with j < i. If j = 1, then
deg uj ≥ k − 1 > i − 2 so there is some child c of u1 that is not in {u2 , . . . , ui−1 }. Otherwise
j > 1 so vj has a parent vj 0 and deg uj − 1 ≥ k − 2 > i − 3 so there is some child c of uj that
is not in {u1 , . . . , ui−1 } \ {uj , uj 0 }. Either way, set ui to be the vertex c.

Thus we have embedded T into H, which is embedded into G, so G has a copy of T . 

So ex(n, T ) = Θ(n). In fact, the lower bound is correct, but the proof is long and is omitted
here.

12
Extremal Graph Theory Tristan Shin

Theorem 4.9: Ajtai-Komlós-Simonovits-Szemerédi (2015)

k−2
ex(n, T ) = n + o(1)
2

Another example of a sparse bipartite graph is the even cycle C2k .

Theorem 4.10: Bondy-Simonovits (1974)

1
ex(n, C2k ) = O(n1+ k )

This proof is quite advanced and is omitted here.

Once again, it is still an open problem if Bondy-Simonovits is the correct asymptotic. We

1
know that ex(n, C2k ) = Θ(n1+ k ) for k = 2, 3, 5 but not for any other values of k.

13
Extremal Graph Theory Tristan Shin

5 Concluding remarks

Throughout this handout, we examined several results about forbidding certain patterns in
graphs. More generally, we consider a property and ask how big we can make our objects
before these objects are forced to have the property.

As we saw in the intro, this is similar in nature to some questions asked in additive combi-
natorics. When attempting to prove Roth’s theorem by converting the setting to a graph, a
natural question to ask might be: What is the maximum number of edges in a triangle-free
graph on n vertices? Mantel’s theorem answers this. However, it does not imply the bound
we want in Roth’s theorem.

Instead, the correct question to ask is: What is the maximum number of edges in a graph
on n vertices where every edge is in a unique triangle? Using Szemerédi’s graph regularity
lemma, one can show that the answer is o(n2 ). This in turn implies Roth’s theorem.

The natural generalization of Roth’s theorem is true, for roughly the same reasons.

Theorem 5.1: Szemerédi (1975)

Every subset of N with positive upper density contains arbitrarily long arithmetic
progressions.

What is surprising, though, is a recent celebrated result of Green-Tao.

Theorem 5.2: Green-Tao (2008)

The prime numbers contain arbitrarily long arithmetic progressions.

The proofs of these theorems combine intuition from extremal graph theory, methods from
regularity, and careful understanding of the graph theoretical structure behind these prop-
erties to prove some of the simplest statements in additive combinatorics.

If you want to learn more about these vast fields mentioned, their connections, and more, I
encourage you to check out Yufei Zhao’s subject on Graph Theory and Additive Combina-
torics, available on MIT OpenCourseWare (as taught in Fall 2019).

14