Subscribe to the weekly news from TrueShelf

## 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}$

0

0

0

0

0

0

0

0

0

0