de Bruijn–Erdős theorem

Remarks

For a point $p$ let $r_p$ be the number of lines through $p$, and for a line $\ell$ let $k_\ell$ be its number of points. If $p$ is not on $\ell$, the lines joining $p$ to the points of $\ell$ are distinct, so $r_p \ge k_\ell$. Write $b = \abs{L}$ and sum $1/(n(b - r_p))$ and $1/(b(n - k_\ell))$ over all pairs $(p, \ell)$ with $p \notin \ell$: each sum equals $1$. If $b < n$, then $n r_p > b k_\ell$ for each such pair, so each term of the first sum is larger than the matching term of the second, a contradiction. A closer look at the case $b = n$ gives the description of equality.

Hypothesis 3 is needed: a single line through all $n \ge 3$ points satisfies clauses 1 and 2 and has only one line.

A consequence: $n$ points of the real plane, not all on one line, determine at least $n$ distinct lines through two or more of them. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős.

Going deeper

For a student

The statement lives in a linear space, a partial linear space in which any two points are joined. It is close in spirit to Fisher's inequality for block designs. Applied to points in the real plane, it gives a lower bound for the number of lines they determine, a question related to the Sylvester–Gallai theorem. The equality case shows how rigid projective planes are among all finite linear spaces.