Extremal graph theory

Choose a fixed sample size

m

for which the normalized Turan theorem bound lies below the given density by a positive margin. The expected edge count in a random

m

-vertex subset then forces a positive proportion of subsets to contain a forbidden-size clique. Each clique belongs to a known number of subsets, so double counting gives a positive constant times

n^{r + 1}

cliques.

Extremal number ( $ex (n, H)$ )

The extremal number

ex (n, H)

is the largest number of edges in an

n

-vertex graph containing no subgraph isomorphic to

H

Extremal graph for disjoint cliques

For fixed positive integers

r, s

and sufficiently large

n

, the unique extremal graph forbidding

s

vertex-disjoint copies of the complete graph

K_{r + 1}

is the join of graphs

K_{s - 1} + T_{r} (n - s + 1)

, up to isomorphic graphs. Each forbidden clique would require a distinct vertex of

K_{s - 1}

Monotonicity of the normalized extremal number

For every fixed graph

H

, the sequence

\frac{ex ( n , H )}{( 2 n )}

is nonincreasing once

n \geq 2

. Indeed, choose a uniformly random

m

-vertex induced subgraph of an extremal

H

-free graph on

n

vertices. It remains

H

-free and has expected edge count

ex (n, H) \frac{( 2 m )}{( 2 n )},

which cannot exceed

ex (m, H)

Mantel theorem ( $ex (n, K_{3}) = ⌊ n^{2} /4 ⌋$ )

The complete bipartite graph

K_{3, 3}

has vertex sets

A = {a_{1}, a_{2}, a_{3}}

and

B = {b_{1}, b_{2}, b_{3}}

, with every edge between

A

and

B

and none inside either part. Its six vertices support

3 \cdot 3 = 9

edges and no triangles in a graph: among any three vertices, two belong to the same independent set and have no joining edge.

Figure 1.
The sharp nine-edge triangle-free graph $K_{3, 3}$ and the three triangles in a graph created by adding $a_{1} a_{2}$
. **Details**.

Add the single edge

a_{1} a_{2}

. Each

b_{j}

is a common neighbour of its endpoints, producing the triangle in a graph

a_{1} a_{2} b_{j}

. These are exactly the three new triangles in a graph, because every triangle in a graph must use the only edge inside a part. The new count is ten edges; nine was the last possible count without a triangle in a graph on six vertices.

In general, every simple graph with a finite set of

n \geq 0

vertices that is triangle-free has at most

m \leq ⌊ \frac{n ^{2}}{4} ⌋

edges. This is the

r = 2

case of Turán's theorem, with forbidden clique

K_{3}

. Equality holds exactly for the balanced complete bipartite graph

K_{⌊ n /2 ⌋, ⌈ n /2 ⌉}

, up to graph isomorphism; empty parts are allowed for

n < 2

The floor function gives the exact integer bound. Splitting

n

vertices into two independent sets of sizes

a

and

n - a

, and putting in every cross edge, gives

a (n - a) = \frac{n ^{2}}{4} - (a - \frac{n}{2})^{2} .

The count is largest when

a

is an integer nearest

n /2

. For

n = 2 k

it is

k^{2}

; for

n = 2 k + 1

it is

k (k + 1)

. Both equal

⌊ n^{2} /4 ⌋

. This proves attainability for every

n

, including the empty graph.

A short proof of the upper bound uses degrees of vertices. In a triangle-free graph, the endpoints

u, v

of an edge have disjoint vertex neighbourhoods: a common neighbour would complete a triangle in a graph. Thus

d (u) + d (v) \leq n

. Summing over edges counts

d (v)

once for each of the

d (v)

edges incident to

v

, giving

\sum_{v \in V} d (v)^{2} = \sum_{uv \in E} (d (u) + d (v)) \leq nm .

(3)

For

n > 0

, the Cauchy-Schwarz inequality and handshaking lemma yield

4 m^{2} = (\sum_{v \in V} d (v))^{2} \leq n \sum_{v \in V} d (v)^{2} \leq n^{2} m .

(4)

m > 0

, division gives

m \leq n^{2} /4

;

m = 0

is immediate. Since

m

is an integer, apply the floor function. The case

n = 0

is immediate too. This proves the bound; the full equality characterization follows from Turán's theorem.

