Maths WorkshopMaths problems with full solutions
Exercise 2227Combinatorics › Pigeonhole principleOlympiadAdded 4 Nov 2026

The Sylvester-Gallai theorem

#combinatorial geometry#extremal principle#distance#lines

Statement

Let SS be a finite set of at least 33 points in the plane, not all on one line. Prove that there is a line passing through exactly two points of SS.

Hint

Consider all pairs consisting of a point P∈SP\in S and a line ℓ\ell through at least two points of SS with P∉ℓP\notin\ell. Choose the pair with the smallest distance from PP to ℓ\ell.

Show solutionHide solution

Solution

Choosing a minimal pair. There are finitely many such pairs (P,ℓ)(P,\ell), and at least one. Choose one for which the distance h=dist⁡(P,ℓ)>0h=\operatorname{dist}(P,\ell)>0 is smallest. Let QQ be the foot of the perpendicular from PP to ℓ\ell.

Claim. The line ℓ\ell contains exactly two points of SS.

Suppose not: ℓ\ell contains at least three points of SS. Among them, at least two lie in one closed half-line of ℓ\ell starting at QQ. Call these two points BB and CC, with BB between QQ and CC or B=QB=Q, and B≠CB\ne C. Then BC≤QC<PCBC\le QC<PC.

A closer pair. Consider the line m=PCm=PC, which contains the two points P,CP,C of SS. The point BB is not on mm. The distance from BB to mm is
dist⁡(B,m)=BCsin⁡∠PCQ=BC⋅hPC<h,\operatorname{dist}(B,m)=BC\sin\angle PCQ=BC\cdot\frac{h}{PC}<h,
because BC<PCBC<PC. So the pair (B,m)(B,m) has a smaller distance than (P,ℓ)(P,\ell), contradicting the choice.

Therefore ℓ\ell passes through exactly two points of SS. □\square

Remark. This is Kelly's proof (1948) of a conjecture of Sylvester. The statement is false in the projective plane (the Fano plane has 77 points and every line has 33), which shows that the proof must use distances.

Lesson. The extremal principle: pick the configuration minimising a quantity and show that a smaller one exists unless the structure is special.