Given 7 points in the plane, how many segments (each joining two points) are needed so that given any three points at least two have a segment joining them?
Solution
Answer: 9.
9 is obviously sufficient. Take points A, B, C and P, Q, R, S with segments AB, BC, CA, and PQ, PR, PS, QR, QS, RS. If the three points are A, B, C or three of P, Q, R, S, then they are all joined. Any other three points must include either two from A, B, C (which will be joined) or two from P, Q, R, S (which will be joined).
Now suppose we have only 8 points. Suppose that we cannot find three points without a segment between them. If every point is joined to at least three others, then there are at least 7.3/2 segments. Contradiction. So there is a point A which is not joined to any of B, C, D, E. If two of B, C, D, E are not joined, then with A they form three points with no segments. Contradiction. So there are 6 segments between B, C, D, E.
Let the remaining two points be X, Y. Two of the points A, X, Y cannot be joined (because there are only 2 segments available outside B, C, D, E). One of the points B, C, D, E cannot be joined to either of these two points (since there are at most 2 segments available), so we have three points with no segments. Contradiction.
© John Scholes
jscholes@kalva.demon.co.uk
28 Dec 2002
Last corrected/updated 28 Dec 02