(1) Every graph with $n\ge3$ vertices and more than $\frac{n^2}{4}$ edges contains a triangle.

(2) For every even $n$ there exists a graph with $n$ vertices and $\frac{n^2}{4}$ edges that doesn't contain a triangle.

I know this is a well-known theorem by Turan, but I can't understand the proof there.

  • 2
    $\begingroup$ If you have a particular proof that you do not understand, it may be useful for you to reproduce the proof and note what parts you are having difficulty understanding. $\endgroup$ – Aaron Jan 31 '18 at 11:55
  • $\begingroup$ This smells like the pigeonhole principle from $200$ miles away. $\endgroup$ – Arnaud Mortier Jan 31 '18 at 13:25

Well (2) is easy: Say the vertices are the union of two disjoint sets $V_1$ and $V_2$, each with $n/2$ elements, and add edges $(v,w)$ for every $v\in V_1$ and $w\in V_2$.

A hint for (1): If $S$ is a set containing exactly three vertices let $E_S$ be the set of all edges from one vertex in $S$ to another vertex in $S$. You need to show that some $E_S$ contains three edges.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.