# $n$ vertex graph with more edges than its Turan number: $e(G) = t_r(n) + 1$

I have been struggling with this problem for quite some time now and I cannot think of a way to proceed with either part:

Suppose that G is a graph with $$n > r + 1$$ vertices and $$t_r(n) + 1$$ edges:

(a) Prove that for every $$p$$ with $$r + 1 < p <= n$$ there is a subgraph $$H$$ of $$G$$ with $$|H| = p$$ and $$e(H) \geq t_r(p) + 1$$.

(b) Prove that $$G$$ contains two copies of $$K_{r+1}$$ with exactly $$r$$ common vertices.

For part a), I have so far tried to use induction on $$n$$. For the base case with $$n = r+2$$ we have only $$H = G$$ and $$n = p$$ to check, which is clearly true. For the $$n$$th case I think we want to find a vertex $$v$$ in $$G$$ of degree $$\delta(T_r(n))$$, so that $$H = G-v$$ satisfies the induction hypothesis and gives all of the required subgraphs.

This is where I am stuck, I cannot seem to find anything close to this required vertex. As $$e(G) \geq t_r(n) + 1$$ we know $$K_{r+1} \leq G$$, so there is a vertex $$v$$ with $$d(v) \geq r$$, which is not enough as $$(q-1)r \leq \delta(T_r(v)) \leq qr-1$$.

Perhaps useful I thought would also be the fact that if $$|G| = n, e(G) = t_r(n), K_{r+1} \nleq G$$ then $$\delta(G) \leq \delta(T_r(v)) \leq \Delta(T_r(v)) \leq \Delta(G)$$, this would give us a large enough vertex to delete, but we need $$G$$ to not contain $$K_{r+1}$$.

Likewise I did not get very far in the second part of the question, apart from the fact that a $$K_{r+1}$$ would exist in G in that case, but I cannot see how to get a second copy.

I noticed that someone has asked this identical problem a few years ago, but unfortunately, that one does not have any responses - which is why I have posted again as I do not have enough reputation to start a bounty without losing some rights on this site.

a) We use induction on p. For a base case of $$p=n$$, we are given that such a subgraph exists (since the entire graph is itself a subgraph satisfying the required conditions). Now assume that such a subgraph, $$H$$, exists on $$l+1$$ vertices. We note the identity: $$t_r(l)=t_r(l+1)-\delta (T_r(l+1))$$.
What we are looking for is a vertex in the subgraph $$H$$ which we can remove so that $$H-v$$ is a subgraph of G on $$l$$ vertices with sufficiently many edges.
Of course, using the identity, if there does exist a vertex, $$v$$, of degree less than or equal to $$\delta (T_r(l+1))$$, then we can just remove this vertex, and $$H-v$$ has $$e(H-v)\geq t_r(l+1)+1-d(v)\geq t_r(l)+1$$.
Otherwise, if no such vertex exists, then all vertices have degree greater than this. Now consider removing any vertex from the graph. So there are $$l$$ vertices, each with degree greater than $$\delta (T_r(l+1))-1$$ (the -1 comes from the fact each vertex could be adjacent to the removed vertex), and $$\delta (T_r(l+1))-1=l+1-\lceil \frac{l+1}{r} \rceil -1 = l-\lceil \frac{l+1}{r} \rceil$$, therefore $$e(H-v) \geq \frac{l(l+1-\lceil \frac{l+1}{r} \rceil)}{2}$$, which we can use as an upper bound for $$t_r(l)+1$$ by thinking about the structure of $$T_r(n)$$ (although care is needed for all the cases).
b) Once we have part a) this part should be fairly simple. Apply the lemma for p=r+2, that is, we have that there is a subgraph of G, H, on r+2 vertices with at least $$t_r(r+2)+1$$ edges. Intuitively what we should be thinking about is the fact that for n 'not much larger' than r, $$T_r(n)$$ is 'nearly' a complete graph. In fact, $$T_r(r+2)$$ is a complete r-partite graph with r-2 parts of size 1, and 2 parts of size 2 (from the definition of $$T_r(n)$$, so it is only 2 edges short of $$K_{r+2}$$, those 2 edges being, for each of the parts of size 2, the edge inbetween the 2 vertices. Therefore our subgraph H is either $$K_{r+2}$$ or $$K_{r+2}-e$$ for any edge (since we have $$t_r(n)+1$$ edges in H). Clearly if $$H=K_{r+2}$$, taking any two distinct sets of r+1 vertices, they both form a copy $$K_{r+1}$$ with r common vertices. In the case $$H=K_{r+2}-e$$, let the two endvertices of e be in distinct subsets of r+1 vertices, and, since e is the only missing egde, the two subset of r+1 vertices form two copies of $$K_{r+1}$$ with r common vertices.
• There seems to be something wrong with the problem statement. In (a) it's assumed that $p\le n$ but if $p=n$ then $H$ is a subgraph of $G$ with $e(H)>t_r(n)+1=e(G)$. Please correct the problem statement (if needed) before going ahead with the proof.