Let $G$ be a graph with $ n > r+1 $ vertices and $t_r(n) + 1$ edges, where $t_r(n)$ is the Turan number i.e. the number of edges of the Turan graph $T_r(n)$. I'm trying to prove the following:

  • For every $p$ where $ r+1 < p \leq n$, there is a subgraph $H$ of $G$ such that $|H| = p$ and $e(H) \geq t_r(p) + 1$.
  • $G$ contains two copies of $K_{r+1}$ with exactly $r$ common vertices.

I'm afraid I'm not seeing how to get very far on either problem, though. For the first part, I'm attempting to proceed by downward induction on $p$: in the case $p = n$, we can take $H = G$. Assume the result holds for some $p+1$, then letting $H'$ be a subgraph of $G$ with $p+1$ vertices and $e(H') \geq t_r(p+1) + 1$, I would like to delete a vertex $v$ from $H'$ which has degree $\delta(T_r(p+1))$. Then $H = H' - v$ has $e(H) \geq t_r(p+1) - \delta(T_r(p+1)) + 1 = t_r(p) + 1$. But how do we know that such a vertex exists in $H'$?

For the second part, I know that since $G$ has more than $t_r(n)$ edges, it must have a copy of $K_{r+1}$, but I can't see how to produce a second copy of $K_{r+1}$ with $r$ vertices in common.

Any help is greatly appreciated.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.