IMO 2004 SL C8

Origin: POL | Category: Combinatorics

Problem

For a finite graph G, let f(G) be the number of triangles and g(G) the number of tetrahedra formed by edges of G. Find the least constant c such that g(G)3 \leqc \cdot f(G)4 for every graph G.

Solution

Denote by V1, . . . , Vn the vertices of a graph G and by E the set of its edges. For each i = 1, . . . , n, let Ai be the set of vertices connected to Vi by an edge, Gi the subgraph of G whose set of vertices is Ai, and Ei the set of edges of Gi. Also, let vi, ei, and ti = f(Gi) be the numbers of vertices, edges, and triangles in Gi respectively.

The numbers of tetrahedra and triangles one of whose vertices is Vi are respectively equal to ti and ei. Hence n  i=1 vi = 2|E|, n  i=1 ei = 3f(G) and n  i=1 ti = 4g(G). Since ei \leqvi(vi −1)/2 \leqv2 i /2 and ei \leq|E|, we obtain e2 i \leqv2 i |E|/2, i.e., ei \leqvi

|E|/2. Summing over all i yields 3f(G) \leq2|E|

|E|/2, or equivalently f(G)2 \leq2|E|3/9. Since this relation holds for each graph Gi, it follows that ti = f(Gi) = f(Gi)1/3f(Gi)2/3 \leq 2 1/3 f(G)1/3ei. Summing the last inequality for i = 1, . . . , n gives us 4g(G) \leq3 2 1/3 f(G)1/3 \cdot f(G), i.e. g(G)3 \leq3 32f(G)4. The constant c = 3/32 is the best possible. Indeed, in a complete graph Cn it holds that g(Kn)3/f(Kn)4 =
n 3
n −4 \to 32 as n \to\infty. Remark. Let Nk be the number of complete k-subgraphs in a finite graph G. Continuing inductively, one can prove that N k k+1 \leq k! (k+1)k N k+1 k .