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

Встановили Ніколас де Брейном і Пал Ердеш 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 (3 листопада). — С. 421—423.
• Lynn Margaret Batten. Combinatorics of finite geometries. — Cambridge University Press, 1997. — С. 25–27. — ISBN 0-521-59014-0.