Граф Татта, состоит из трёх одинаковых кусков, так называемых фрагментов Татта.
Фрагмент обладает свойством, что из трёх выходящих из него рёбер одно обязательно присутствует в гамильтоновом цикле в любом графе с таким фрагментом.
«Обязательные» рёбра фрагмента подходят к центральной вершине.
Поскольку любой гамильтонов цикл может использовать лишь два из них, гамильтонова цикла не существует.
Полученный граф является 3-связным и планарным, так что по теореме Штайница этот граф является графом многогранника. Граф имеет 25 граней.
Геометрически может быть получен из тетраэдра (каждая грань которого соответствует четырём большим граням с 9 рёбрами, три из которых находятся между парами фрагментов, а четвёртая образует внешнюю грань) путём многократного отсечения трёх его вершин.
В 1968 году Гринберг построил ещё несколько контрпримеров для гипотезы Тэйта — графы Гринберга с 42, 44 и 46 вершинами[6], а в 1974 году найдены ещё два таких графа (графы Фолкнера — Янгера) с 42 и 44 вершинами[7]. В 1988 году установлено, что существует в точности шесть негамильтоновых полиэдральных графов с 38 вершинами, имеющих нетривиальные сечения трёх рёбер, они образуются путём замены двух вершин пятиугольной призмы тем же фрагментом, что используется в примере Татта[8].
Примечания
↑P. G. Tait. Listing's Topologie // Philosophical Magazine (5th ser.). — 1884. — Т. 17. — С. 30–46.. Статья перепечатана в Scientific Papers, Vol. II, pp. 85-98.
↑W. T. Tutte. On Hamiltonian circuits // Journal of the London Mathematical Society. — 1946. — Т. 21, вып. 2. — С. 98–101. — doi:10.1112/jlms/s1-21.2.98.
↑Lederberg, J. «DENDRAL-64: A System for Computer Construction, Enumeration and Notation of Organic Molecules as Tree Structures and Cyclic Graphs. Part II. Topology of Cyclic Graphs.» Interim Report to the National Aeronautics and Space Administration. Grant NsG 81-60. December 15, 1965. [1]Архивная копия от 20 мая 2014 на Wayback Machine
↑Э. Я. Гринберг. Плоские однородные графы степени три без гамильтоновых циклов. // Латв. матем. ежегодник. — Т. 4. — С. 51-58..
↑G. B. Faulkner, D. H. Younger. Non-Hamiltonian Cubic Planar Maps. // Discrete Mathematics. — 1974. — Т. 7. — С. 67-74.
↑D. A. Holton, B. D. McKay. The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices // Journal of Combinatorial Theory, Series B. — 1988. — Т. 45, вып. 3. — С. 305–319. — doi:10.1016/0095-8956(88)90075-5.
Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!