5

Part of 2023 China Northern MO

Problems(1)

combo graph inequality problem, f^ 2(G)<= c x g^3(G)

Source: China Northern MO 2023 p5 CNMO

Given a finite graph

f^ 2(G)\le c \cdot g^3(G)

f(G)

be the number of triangles in graph

G

g(G)

be the number of edges in graph

G

, find the minimum constant

c

, so that for each graph

G

f^ 2(G)\le c \cdot g^3(G)

inequalitiescombinatoricsgraph theory