The useful reversal is that more than

⌊ n^{2} /4 ⌋

edges force a triangle in a graph, whatever their placement. A global count certifies a local pattern. The extremizer is bipartite, but a triangle-free graph need not be bipartite: a five-vertex graph cycle has five edges, below the bound of six. Historically, Willem Mantel posed the triangle-exclusion question in 1907.^[ref]

Triangle lower bound one edge above the Mantel threshold

Every graph on

2 n

vertices with at least

n^{2} + 1

edges contains at least

n

triangles. An induction deletes the endpoints of an edge lying in no triangle; if every edge lies in a triangle, the edge-triangle incidence bound is already sufficient.

Turán's theorem ( $ex (n, K_{r + 1}) = t_{r} (n)$ )

 1  0

How many edges can we retain while excluding a prescribed clique? For integers

r \geq 1

and

n \geq 0

, every simple graph on

n

vertices containing no complete subgraph

K_{r + 1}

satisfies

e (G) \leq t_{r} (n) := e (T_{r} (n)) .

Equality holds exactly for the Turán graph

T_{r} (n)

, up to graph isomorphism. Thus the extremal number is

ex (n, K_{r + 1}) = t_{r} (n)

For example,

T_{3} (8)

has independent sets of sizes

3, 3, 2

and

21

edges, as counted in Turán graph. It contains triangles in a graph, but no four-vertex clique. Consequently any simple graph on eight vertices with

22

edges contains

K_{4}

, while

21

edges alone do not force one. Excluding larger cliques permits denser graphs; Mantel theorem is precisely the first nontrivial case.

A short proof outline uses Zykov symmetrization. If an extremizer is not a complete multipartite graph, it has vertices

x, y, z

with

x y, x z

absent and

yz

present. If either

y

z

has larger vertex degree than

x

, clone that vertex in place of

x

. Otherwise replace both

y, z

by nonadjacent clones of

x

, gaining

2 d (x) - d (y) - d (z) + 1 > 0

edges. Both contradict extremality; balancing the resulting at most

r

parts gives

T_{r} (n)

The vertex cloning in a graph step preserves clique exclusion because any clique using a clone can substitute its original vertex; nonadjacent clones cannot occur together in a clique. At most

r

parts can be nonempty, since selecting one vertex from each gives a clique. If fewer than

r

parts are nonempty and one has at least two vertices, splitting it creates more edges, so it cannot be extremal. For

r = 1

the bound is zero. For

r \geq n

, the Turán graph is

K_{n}

, and the bound is the total

(2 n)

possible edges.

Edit-distance stability for clique-free graphs ( $e (G) \geq t_{r} (n) - k ⟹ ∣ E (G) △ E (H) ∣ \leq 3 k$ )

A clique-free graph near the Turan theorem edge bound is close to a complete multipartite graph. Choose a maximum-degree vertex, split its neighbourhood from the remaining vertices, and apply induction inside the neighbourhood. The degree bound implies that missing cross edges are at least twice the number of edges inside the remaining class. This inequality controls all three types of edits and gives the constant three.

Bipartite stability from few odd cycles ( $∣ E (G) △ E (H) ∣ \leq 11 ϵ (2 n)$ )

Fix an odd cycle length. If the graph has edge density at least

1/2 - ϵ

and sufficiently few copies of that cycle, odd-cycle copies from positive triangle density forces few triangles in a graph. The triangle removal lemma deletes at most

ϵ (2 n)

edges, after which the clique-free edit bound applies with two parts. Absorbing its linear rounding error into the density margin gives the displayed bound for large order.

Turán graph ( $T_{r} (n)$ )

 1  0

The Turán graph

T_{r} (n)

is a complete multipartite graph with

r

independent sets of sizes differing by at most one, with every cross edge present. Empty parts are allowed when

r > n

Figure 1.
The Turán graph $T_{3} (8)$ has three independent sets of sizes $3, 3, 2$ , giving $21$ edges and no four-vertex clique
. **Details**.

In this example, the independent sets are

A = {a_{1}, a_{2}, a_{3}}

B = {b_{1}, b_{2}, b_{3}}

and

C = {c_{1}, c_{2}}

. Count the edges between each pair of parts:

