В математике гипотеза Тейта гласит, что «Каждый трехсвязный планарный кубический граф имеет гамильтонов цикл (вдоль ребер) через все свои вершины ». Он был предложен П.Г. Тейтом (1884) и опровергнут У.Татте (1946), который построил контрпример с 25 гранями, 69 ребрами и 46 вершинами. Несколько меньших контрпримеров с 21 гранью, 57 ребрами и 38 вершинами позже были доказаны Холтоном и Маккеем (1988). Условие 3-регулярности графа необходимо из-за таких многогранников, как ромбический додекаэдр , который образует двудольный граф с шестью вершинами четвертой степени на одной стороне и восемью вершинами третьей степени на другой стороне; поскольку любой гамильтонов цикл должен был бы чередоваться между двумя сторонами бираздела, но они имеют неодинаковое количество вершин, ромбдодекаэдр не является гамильтоновым.
Гипотеза была важной, потому что, если бы она была верной, она подразумевала бы теорему о четырех цветах : как описал Тейт, проблема четырех цветов эквивалентна проблеме нахождения 3-реберной раскраски кубических плоских графов без мостов . В гамильтоновом кубическом планарном графе такую раскраску ребер найти легко: используйте поочередно два цвета на цикле и третий цвет для всех остальных ребер. Альтернативно, 4-раскраска граней гамильтонова кубического планарного графа может быть построена напрямую, используя два цвета для граней внутри цикла и еще два цвета для граней снаружи.
Ключом к этому контрпримеру является то, что теперь известно как фрагмент Тутте , показанный справа.
Если этот фрагмент является частью большего графа, то любой гамильтонов цикл графа должен входить или выходить из верхней вершины (и любой из нижних). Он не может войти в одну нижнюю вершину и выйти из другой.
Затем фрагмент можно использовать для построения негамильтонова графа Тутте , соединив три таких фрагмента, как показано на рисунке. «Обязательные» ребра фрагментов, которые должны быть частью любого гамильтонова пути через фрагмент, соединяются в центральной вершине; поскольку любой цикл может использовать только два из этих трех ребер, не может быть гамильтонова цикла.
Полученный граф Тутте является 3-связным и плоским , поэтому по теореме Стейница это график многогранника. Всего у него 25 граней, 69 ребер и 46 вершин. Геометрически его можно реализовать из тетраэдра (грани которого соответствуют четырем большим граням на рисунке, три из которых находятся между парами фрагментов, а четвертая образует внешнюю часть) путем многократного усечения трех его вершин.
Как показывают Холтон и Маккей (1988), существует ровно шесть негамильтоновых многогранников с 38 вершинами, которые имеют нетривиальные трехреберные разрезы. Они образуются путем замены двух вершин пятиугольной призмы тем же фрагментом, что и в примере Тутте.
Частично основано на публикации Билла Тейлора на sci.math, использовано с разрешения.