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<i_r\leq n$. 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?
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.