Show that any graph with 6 points has a triangle or three points which are not joined to each other.
Solution
Take any point X. Suppose there are 3 points A, B, C joined to X. Then either two of A, B, C are joined, in which case they form a triangle with X, or none are in which case we have three points not joined to each other. So at most 2 points are joined to X. That means there are three points A', B', C' not joined to X. Either two of them are not joined, in which case they form three unjoined points with X, or they form a triangle.
© John Scholes
jscholes@kalva.demon.co.uk
29 Oct 2003
Last corrected/updated 29 Oct 03