Гипотеза Эрдёша — Дьярфаша — нерешённая проблема в теории графов
Формулировка Любой граф с вершинами степени не менее 3 содержит простой цикл длиной, равной степени двойки.
История
Гипотеза сформулирована в 1995 году венгерскими математиками Палом Эрдёшем и .
Компьютерный поиск, осуществлённый и Класом Маркстрёмом (Klas Markström) показал, что любой контрпример должен иметь минимум 17 вершин и любой кубический контрпример должен иметь минимум 30 вершин. Поиск Маркстрёма дал четыре графа с 24 вершинами, имеющих циклы степени двойки только с 16 вершинами, при этом один из этих графов является планарным.
Известен более слабый результат относительно степени графа, содержащего циклы длины из некоторого множества: имеется множество длин, с , такое, что любой граф со средней степенью десять или более содержит цикл с длиной из . Известно также, что гипотеза верна для планарных графов без клешней и для графов, у которых нет больших звёзд и которые удовлетворяют дополнительным ограничениям на степень вершин.
Примечания
Литература
Ссылки
Категория:Математические гипотезы Категория:Графы, имеющие собственные названия Категория:Пал Эрдёш