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