A graph has 1991 points and every point has degree at least 1593. Show that there are six points, each of which is joined to the others. Is 1593 the best possible?
Answer
Yes.
Solution
Take any two points A and B which are joined. Each is joined to at least 1592 other points, so at least 2·1592 - 1989 = 1195 points are joined to both A and B. Take one such, C. Each of A, B, C is joined to at least 1591 other points, so at least 3·1591 - 2·1988 = 797 other points are joined to all of A, B and C. Take one such, D. Similarly, at least 4·1590 - 3·1987 = 399 points are joined to all of A, B, C, D. Take one such, E. At least 5·1589 - 4·1986 = 1 point is joined to all of A, B, C, D, E. Suppose it is F. Then each of A, B, C, D, E, F is joined to the others.
To show that 1593 is best possible, take 1991 points labeled 1, 2, ... , 1991 and join m and n iff m and n are incongruent mod 5. There are 398 points congruent to each of 0, 2, 3, 4 mod 5 and 399 congruent to 1 mod 5. So every point is joined to 4·398 = 1592 or 3·398 + 399 = 1593 other points. But any six points must include two with the same residue mod 5 which are therefore not joined.
© John Scholes
jscholes@kalva.demon.co.uk
1 Jan 2003
Last corrected/updated 1 Jan 03