
#1
February 11th, 2020,
22:41
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 nvertex graph with no $K_{p+1}$ subgraph

February 11th, 2020 22:41
# ADS
Circuit advertisement

#2
February 19th, 2020,
11:02
Thread Author
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.