Complete subgraphs and Turán's theorem

We've seen the maximum size of a graph containing no path of a certain length. What is the maximum size of a graph containing no $K_r$?

Definition 6..7 ($r$-partite graph)  

An $r$-partite graph is a graph with a vertex partition $V_1,\ldots,V_r$ so that each $V_i$ is an independent set (i.e. $G[V_i]$ is empty of edges).

Certainly no $(r-1)$-partite graph contains $K_r$.

What is the maximum size of a $(r-1)$-partite graph? Clearly we should look at a complete $(r-1)$-partite graph, where any pair of vertices in different classes are joined.

Suppose two class orders differ by more than 1, $\vert V_i\vert \ge \vert V_j\vert + 2$. Moving a vertex from $V_i$ to $V_j$ increases the number of edges by $\vert V_i\vert - \vert V_j\vert - 1 \ge 1$. Therefore the classes are as equal as possible.

Definition 6..8 (Turán graph, $T_r$ and $t_r$)  

The Turán graph $T_r(n)$ is the complete $r$-partite graph of order $n$ with classes orders $\lfloor \frac{n}{r} \rfloor$ or $\lceil \frac{n}{r} \rceil$.

We write $t_r(n) = e(T_r(n))$.

Theorem 6..9 (Turán's theorem; maximum sized graph not containing $K_r$)  

Let $G$ be a $K_r$ free graph of order $n$ with $e(G) \ge t_{r-1}(n)$ then $G$ = $T_{r-1}(n)$.

Proof. The vertices in $T_r(n)$ with least degree belong to vertex class of greatest order, by removing one of these we get $T_r(n-1)$.

$$t_{r-1}(n) - \delta(T_{r-1}(n)) = t_{r-1}(n-1)$$ (6.1)

Furthermore the degrees are as equal as possible.

$$\Delta(T_{r-1}(n)) - \delta(T_{r-1}(n)) \le 1$$ (6.2)

By induction on $n$. True for $n \le r - 1$, because $T_{r-1}(n)$ is $K_n$ for $n \le r - 1$.

In general let $G' \subset G$ be a spanning subgraph with $t_{r-1}$ edges. Certainly $G'$ is also $K_r$ free. Now apply the handshaking lemma to $G'$

$$n\delta(G') \le 2e(G')$$

$$= 2 t_{r-1}$$

$$\le \delta(T_{r-1}(n)) + (n-1)\Delta(T_{r-1}(n))$$

Using 6.2

$$\le n\delta(T_{r-1}(n)) + n - 1$$

$$\delta(G') \le \delta(T_{r-1}(n))$$

Pick $v \in V(G')$ a vertex of minimum degree. Then $G' - v$ is again $K_r$-free.

$$e(G'-v) = e(G') - \delta(G')$$

$$= t_{r-1}(n-1)$$

by 6.1.

So by the induction hypothesis, $G' - v$ is a complete $(r-1)$-partite graph. In $G'$, $v$ cannot be joined to all vertex classes in $G' - v$, since otherwise $G'$ would contain $K_r$. So $G'$ is $(r-1)$-partite. But $e(G') = t_{r-1}(n)$ and $T_{r-1}(n)$ is the only $(r-1)$-partite graph of that size, so $G' = T_{r-1}(n)$.

Adding any new edge to $T_{r-1}(n)$ creates a $K_r$, so $G = G' = T_{r-1}(n)$.

$\qedsymbol$

Theorem 6..10 (Turán's theorem; alternative forumulation and proof)  

Let $G$ be a $K_r$-free graph with vertex set $V$. Then there exists a $(r-1)$-partite graph $H$ with vertex set $V$, and $d_H(v) \ge d_G(v)$ for all $v \in V$.

Proof. By induction on $r$.

Case $r = 2$ trivial.

In general, we pick $x$ a vertex of $G$ of maximum degree.

Let $G' = G[\Gamma(x)]$. Then $G'$ is $K_{r-1}$ free. Let $V' = \Gamma(x)$.

By induction, there is a $(r-2)$-partite graph $H'$ with vertex set $V'$ and $d_{H'}(v) \ge d_{G'}(v)$ $\forall v \in V'$. Form $H$ by joining every vertex in $V \setminus V'$ to $H'$.

Now construct $H$ by joining every vertex in $V \setminus V'$ to $H'$. Then $H$ is $(r-1)$-partite. Need to show $d_H(v) \ge d_G(v)$ for all $v \in V$.

If $v \in V \setminus V'$, $d_H(v) = \left\Vert V'\right\Vert = d_G(x)$. But $d_G(x) \ge d_G(v)$ $\forall v \in V$.

Otherwise, $v \in V'$. $d_H(v) = \left\Vert V \setminus V'\right\Vert + d_{H'}(v)$. But $d_{H'}(v) \ge d_{G'}(v)$. Now $d_{G}(v) \le d_{G'}(v) + \left\Vert V \setminus V'\right\Vert$, so $d_H(v) \ge d_G(v)$. Done.

$\qedsymbol$

Lemma 6..11 (Alternative formulation of Turán's theorem implies original)  

Let $G$ be a $K_r$ free graph of order $n$ with $e(G) \ge t_{r-1}(n)$ then $G$ = $T_{r-1}(n)$.

Proof. Only remains to show $e(G) \le t_{r-1}(n)$, as certainly $T_{r-1}(n)$ is the unique $(r-1)$-partite graph of size $t_{r-1}(n)$. By previous theorem there exists a $(r-1)$-partite graph $H$ with vertex set $V(G)$, and $d_H(v) \ge d_G(v)$ for all $v \in V(G)$.

$e(G) = \frac{1}{2} \sum_{v\in V}(d_G(v) \le \frac{1}{2} \sum_{v \in V} d_H(v) = e(H)$. Now certainly $H$ is $(r-1)$-partite, and $t_{r-1}(n)$ is the maximum number of edges of an $(r-1)$-partite graph. So $e(G) = e(H) \le t_{r-1}(n)$.

$\qedsymbol$

Lemma 6..12 (Variant on the alternative formulation of Turán's theorem)  

Let $G$ be a graph of order $n$, and let $x \in V(G)$ of degree $d = \Delta(G)$. If $e(G[\Gamma(x)]) \le t_{r-2}(d)$, then $e(G) \le t_{r-1}(n)$.

Proof. Let $V' = \Gamma(x)$. Let $H'$ be a copy of $T_{r-2}(d)$ with vertex set $V'$. Form an $(r-1)$-partite graph $H$ by joining every vertex in $V \setminus V'$ to $H'$. Certainly $e(H) \le t_{r-1}(n)$.

Now $e(H) - e(H') \ge e(G) - e(G[V'])$, so if $e(G[V']) \le e(H')$ then $e(G) \le e(H) \le t_{r-1}(n)$.

$\qedsymbol$

Corollary 6..13 (Variant on alternative formulation of Turán's theorem)  

If $G$ has order $n$ and size $e(G) > t_{r-1}(n)$, then $G$ contains $K_r$ as a subgraph.

Proof. By induction on $r$. Case $r = 2$ is trivial.

In general we take a vertex $x \in V(G)$ with degree $d = \Delta(G)$. By the last lemma $e(G[\Gamma(x)]) > t_{r-2}(d)$ as $e(G) > t_{r-1}(n)$. By induction, $G[\Gamma(x)]$ contains $K_{r-1}$, so $G$ contains $K_r$.

$\qedsymbol$

Observation 6..14 (Method for finding $K_r$ in a graph)  

This corollary gives us an algorithm for finding $K_r$ in a graph that has more edges than $t_{r-1}(\left\Vert G\right\Vert)$. Take vertex $x_r$ of degree $\Delta(G)$. Let $G_r = G[\Gamma(x_r)]$. Given $x_n, G_n$ with $n > 1$, take $G_{n-1}$ to be $G_n[\Gamma_{G_n}(x_n)]$ and $x_{n-1}$ to be a vertex of highest degree in $G_n$.

By the lemma, $G_n$, $n > 1$ contains $K_{n-1}$. Therefore $G[x_1,\cdots,x_r] \cong K_r$.