MathDB

Write

t(G)

for the number of complete quadrilaterals in the graph

G

and

e_G(S)

for the number of edges spanned by a subset

S

of vertices of

G

. Let

G_1, G_2

be two (simple) graphs on a common underlying set

V

of vertices,

|V|-n

, and assume that

|e_{G_1}(S)-e_{G_2}(S)|<\frac{n^2}{1000}

holds for any subset

S\subseteq V

. Prove that

|t(G_1)-t(G_2)|\le \frac{n^4}{1000}

Problem Statement