Subscribe to the weekly news from TrueShelf

0

Turan graphs

Prove the following :

  • Let \(G\) be a simple graph with \(n\) vertices. If \(G\) has more than \(\lfloor \frac{n^2}{4} \rfloor\) edges, then \(G\) contains a triangle.

  • Let \(G\) be a simple graph with \(n\) vertices, such that \(G\) contains no \(K_{r+1}\). Prove that the number of edges in \(G\) is at most

\(\left(\frac{r-1}{r}\right)\frac{n^2}{2}\)

Related Content