Гипотеза Эрдёша — Дьярфаша

Любой граф с вершинами степени не менее 3 содержит простой цикл длиной, равной степени двойки.

Гипотеза сформулирована в 1995 году венгерскими математиками Палом Эрдёшем и Андрашем Дьярфашем.

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

Известен более слабый результат относительно степени графа, содержащего циклы длины из некоторого множества: имеется множество ${\displaystyle S}$ длин, с ${\displaystyle |S|=\mathrm {O} (n^{0,99})}$, такое, что любой граф со средней степенью десять или более содержит цикл с длиной из ${\displaystyle S}$^[1]. Известно также, что гипотеза верна для планарных графов без клешней^[2] и для графов, у которых нет больших звёзд и которые удовлетворяют дополнительным ограничениям на степень вершин^[3].