t_{3} (8) = 3 \cdot 3 + 3 \cdot 2 + 3 \cdot 2 = 9 + 6 + 6 = 21.

Any four vertices put at least two in the same independent set, by the pigeonhole principle, so they cannot form

K_{4}

. Conversely, every choice of one vertex from each part is a triangle in a graph, giving

3 \cdot 3 \cdot 2 = 18

triangles in a graph. Clique exclusion here does not mean triangle-free.

For the exact count, Euclidean division writes

n = r q + s

, where

q = ⌊ n / r ⌋

uses the floor function and

s = n mod r

is the remainder, with

0 \leq s < r

. There are

s

parts of size

q + 1

and

r - s

of size

q

. For any part sizes

a_{1}, \dots, a_{r}

summing to

n

, count cross edges by expanding the square:

e (K_{a_{1}, \dots, a_{r}}) = \sum_{i < j} a_{i} a_{j} = \frac{1}{2} (n^{2} - \sum_{i = 1}^{r} a_{i}^{2}) .

Therefore

t_{r} (n) = \frac{1}{2} [n^{2} - s (q + 1)^{2} - (r - s) q^{2}] = (1 - \frac{1}{r}) \frac{n ^{2}}{2} - \frac{s ( r - s )}{2 r} .

(3)

For

n = 8, r = 3

, we have

q = 2, s = 2

, giving

(64 - 2 \cdot 9 - 1 \cdot 4) /2 = 21

. The Quadratic Turan edge bound gives

64/3

instead: the exact correction subtracts

1/3

Balancing is an integer optimization with a simple reason. If two part sizes satisfy

a \geq b + 2

, moving one vertex from the larger part to the smaller decreases their contribution to the sum of squares by

a^{2} + b^{2} - (a - 1)^{2} - (b + 1)^{2} = 2 (a - b - 1) > 0,

(4)

so it increases the edge count by

a - b - 1

. For eight vertices, parts

4, 2, 2

give

20

edges; moving one vertex produces

3, 3, 2

and

21

edges. The most symmetric permitted sizes pack the most cross edges, which explains the sharp construction in Turán's theorem.

Triangle support line between bipartite and tripartite Turan graphs

For

n \geq 3

, put

e_{i} = e (T_{i} (n))

t_{3} = k_{3} (T_{3} (n))

, and

c_{n} = (e_{3} - e_{2}) / t_{3}

. Every graph on

n

vertices satisfies

e (G) - c_{n} k_{3} (G) \leq e_{2} .

Thus an edge count

e_{2} + θ (e_{3} - e_{2})

forces at least

θ t_{3}

triangles in a graph. This is an exact finite bound, with the rounding in the Turán graph retained. To prove it, use edge-triangle symmetrization. The inequality

c_{n} \geq 2/ n

allows merging the two smallest classes when there are at least four classes. With three classes, fixing the middle class makes the objective affine in the product of the other two sizes; either merge them or balance them. Only

T_{2} (n)

and

T_{3} (n)

need remain.

Zykov symmetrization

Zykov symmetrization replaces one of two nonadjacent vertices by a clone of the other. Cloning the vertex of larger degree does not decrease the edge count and does not create a larger clique. Iteration reduces the extremal problem for clique-free graphs to complete multipartite graphs.

Edge-triangle symmetrization

For each real

c

, some maximizer of

e (G) - c k_{3} (G)

among graphs on

n

vertices is complete multipartite graph. Among maximizers maximize

\sum_{v} d (v)^{2}

. Cloning either of two nonadjacent vertices preserves the objective, since maximality forces their local contributions

d (v) - ce (G [N (v)])

to agree. If their vertex neighbourhoods differ, the sum of the two changes in the squared-degree of a vertex objective is twice the size of their symmetric difference, a contradiction. Nonadjacency therefore partitions the vertices into classes with identical vertex neighbourhoods.

Quadratic Turan edge bound

Every

n

-vertex graph containing no

K_{r + 1}

satisfies

e (G) \leq (1 - \frac{1}{r}) \frac{n ^{2}}{2} .

Rhombus-free edge bound

A graph-theoretic rhombus is two triangles sharing an edge. Every rhombus-free graph on

n \geq 4

vertices has at most

e (T_{2} (n)) = ⌊ \frac{n ^{2}}{4} ⌋

