Suppose that G is a graph with $\displaystyle n>r+1$ vertices and $\displaystyle t_r(n)+1$ edges. Prove that G contains two copies of $\displaystyle K_{r+1}$ with exactly r common vertices.

Printable View

- Oct 30th 2010, 02:38 AMNewtonianPuzzle based on Turan's Theorem
Suppose that G is a graph with $\displaystyle n>r+1$ vertices and $\displaystyle t_r(n)+1$ edges. Prove that G contains two copies of $\displaystyle K_{r+1}$ with exactly r common vertices.