B1.5

Combinatorics | Part II, 2003

Let GG be a graph of order n4n \geqslant 4. Prove that if GG has t2(n)+1t_{2}(n)+1 edges then it contains two triangles with a common edge. Here, t2(n)=n2/4t_{2}(n)=\left\lfloor n^{2} / 4\right\rfloor is the Turán number.

Suppose instead that GG has exactly one triangle. Show that GG has at most t2(n1)+2t_{2}(n-1)+2 edges, and that this number can be attained.

Typos? Please submit corrections to this page on GitHub.