De Bruijn–Erdős theorem (incidence geometry)

In incidence geometry, the De Bruijn–Erdős theorem, originally published by Nicolaas Govert de Bruijn and Paul Erdős (1948), states a lower bound on the number of lines determined by n points in a projective plane. By duality, this is also a bound on the number of intersection points determined by a configuration of lines.

Although the proof given by De Bruijn and Erdős is combinatorial, De Bruijn and Erdős noted in their paper that the analogous (Euclidean) result is a consequence of the Sylvester–Gallai theorem, by an induction on the number of points.

Statement of the theorem

Let P be a configuration of n points in the projective plane, not all on a line. Let t be the number of lines determined by P. Then,

t ≥ n,
if t = n, any two lines share a point.

Proof

The theorem is clearly true for three non-collinear points. We proceed by induction.

Assume n > 3 and the theorem is true for n − 1. Let P be a set of n points not all collinear. The Sylvester–Gallai theorem states that P determines an ordinary (i.e., two-point) line. Let a and b be two points in P spanned by an ordinary line.

If the removal of point a produces a set of collinear points then the remaining n − 1 > 2 points all lie on a line through b, not incident to a. In which case, remove b to obtain a set, P' , of n − 1 non-collinear points. By our hypothesis, P' spans n − 1 lines which is exactly one fewer than the number of lines spanned by P (since the line connecting a and b is not present).

Otherwise, the removal of a produces a set, P' , of n − 1 non-collinear points. Again, by our hypothesis, P' spans n − 1 lines which is at least one fewer than the number of lines spanned by P.

References

de Bruijn, N. G.; Erdős, P. (1948), "A combinatioral [sic] problem" (PDF), Indagationes Mathematicae, 10: 421–423.
Batten, Lynn Margaret (1997), "2.2 The de Bruijn–Erdős theorem", Combinatorics of finite geometries (2 ed.), Cambridge University Press, pp. 25–27, ISBN 0-521-59014-0