# Problem on graphs with more edge than a Turan number

I ran into the following problem when revising for a Graph Theory exam - I had already solved part c) however I am keeping it in as it seems to link to part d). Now I see these type of problems on Turan graphs quite frequently, however, I have always struggled with problems such as these where it involves graphs with more edges than its Turan number.

The Turan number $$t_r(n)$$ represents the maximum number of edges a graph with $$n$$ vertices can have and not contain a copy of $$K_{r+1}$$. So in this case having $$t_2(n) + 2$$ edges would then contain at least a triangle. However, I am not sure how this would link together with subgraphs of size 5 or 7 - perhaps 5/7 vertices come from removing a vertex from a graph described in the previous part?

I'd be grateful if anyone could give any pointers on the general techniques / things to try when facing these problems.

We use a similar proof structure here akin to the induction proof of Turan's theorem. We use induction on $$|G|$$, the number of vertices.

Base case, $$n=5:$$ Suppose $$e(G) = t_2(5) + 2 = 8$$. We just take subgraph $$H \leq G$$ with $$H = G$$ so $$|H| = 5, e(H) = e(G) = t_2(5) + 2$$

Inductive case: suppose true up to $$|G| < n$$, then for $$|G| = n$$:

Claim: $$G$$ has a subgraph $$K'$$ such that $$\delta(K') \leq \delta(T_2(n))$$, i.e. the min. degree of $$K'$$ is smaller than the min. degree of $$T_2(n)$$.

Proof of claim: Taking contrapositive of the last part of part c), we have that if $$e(K') \leq t_2(n) + 2$$ then $$\delta(K') \leq \delta(T_2(n))$$. Since $$e(G) \geq t_2(n)+2$$ it does indeed has a subgraph $$K'$$ with $$e(K') = t_2(n) + 2$$. So the lemma applies and $$\delta(K') \leq \delta(T_2(n))$$ as required.

By the claim, then, $$K'$$ has a vertex $$v$$ with $$d(v) = \delta(K') \leq \delta(T_2(n))$$. For $$K = K'-v$$ we have that $$K \leq K' \leq G$$, so $$K$$ is a subgraph of $$G$$ and:

$$e(K) = e(K') - d(v) \geq (t_2(n) + 2) - \delta(T_2(n)) = t_2(n-1) + 2$$ (last step by property of Turan graphs: $$t_r(n) - \delta(T_r(n) = t_r(n-1)$$).

Here the $$IH$$ applies on $$K$$ and $$K$$ has a subgraph $$H$$ with our desired properties, thus $$H \leq K \leq G$$ and $$H$$ is also a subgraph of $$G$$. As required.