# $K_{r+1}$-free graph with maximum number of edges contains $K_r$

If $$n>r$$ and $$G$$ be an $$n$$-vertex, $$K_{r+1}$$-free graph with the maximum number of edges. Then $$G$$ contains $$K_r$$.

I was reading the proof of Turan's theorem and the author uses the above fact. I do not think that it is obvious and I guess it is true due to maximality. So I have decided to prove it.

Proof: Suppose that $$G=(V(G),E(G))$$ is a $$K_r$$-free graph and let $$V(G)=\{v_1,\dots,v_n\}$$, where $$n\geq r+1$$. There exists $$k,\ell$$ such that $$v_{k}v_{\ell}\notin E(G)$$. Consider the new graph $$\widehat{G}=(V(G),E(G)\cup \{v_kv_{\ell}\})$$ and we see that $$e(\widehat{G})>e(G)$$.

I claim that $$\widehat{G}$$ is a $$K_{r+1}$$-free graph. If this is not true, then $$\{v_{i_1},\dots,v_{i_{r+1}}\}$$ is a clique of size $$r+1$$ in $$\widehat{G}$$ for some $$1\leq i_1<\dots. But it is not a clique in $$G$$, then $$\exists i,j$$ such that $$v_iv_j\notin E(G)$$. It immediately implies that $$v_iv_j=v_{k}v_{\ell}$$. Consider $$\{v_{i_1},\dots,v_{i_{r+1}}\}\setminus \{v_k\}$$ and it is a clique of size $$r$$ in $$\widehat{G}$$ but not in $$G$$. Hence $$\exists \alpha,\beta\neq k$$ such that $$v_{\alpha}v_{\beta}=v_{k}v_{\ell}$$. Hence $$(k=\alpha)\lor (k=\beta)$$ which is a contradiction.

Therefore, we were able to construct the new graph $$\widehat{G}$$ which is $$K_{r+1}$$-free such that it has more edges than $$G$$.

I was wondering is there a more intuitive explanation\proof of this fact?

• It's easier to use maximal (under the subgraph relation) than maximum (number of edges): if $G$ is a maximal $K_{r + 1}$-free graph and $e$ is a non-edge then $G \cup e$ has a $K_{r + 1}$. But $K_{r + 1} - e$ has a $K_r$ subgraph.
– JBL
Commented Jul 30, 2022 at 2:53
• @JBL, sorry but I did not get your point. I was wondering can you write it as a separate answer please? I'd appreciate it!
– RFZ
Commented Jul 30, 2022 at 4:07

As requested, expanding my comment to an answer:

Let $$G$$ be a maximal $$K_{r + 1}$$-free graph on $$V$$, meaning that $$G \cup e$$ contains $$K_{r + 1}$$ for every potential edge not already in $$G$$. (The maximum graphs you're after are all of this form, since otherwise you could add an edge, but there are more maximal ones that are not maximum.) Let's add a single edge to $$G$$, producing the graph $$G \cup e$$ that contains $$K_{r + 1}$$. Now consider that $$K_{r + 1}$$-subgraph. All but one of its edges belongs to $$G$$ (the exception is $$e$$). But $$K_{r + 1} - e$$ contains a $$K_r$$ subgraph. Therefore $$G$$ contains a $$K_r$$ subgraph.

• I read your answer and I see it is exactly the same what I wrote in my post (probably with fewer notations).
– RFZ
Commented Jul 30, 2022 at 17:45
• If you like. The intuitive idea is very simple (maximality + $K_{r + 1} - e$ contains $K_r$) so if you think you already had this idea (albeit obscured in a needless proof by contradiction) then I don't know what you feel you were missing.
– JBL
Commented Jul 30, 2022 at 19:54
• You are right! There is no need to use the proof by contradiction here.
– RFZ
Commented Aug 1, 2022 at 1:00
• By the way, thank you so much for your answer! I accepted it! +1
– RFZ
Commented Aug 1, 2022 at 14:46
• You're welcome, and thank you!
– JBL
Commented Aug 1, 2022 at 16:03