Tates formodning er en tilbagevist matematisk formodning om, at enhver 3-forbundet plan kubisk graf har en Hamilton-cyklus, der passerer gennem alle dens hjørner .
Udtalt i 1884 af Peter Tate [1] , tilbagevist i 1946 af William Tutt [2] , som konstruerede et modeksempel med 25 flader, 69 kanter og 46 hjørner, Tatta-grafen . Senere, i 1988, blev der fundet et modeksempel med 21 flader, 57 kanter og 38 hjørner, og det blev bevist, at denne graf er minimal [3] .
3-regularitetsbetingelsen (3-regulære grafer kaldes kubiske) er nødvendig, fordi der er polyedre, såsom det rombiske dodekaeder . Det rombiske dodekaeder danner en todelt graf , og enhver Hamiltonsk cyklus i denne graf skal skiftevis ændre grafens dele (sider), så antallet af toppunkter i delene skal være lige store, men grafen har seks toppunkter af grad 4 på én side og otte hjørner af grad 3 på den anden.
Hvis formodningen var sand, ville en simpel løsning på firefarveproblemet følge deraf . Ifølge Tate svarer firefarveproblemet til problemet med at finde en 3-linjefarvning af broløse kubiske plane grafer . I en Hamiltonsk kubisk plan graf er en sådan kantfarvning let at finde - vi bruger skiftevis to farver til at farve kanterne langs Hamiltons cyklus, og farver de resterende kanter med den tredje farve. Alternativt kan man konstruere en firefarvet farvning af ansigterne på en Hamiltonsk kubisk plan graf direkte ved at bruge to farver til farvning af ansigterne inde i cyklussen og to farver til ansigterne udenfor.
Nøglen til modeksemplet er grafen, nu kaldet Tutta-fragmentet . Hvis dette fragment er en del af en større graf, skal enhver Hamilton-cyklus passere gennem den (hængende) kant ved det øverste toppunkt (og gennem en af de nederste kanter). En sti kan ikke komme ind gennem en nederste kant og gå ud gennem en anden bundkant.
Tutt-fragmentet bruges til at konstruere en ikke-Hamiltonsk Tutt-graf , hvis tre sådanne fragmenter lægges sammen. De "obligatoriske" kanter af fragmenterne, som skal være en del af den Hamiltonske vej gennem fragmentet, er forbundet i midten. Da enhver cyklus kun kan passere gennem to af de tre kanter i midten, kan der ikke være en Hamilton-cyklus for denne graf. Den resulterende Tutt-graf er 3-forbundet og plan , så det er en polytopgraf ifølge Steinitzs sætning . Grafen har 25 flader, 69 kanter og 46 hjørner. Geometrisk kan en graf fås fra et tetraeder (hvis flader svarer til de fire store flader i figuren - tre flader mellem par af fragmenter, og den fjerde flade er den ydre) ved gentagne gange at afkorte tre af dens hjørner.
Som Holton og McKay viste i 1988 [3] , er der præcis seks ikke-Hamiltonske 3-regulære polyedre med 38 hjørner. Polyedrene dannes ved at erstatte to hjørner af et femkantet prisme med det samme fragment fra Tuttas eksempel.