A graph has n > 2 points. Show that we can find two points A and B such that at least [n/2] - 1 of the remaining points are joined to either both or neither of A and B.
Solution
Consider the number of pairs (X, {Y, Z}), where X, Y, Z are distinct points such that X is joined to just one of Y, Z. If X is joined to just k points, then there are just k(n - 1 - k) ≤ (n - 1)2/4 such pairs (X, {Y, Z}). Hence in total there are at most n(n - 1)2/4 such pairs. But there are n(n - 1)/2 possible {Y, Z}. So we must be able to find one of them {A, B} which belongs to at most [ (n - 1)/2 ] such pairs. Hence there are at least n - 2 - [ (n - 1)/2 ] = [n/2] - 1 points X which are joined to both of A and B or to neither of A and B. [If confused by the [ ], consider n = 2m and n = 2m+1 separately! ]
© John Scholes
jscholes@kalva.demon.co.uk
26 Aug 2002