Кіріспе
Графтар теориясы
Дәлелденбеген графтар теориясы
Математикада Тайт болжамы былай гласиды: "Кез келген 3-байланысқан жазық кубтық графтың барлық төбелері арқылы Гамильтон циклі (қабырғалары бойынша) болады". Оны ұсынған және 25 жақ, 69 қабырға және 46 төбесі бар қарсы мысал құрастырып жоққа шығарған . Кейіннен 21 жақ, 57 қабырға және 38 төбесі бар бірнеше кішірек қарсы мысалдар ең аз деп дәлелденді. Графтың 3-ретті болуы шарты, мысалы, ромбтық додекаэдр сияқты көпжақтарға байланысты қажет, ол бір жағында алты 4-дәрежелі төбелері және екінші жағында сегіз 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 төбелі Гамильтондық емес көпжақтың дәл алтысы бар. Олар бесбұрышты призманың екі төбесін Тютте мысалында қолданылған фрагментпен алмастыру арқылы құрылған.