Exercise 1977Combinatorics › Pigeonhole principleOlympiadAdded 5 Nov 2026

The Sylvester–Gallai theorem

#combinatorial geometry#extremal principle#minimal distance

Statement

Let $S$ be a finite set of points in the plane, not all on one line. Prove that there is a line containing exactly two points of $S$ .

Hint

Among all pairs (point $P$ of $S$ , line $\ell$ through at least two points of $S$ with $P\notin\ell$ ), choose one with the smallest distance from $P$ to $\ell$ . Show that $\ell$ contains no third point.

Show solutionHide solution

Solution

Idea (Kelly). Minimise a distance, then find a smaller one if the line has three points.

Setup. Since the points are not all collinear, such pairs $(P,\ell)$ exist, and there are finitely many, so one pair minimises $d(P,\ell)=PQ>0$ .

Claim. $\ell$ contains exactly two points of $S$ . Suppose it contains at least three. Among three points of $\ell$ , two (say $B\ne C$ ) lie on the same side of $Q$ on $\ell$ ; label them so that $B$ lies between $Q$ and $C$ . Then $BC\le QC<PC$ , because $PC$ is the hypotenuse of the right triangle $PQC$ .

Consider the line $m=PC$ (it contains the two points $P,C$ of $S$ ) and the point $B\in S$ . $B$ is not on $m$ . The distance from $B$ to $m$ is
$d(B,m)=BC\sin\angle PCQ=BC\cdot\frac{PQ}{PC}<PQ,$
contradicting the minimality of $PQ$ . Hence $\ell$ contains exactly two points of $S$ . ∎

Remark. Finiteness is needed: for the set of all points with rational coordinates every line through two points contains infinitely many.

Lesson. Extremal principle: pick the configuration minimising a distance, then show a violation would produce a smaller one.

The Sylvester–Gallai theorem

Statement

Solution

More problems in Pigeonhole principle