Tates gissning är en vederlagd matematisk gissning att varje 3-kopplad plan kubisk graf har en Hamiltonsk cykel som passerar genom alla dess hörn .
Uppgiven 1884 av Peter Tate [1] , vederlagd 1946 av William Tutt [2] , som konstruerade ett motexempel med 25 ansikten, 69 kanter och 46 hörn, Tatta-grafen . Senare, 1988, hittades ett motexempel med 21 ytor, 57 kanter och 38 hörn och det bevisades att denna graf är minimal [3] .
3-regularitetsvillkoret (3-regelbundna grafer kallas kubiska) är nödvändigt eftersom det finns polyedrar som den rombiska dodekaedern . Den rombiska dodekaedern bildar en tvådelad graf , och varje Hamiltonsk cykel i denna graf måste växelvis ändra delarna (sidorna) av grafen, så antalet hörn i delarna måste vara lika, men grafen har sex hörn av grad 4 på en sidan och åtta hörn av grad 3 på den andra.
Om gissningen var sann, skulle en enkel lösning på fyrfärgsproblemet följa av det . Enligt Tate är fyrfärgsproblemet likvärdigt med problemet med att hitta en 3-linjers färgning av brolösa kubiska plana grafer . I en Hamiltonsk kubisk plan graf är en sådan kantfärgning lätt att hitta - vi använder växelvis två färger för att färga kanterna längs Hamiltons cykel, och färgar de återstående kanterna med den tredje färgen. Alternativt kan man konstruera en fyrfärgsfärgning av ytorna på en Hamiltonsk kubisk plan graf direkt genom att använda två färger för färgning av ytorna inuti cykeln och två färger för ytorna utanför.
Nyckeln till motexemplet är grafen, nu kallad Tutta-fragmentet . Om detta fragment är en del av en större graf, måste alla Hamiltons cykel passera genom den (hängande) kanten vid den övre vertexen (och genom en av de nedre kanterna). En stig kan inte gå in genom en nedre kant och gå ut genom en annan nedre kant.
Tutt-fragmentet används för att konstruera en icke-Hamiltonsk Tutt-graf , om tre sådana fragment adderas tillsammans. De "obligatoriska" kanterna på fragmenten, som måste vara en del av Hamiltons väg genom fragmentet, är sammankopplade i mitten. Eftersom varje cykel bara kan passera genom två av de tre kanterna i mitten, kan det inte finnas en Hamiltonsk cykel för denna graf. Den resulterande Tutt-grafen är 3-kopplad och plan , så det är en polytopgraf enligt Steinitz sats . Grafen har 25 ytor, 69 kanter och 46 hörn. Geometriskt kan en graf erhållas från en tetraeder (vars ytor motsvarar de fyra stora ytorna i figuren - tre ytor mellan par av fragment, och den fjärde ytan är den yttre) genom att upprepade gånger trunkera tre av dess hörn.
Som Holton och McKay visade 1988 [3] finns det exakt sex icke-Hamiltonska 3-regelbundna polyedrar med 38 hörn. Polyedrarna bildas genom att ersätta två hörn av ett femkantigt prisma med samma fragment från Tuttas exempel.