Теорема де Брёйна — Эрдёша

Установлена Николасом де Брёйном и Палом Эрдёшем в 1948 году.

Пусть задан набор ${\displaystyle P}$ из ${\displaystyle n}$ точек на проективной плоскости, из которых не все лежат на одной прямой. Пусть ${\displaystyle t}$ это число всех прямых, проходящих через пары точек из ${\displaystyle P}$: Тогда ${\displaystyle t\geqslant n}$. Более того, если ${\displaystyle t=n}$, то любые две прямые пересекаются в точке из ${\displaystyle P}$.

Стандартное доказательство ведётся по индукции. Теорема определённо верна для трёх точек, не лежащих на одной прямой. Пусть ${\displaystyle n>3}$, утверждение верно для ${\displaystyle n-1}$ и ${\displaystyle P}$ — множество из ${\displaystyle n}$ точек, не все из которых лежат на одной прямой. По теореме Сильвестра одна из этих прямых проходит ровно через две точки из ${\displaystyle P}$. Обозначим эти две точки ${\displaystyle a}$ и ${\displaystyle b}$.

Если при удалении точки ${\displaystyle a}$ все оставшиеся точки будут на одной прямой, то ${\displaystyle P}$ образует пучок из ${\displaystyle P}$ прямых (${\displaystyle n-1}$ простых прямых проходят через ${\displaystyle P}$, плюс одна прямая, проходящая через остальные точки). В противном случае удаление ${\displaystyle a}$ образует множество ${\displaystyle P}$ из ${\displaystyle n-1}$ неколлинеарной точки. По предположению индукции через ${\displaystyle P}$ проходят ${\displaystyle n-1}$ прямые, что по меньшей мере на единицу меньше числа прямых, проходящих через точки множества ${\displaystyle P}$.

• N. G. de Bruijn, P. Erdős. A combinatioral [sic] problem // Indagationes Mathematicae. — 1948. — Т. 10. — С. 421—423.
• Lynn Margaret Batten. Combinatorics of finite geometries. — Cambridge University Press, 1997. — С. 25–27. — ISBN 0-521-59014-0.