Conjectura lui Tate este o presupunere matematică respinsă că orice graf cubic plan cu 3 conexiuni are un ciclu hamiltonian care trece prin toate vârfurile sale .
Anunțat în 1884 de Peter Tate [1] , infirmat în 1946 de William Tutt [2] , care a construit un contraexemplu cu 25 de fețe, 69 de muchii și 46 de vârfuri, graficul Tatta . Ulterior, în 1988, s-a găsit un contraexemplu cu 21 de fețe, 57 de muchii și 38 de vârfuri și s-a dovedit că acest grafic este minim [3] .
Condiția de 3-regularitate (graficele 3-regulate se numesc cubice) este necesară deoarece există poliedre precum dodecaedrul rombic . Dodecaedrul rombic formează un grafic bipartit , iar orice ciclu hamiltonian din acest grafic trebuie să schimbe alternativ părțile (laturile) graficului, astfel încât numărul de vârfuri din părți trebuie să fie egal, dar graficul are șase vârfuri de gradul 4 pe unul. latura și opt vârfuri de gradul 3 pe cealaltă.
Dacă presupunerea ar fi adevărată, atunci ar urma din ea o soluție simplă la problema cu patru culori . Potrivit lui Tate, problema cu patru culori este echivalentă cu problema găsirii unei colorări pe 3 linii a graficelor plane cubice fără punte . Într-un grafic planar cubic hamiltonian, o astfel de colorare a marginilor este ușor de găsit - folosim alternativ două culori pentru a colora marginile de-a lungul ciclului hamiltonian și colorăm marginile rămase cu a treia culoare. Alternativ, se poate construi o colorare în patru culori a fețelor unui grafic cubic hamiltonian direct folosind două culori pentru colorarea fețelor din interiorul ciclului și două culori pentru fețele din exterior.
Cheia contraexemplului este graficul, numit acum fragmentul Tutta . Dacă acest fragment face parte dintr-un grafic mai mare, orice ciclu hamiltonian trebuie să treacă prin muchia (atârnată) de la vârful superior (și printr-una dintre muchiile inferioare). O cale nu poate intra printr-o margine de jos și nu poate ieși printr-o altă margine de jos.
Fragmentul Tutt este folosit pentru a construi un grafic Tutt non-Hamiltonian , dacă trei astfel de fragmente sunt adăugate împreună. Marginile „obligatorii” ale fragmentelor, care trebuie să facă parte din calea hamiltoniană prin fragment, sunt conectate la centru. Deoarece orice ciclu poate trece doar prin două dintre cele trei muchii din centru, nu poate exista un ciclu hamiltonian pentru acest grafic. Graficul Tutt rezultat este 3-conectat și plan , deci este un graf politop după teorema lui Steinitz . Graficul are 25 de fețe, 69 de muchii și 46 de vârfuri. Geometric, se poate obține un grafic dintr-un tetraedru (ale cărui fețe corespund celor patru fețe mari din figură - trei fețe între perechi de fragmente, iar a patra față este cea exterioară) prin trunchierea repetată a trei dintre vârfurile sale.
După cum au arătat Holton și McKay în 1988 [3] , există exact șase poliedre regulate non-Hamiltoniene cu 38 de vârfuri. Poliedrele se formează prin înlocuirea a două vârfuri ale unei prisme pentagonale cu același fragment din exemplul lui Tutta.