1st APMO 1989

Show that a graph with n vertices and k edges has at least k(4k - n²)/3n triangles.

Solution

Label the points 1, 2, ... , n and let point i have degree d_i (no. of edges). Then if i and j are joined they have at least d_i + d_j - 2 other edges between them, and these edges join them to n - 2 other points. So there must be at least d_i + d_j - n triangles which have i and j as two vertices. Hence the total number of triangles must be at least ∑_{edges ij} (d_i + d_j - n)/3. But ∑_{edges ij} (d_i + d_j) = ∑ d_i², because each point i occurs in just d_i terms. Thus the total number of triangles is at least (∑ d_i²)/3 - nk/3. But ∑ d_i² ≥ (∑ d_i) ²/n (a special case of Chebyshev's inequality) = 4k²/n. Hence result.

1st APMO 1989

© John Scholes
jscholes@kalva.demon.co.uk
11 Apr 2002