Proving Turan's Theorem (Dual Version) and its Implications for $ex(n, K_{p+1})$

[joypav]

I have already proved that for a graph $G$ with $n$ vertices and $|E(T'(n,q))|$ edges, $\alpha (G) \geq q$. Additionally, if $\alpha (G) = q$ then it must be that $G \cong T'(n,q)$.

Apparently this is the "dual version" of Turan's Theorem. How does this theorem imply Turan's?

That $ex(n, K_{p+1}) = |E(T(n,p))|$

Where:

- $T'(n,q)$ : $q$ disjoint cliques with size as equal as possible
- $\alpha (G)$ : independence number of $G$
- $ex(n, K_{p+1})$ : max number of edges in an n-vertex graph with no $K_{p+1}$ subgraph

 

[joypav]

For completeness, here is the proof I wrote.
I'm not sure it is correct! May be some mistakes in the details.

Known Theorem:
Define $T'(n,q)$ to be q disjoint cliques with sizes of vertex sets as equal as possible. Let G be a graph with n vertices and $|E(T'(n,q))|$ edges. Then,
$$\alpha (G) \geq q$$
and if $\alpha (G) = q$ then $G \cong T'(n,q)$.To prove Turan's theorem, it suffices to show that if $|E(G)|>|E(T(n,p))|$ then $\omega (G) \geq p+1$, (where $\omega (G)$ is the size of the largest clique in G).\\
Assume $|E(G)|>|E(T(n,p))|$ then $|E(\overline{G})| \leq |E(T'(n,p))|$. By the in class proof, $\alpha (\overline{G}) \geq p+1$.
Notice that $\omega(G) = \alpha(\overline{G})$. Then we have, $\omega(G) = \alpha(\overline{G}) \geq p+1$, completing the proof.