A graph with n points and k edges has no triangles. Show that it has a point P such that there are at most k(1 - 4k/n2) edges between points not joined to P (by an edge).
Solution
Given a point P, the edges of the graph can be divided into three categories: (1) edges PQ, (2) edges QQ', where Q is joined to P, and (3) edges Q'Q", where Q' and Q" are not joined to P. Note that if Q is joined to P and there is an edge QQ', then Q' cannot be joined to P, or PQQ' would be a triangle. So the total number of edges in categories (1) and (2) is ∑' deg Q, where ∑' indicates that the sum is taken over points Q which are joined to P (by an edge). Thus the total number of edges in category (3) is k - ∑' deg Q. So we have to show that for some P, ∑' deg Q ≥ 4k2/n2.
The total for all points P is ∑P∑' deg Q. If we invert the order of the summations, this becomes ∑ deg2Q, where the sum is over all points Q. Now by Cauchy, (∑ deg Q)2 ≤ (∑ 12)(∑ deg2Q) = n ∑ deg2Q. But ∑ deg Q = 2k, so ∑ deg2Q ≥ 4k2/n and hence ∑P∑' deg Q ≥ 4k2/n. But if a sum of n terms is at least 4k2/n, then at least one for the terms must be at least 4k2/n2. In other words, there is a point P such that ∑' deg Q ≥ 4k2/n2, as required.
© John Scholes
jscholes@kalva.demon.co.uk
11 May 2002