5
$\begingroup$

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.

$\endgroup$

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.