В геометрии инцидентности, теорема Де Брейна – Эрдеша, первоначально опубликованный Николасом Говертом де Брюйном и Полем Эрдешом (1948), устанавливает нижнюю границу количества прямые, определяемые n точками на проективной плоскости. Согласно двойственности, это также ограничение на количество точек пересечения, определяемое конфигурацией линий.
Хотя доказательство, данное Де Брёйном и Эрдешем, является комбинаторным, Де Брёйн и Эрдеш отметили в своей статье, что аналогичный (Евклидов ) результат является следствием Теорема Сильвестра – Галла, с помощью индукции по количеству точек.
Пусть P - конфигурация из n точек на проективной плоскости, а не все на прямой. Пусть t - количество строк, определяемое P. Тогда
Теорема, очевидно, верна для трех не -коллинеарные точки. Мы действуем по индукции.
Предположим, что n>3 и теорема верна для n - 1. Пусть P - набор из n точек, не все из которых лежат на одной прямой. Теорема Сильвестра – Галла утверждает, что существует прямая, содержащая ровно две точки из P. Такие две точечные прямые называются обычными прямыми. Пусть a и b - две точки P на обычной прямой.
Если удаление точки a приводит к набору коллинеарных точек, то P генерирует почти пучок из n прямых (n - 1 обычных прямых, проходящих через a, плюс одна линия, содержащая другие n - 1 точки).
В противном случае при удалении a будет получен набор P 'из n - 1 точки, которые не все коллинеарны. По предположению индукции P 'определяет не менее n - 1 прямой. Обычная линия, определяемая элементами a и b, не входит в их число, поэтому P определяет не менее n строк.
Джон Хортон Конвей имеет чисто комбинаторное доказательство, которое, следовательно, также справедливо для точек и прямых над комплексными числами, кватернионами и октонионами.