A graph has 1982 points. Given any four points, there is at least one joined to the other three. What is the smallest number of points which are joined to 1981 points?
Solution
Answer: 1979.
Suppose there were 4 points not joined to 1981 points. Let one of them be A. Take a point B not joined to A. Now if X and Y are any two other points, X and Y must be joined, because otherwise none of the points A, B, X, Y could be joined to the other 3. There must be two other points C and D not joined to 1981 points. We have just shown that C must be joined to every point except possibly A and B. So it must be not joined to one of those. Similarly D. But now none of A, B, C, D is joined to the other 3. Contradiction. So there cannot be 4 points not joined to 1981 points. But there can be 3. Just take the graph to have all edges except AB and AC.
© John Scholes
jscholes@kalva.demon.co.uk
11 May 2002