Proving Turan's Theorem with Weaker Theorem (Dual Version?)

Question

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

Answer 1

Notation: $e(G)$ is the number of edges of a graph $G$. $\overline{G}$ is the complement of $G$. $\omega(G)$ is the clique number of $G$.

Note that $T'(n,q) = \overline{T(n,q)}$, and $\omega(G) = \alpha(\overline{G})$.

$e(\overline{G}) = \binom{n}{2} - e(G) = e(T(n,q)) > e(T(n,q-1))$. By Turan's theorem, $\alpha(G) = \omega(\overline{G}) \geq (q-1)+1$.

---

Edit.

• Turan's theorem: If $e(G) > e(T(n,q-1))$, then $\omega(G) \geq q$.

It implies that

• Dual version of Turan's theorem: If $e(G) < e(T'(n,q-1))$, then $\alpha(G) \geq q$.

Of course, the dual version implies the original. However,

• Dual version what you wrote: If $e(G) \leq e(T'(n,q))$, then $\alpha(G) \geq q$.

I think it is quite weaker (as you said) to prove the original Turan's theorem since $e(T'(n,q)) < e(T'(n,q-1))$.

In addition, I think that you miss '$G$ minimizing its edges' in this sentence, "additionally, if $\alpha(G)=q$ then it must be that $G\cong T'(n,q)$."