MathDB

Here

G_{n}

denotes a simple undirected graph with

n

vertices,

K_{n}

denotes the complete graph with

n

vertices,

K_{n,m}

the complete bipartite graph whose components have

m

and

n

vertices, and

C_{n}

a circuit with

n

vertices. The number of edges in the graph

G_{n}

is denoted

e(G_{n})

. If

n \geq 5

and

e(G_{n}) \geq \frac{n^{2}}{4}+2

, prove that

G_{n}

contains two triangles that share exactly one vertex.

Problem Statement