In incidence geometry, the De Bruijn–Erdős theorem, originally published by Nicolaas Govert de Bruijn

Nicolaas Govert de Bruijn

Nicolaas Govert de Bruijn is a Dutch mathematician, affiliated as professor emeritus with the Eindhoven University of Technology. He received his Ph.D. in 1943 from Vrije Universiteit Amsterdam....

 and Paul Erdős

Paul Erdos

Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...

, states a lower bound on the number of lines determined by n points in a projective plane

Projective plane

In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines that do not intersect...

. By duality

Duality (projective geometry)

A striking feature of projective planes is the "symmetry" of the roles played by points and lines in the definitions and theorems, and duality is the formalization of this metamathematical concept. There are two approaches to the subject of duality, one through language and the other a more...

, 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

Combinatorial proof

In mathematics, the term combinatorial proof is often used to mean either of two types of proof of an identity in enumerative combinatorics that either states that two sets of combinatorial configurations, depending on one or more parameters, have the same number of elements , or gives a formula...

, De Bruijn and Erdős noted in their paper that the analogous (Euclidean

Euclidean geometry

Euclidean geometry is a mathematical system attributed to the Alexandrian Greek mathematician Euclid, which he described in his textbook on geometry: the Elements. Euclid's method consists in assuming a small set of intuitively appealing axioms, and deducing many other propositions from these...

) result is a consequence of the Sylvester–Gallai theorem

Sylvester–Gallai theorem

The Sylvester–Gallai theorem asserts that given a finite number of points in the Euclidean plane, either# all the points are collinear; or# there is a line which contains exactly two of the points.This claim was posed as a problem by...

, by an induction

Mathematical induction

Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...

 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

Mathematical induction

Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...

.

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.