Гипотеза Тейта

Эта статья о теории графов. О гипотезах теории узлов см. в разделе «Гипотезы Тейта» .

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

Гипотеза была важной, потому что, если бы она была верной, она подразумевала бы теорему о четырех цветах : как описал Тейт, проблема четырех цветов эквивалентна проблеме нахождения 3-реберной раскраски кубических плоских графов без мостов . В гамильтоновом кубическом планарном графе такую ​​раскраску ребер найти легко: используйте поочередно два цвета на цикле и третий цвет для всех остальных ребер. Альтернативно, 4-раскраска граней гамильтонова кубического планарного графа может быть построена напрямую, используя два цвета для граней внутри цикла и еще два цвета для граней снаружи.

Все это контрпример

Фрагмент Тутте

Ключом к этому контрпримеру является то, что теперь известно как фрагмент Тутте , показанный справа.

Если этот фрагмент является частью большего графа, то любой гамильтонов цикл графа должен входить или выходить из верхней вершины (и любой из нижних). Он не может войти в одну нижнюю вершину и выйти из другой.

Контрпример

Затем этот фрагмент можно использовать для построения негамильтоновского графа Тутте , поместив вместе три таких фрагмента, как показано на картинке. «Обязательные» ребра фрагментов, которые должны быть частью любого гамильтонова пути через фрагмент, соединяются в центральной вершине; поскольку любой цикл может использовать только два из этих трех ребер, не может быть гамильтонова цикла.

Полученный граф Тутте является 3-связным и плоским , поэтому по теореме Стейница это график многогранника. Всего у него 25 граней, 69 ребер и 46 вершин. Геометрически его можно реализовать из тетраэдра (грани которого соответствуют четырем большим граням на рисунке, три из которых находятся между парами фрагментов, а четвертая образует внешнюю часть) путем многократного усечения трех его вершин.

Меньшие контрпримеры

Как показывают Холтон и Маккей (1988) , существует ровно шесть негамильтоновых многогранников с 38 вершинами, которые имеют нетривиальные трехреберные разрезы. Они образуются путем замены двух вершин пятиугольной призмы тем же фрагментом, что и в примере Тутте.

См. также

• Теорема Гринберга — необходимое условие существования гамильтонова цикла, которое можно использовать, чтобы показать, что граф образует контрпример к гипотезе Тейта.
• Гипотеза Барнетта — все еще открытое уточнение гипотезы Тейта, утверждающее, что каждый двудольный кубический многогранный граф является гамильтоновым.

Ссылки

• Холтон, Д.А.; Маккей, Б.Д. (1988), «Наименьшие негамильтоновы 3-связные кубические плоские графы имеют 38 вершин», Journal of Combinatorial Theory, Series B , 45 (3): 305–319, doi : 10.1016/0095-8956 (88) )90075-5 .
• Тейт, П.Г. Листинга (1884), « Топология », Философский журнал , 5-я серия, 17 : 30–46 . Перепечатано в научных статьях , Vol. II, стр. 85–98.
• Тутте, В.Т. (1946), «О гамильтоновых схемах» (PDF) , Журнал Лондонского математического общества , 21 (2): 98–101, doi : 10.1112/jlms/s1-21.2.98 .

Частично основано на публикации Билла Тейлора на sci.math , использовано с разрешения.

Внешние ссылки

• Вайсштейн, Эрик В. «Гипотеза Тейта о гамильтоновом графе» . Математический мир .