MathDB

Let

G

is a graph and

x

is a vertex of

G

. Define the transformation

\varphi_{x}

over

G

as deleting all incident edges with respect of

x

and drawing the edges

xy

such that

y\in G

and

y

is not connected with

x

with edge in the beginning of the transformation. A graph

H

is called

G-

attainable if there exists a sequece of such transformations which transforms

G

H.

Let

n\in\mathbb{N}

and

4|n.

Prove that for each graph

G

with

4n

vertices and

n

edges there exists

G-

attainable graph with at least

9n^{2}/4

triangles.

Problem Statement