edges. If the graph is triangle-free this is Turán's theorem. Otherwise remove a triangle: every remaining vertex has at most one neighbor in it, and induction bounds the edge count by

⌊(n - 3)^{2} /4 ⌋ + n \leq ⌊ n^{2} /4 ⌋

Triangular prism graph

The triangular prism has six vertices and nine edges. Each edge lies in at most one triangle, so it has no rhombus; its two triangles show that it is not

K_{3, 3} = T_{2} (6)

This is the prism graph built from two triangles.

Erdős-Stone theorem

 1  0

For every graph

H

with chromatic number

r + 1

ex (n, H) = (1 - \frac{1}{r} + o (1)) (2 n) .

Logarithmic Erdős-Stone theorem ( $t \geq ⌊ d (r, ϵ) lo g n ⌋$ )

An edge density exceeding the Turan theorem threshold for

K_{r + 1}

by a fixed positive amount forces a balanced

K_{r + 1} (t)

subgraph with logarithmic part size. Combine clique supersaturation by sampling with the dense clique family blow-up lemma. Dense binomial random graphs show that the logarithmic order is optimal for a uniform density guarantee.

Logarithmic clique blow-up from minimum degree ( $δ (G) \geq (1 - 1/ r + ε) n ⟹ K_{r + 1} (⌊ d lo g n ⌋) \subseteq G$ )

A fixed positive excess over the Turan theorem threshold forces logarithmic balanced complete multipartite graphs. There is an elementary induction using common neighbourhood from bipartite density: first obtain a logarithmic

r

-partite subgraph from the induction hypothesis, and select disjoint transversal

r

-cliques in it. Each such clique has at least

r ε n

common neighbours, by the union bound on non-neighbour sets. Apply the bipartite common-neighbour count to these cliques as left-side objects. Their selected union and a large common neighbourhood form the extra part.

Random obstruction to larger clique blow-ups ( $E # K_{s} (t) \leq n^{s t} p^{(2 s) t^{2}}$ )

In a binomial random graph with fixed edge probability below one, the displayed first-moment bound tends to zero for

t = C lo g n

and sufficiently large fixed

C

. At the same time the edge density concentrates near

p

. Thus a positive fixed density cannot force balanced complete multipartite subgraphs whose part size grows faster than logarithmically.

High-minimum-degree multipartite stability subgraph

For fixed positive integers

r, t

, a graph

G

n

vertices with

e (G) = (1 - 1/ r + o (1)) n^{2} /2

and no balanced complete multipartite blow-up

K_{r + 1} (t)

contains an

r

-partite subgraph

H

with

n - o (n)

vertices, balanced classes of size

n / r + o (n)

, and minimum degree of a graph

δ (H) = (1 - 1/ r + o (1)) n

One proof first removes a vanishing fraction of vertices of low degree of a vertex, finds a slowly growing

K_{r} (L)

by the Erdős-Stone theorem, and assigns almost every remaining vertex to a root class in which it has fewer than

t

neighbours of a vertex. After discarding a further vanishing fraction, a

K_{t, t}

inside an assigned class would extend to

K_{r + 1} (t)

using the root classes. Thus internal edges and missing cross-class edges both number

o (n^{2})

. Removing the vertices with unusually many missing cross-class edges gives the stated minimum degree of a graph.

Minimum degree of an extremal forbidden-subgraph graph

If a fixed graph

F

has chromatic number

r + 1

, every extremal

F

-free graph

G

n

vertices has minimum degree of a graph

(1 - 1/ r + o (1)) n

. Use a high-minimum-degree multipartite stability subgraph

H

: replacing any vertex by one adjacent to all but one class of

H

preserves

F

-freeness. Any supposed new copy of

F

can replace the new vertex by an unused common neighbour in the omitted class. Extremality therefore gives the lower bound on every degree of a vertex; the Erdős-Stone theorem gives the upper bound on the average degree of a vertex.

Kővári–Sós–Turán theorem

For each fixed positive integer

t

ex (n, K_{t, t}) = O (n^{2 - 1/ t}) .

The standard proof counts

t

-element subsets of graph neighbourhoods in a bipartite subgraph. If one side has degrees

d_{y}

, the absence of

K_{t, t}

gives

\sum_{y} (t d _{y}) \leq (t - 1) (t n) .