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.


1 Answer 1


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.

  • $\begingroup$ 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. $\endgroup$
    – bof
    Dec 30, 2020 at 22:54
  • $\begingroup$ @bof you are right, the inequality in the problem statement should not be a strict inequality - I should have fixed that now! $\endgroup$
    – user1598
    Jan 4, 2021 at 20:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .