MathDB

two triangles with a common edge [variation on Turan]

Source: China TST 1987, problem 6

May 16, 2005

inductioncombinatorics unsolvedcombinatorics

Problem Statement

Let

G

be a simple graph with

2 \cdot n

vertices and

n^{2}+1

edges. Show that this graph

G

contains a

K_{4}-\text{one edge}

, that is, two triangles with a common edge.