Введение
Теория графов
Опровергнутая теория графов
В математике гипотеза Тейта утверждает, что "каждый 3-связный плоский кубический граф имеет гамильтонов цикл (по ребрам), проходящий через все его вершины". Она была предложена и опровергнута , который построил контрпример с 25 гранями, 69 ребрами и 46 вершинами. Несколько меньших контрпримеров, с 21 гранью, 57 ребрами и 38 вершинами, позже были доказаны минимальными. Условие, что граф должен быть 3-регулярным, необходимо, поскольку существуют полиэдры, такие как ромбический додекаэдр, который образует двудольный граф с шестью вершинами степени четыре с одной стороны и восемью вершинами степени три с другой стороны; поскольку любой гамильтонов цикл должен чередоваться между двумя сторонами двудольного разбиения, а у них разное количество вершин, ромбический додекаэдр не является гамильтоновым. Гипотеза была значимой, поскольку, если бы она была верна, это бы подразумевало теорему о четырех красках: как описал Тейт, задача о четырех красках эквивалентна задаче поиска 3 раскрасок ребер мостовых кубических плоских графов. В гамильтоновом кубическом плоском графе такую раскраску ребер легко найти: используйте два цвета поочередно на цикле и третий цвет для всех остальных ребер. Альтернативно, можно непосредственно построить 4-раскраску граней гамильтонова кубического плоского графа, используя два цвета для граней внутри цикла и еще два цвета для граней снаружи.
Disproven graph theory
In mathematics, Tait's conjecture states that "Every 3 connected planar cubic graph has a Hamiltonian cycle (along the edges) through all its vertices". It was proposed by and disproved by , who constructed a counterexample with 25 faces, 69 edges and 46 vertices. Several smaller counterexamples, with 21 faces, 57 edges and 38 vertices, were later proved minimal by The condition that the graph be 3 regular is necessary due to polyhedra such as the rhombic dodecahedron, which forms a bipartite graph with six degree four vertices on one side and eight degree three vertices on the other side; because any Hamiltonian cycle would have to alternate between the two sides of the bipartition, but they have unequal numbers of vertices, the rhombic dodecahedron is not Hamiltonian. The conjecture was significant, because if true, it would have implied the four color theorem: as Tait described, the four color problem is equivalent to the problem of finding 3 edge colorings of bridgeless cubic planar graphs. In a Hamiltonian cubic planar graph, such an edge coloring is easy to find: use two colors alternately on the cycle, and a third color for all remaining edges. Alternatively, a 4 coloring of the faces of a Hamiltonian cubic planar graph may be constructed directly, using two colors for the faces inside the cycle and two more colors for the faces outside.
Фрагмент Тютте
Ключ к этому контрпримеру – то, что сейчас известно как фрагмент Тютте, показанный справа. Если этот фрагмент является частью большего графа, то любой гамильтонов цикл в этом графе должен проходить через верхнюю вершину (либо входя в неё, либо выходя из неё), а также через одну из нижних вершин. Невозможно войти в одну нижнюю вершину и выйти из другой.
Меньшие контрацептивы
Как показано, существует ровно шесть негамильтоновых многогранников с 38 вершинами, обладающих нетривиальными трехреберными сечениями. Они получаются заменой двух вершин пятиугольной призмы тем же фрагментом, который использовался в примере Тютте.