Теорема де Брёйна — Эрдёша — теорема теории графов доказанная Палом Эрдёшем и Николаасом де Брёйном[1].
Хроматическое число бесконечного графа, если это число конечно, равно наибольшему хроматическому числу среди всех его конечных подграфов.
Теорема де Брёйна — Эрдёша имеет несколько различных доказательств, каждое использует аксиому выбора. Исходное доказательство де Брёйна использовало трансфинитную индукцию[2].
Готтшальк[3] дал следующее очень короткое доказательство, основанное на теореме о компактности Тихонова в топологии. Предположим, что для заданного бесконечного графа G любой конечный подграф является k-раскрашиваемым, и пусть X — пространство всех назначений k цветов вершинам графа G (независимо от того, является ли данная раскраска правильной). Тогда X можно рассматривать как произведение топологических пространств kV(G), которое по теореме Тихонова компактно. Для каждого конечного подграфа F графа G, пусть XF — подмножество X, состоящее из назначений цветов, дающих правильную раскраску F. Тогда система множеств XF является семейством замкнутых множеств со свойством конечных пересечений[англ.], так что из-за компактности система имеет непустое пересечение. Любой член этого пересечения является правильной раскраской G [4].
Другое доказательство, использующее лемму Цорна, дал Лайош Поза[англ.], а также привёл в тезисах диссертации 1951 Эндрю Дирак[англ.]. Если G — бесконечный граф, в котором любой конечный подграф является k-раскрашиваемым, тогда по лемме Цорна он является подграфом максимального графа M с тем же свойством (граф, к которому нельзя добавить рёбра без того, чтобы некоторый конечный подграф не потребует более k цветов). Бинарное отношение несмежности в M является отношением эквивалентности и классы эквивалентности этого отношения дают k-раскраску графа G. Однако это доказательство труднее обобщить, чем доказательство по лемме о компактности[5].
Теорему можно доказать с помощью ультрафильтров[6] или нестандартного анализа[7]. Нэш-Вилльямс[8] дал доказательство для графов со счётным числом вершин, основываясь на лемме Кёнига о бесконечном дереве.