Tait gráfelméleti sejtése, amelyet P. G. Tait skót matematikus fogalmazott meg 1884-ben a következőképpen jelenthető ki:
„Minden 3-szorosan összefüggő, 3-reguláris síkgráfban van Hamilton-kör.”
A sejtést 1946-ban W. T. Tutte megcáfolta egy ellenpéldával, amely 25 tartományt (lapot), 69 élt és 46 csúcsot tartalmazott. Később kisebb méretű ellenpéldát is találtak.
A sejtés azért fontos, mert igaz voltából következett volna a négyszín-tétel.
Tutte részgráfja 100px|jobbra A mellékelt részgráfban három él kapcsolódik a gráf más részeihez, és minden Hamilton-körnek át kell mennie a felső élen, és valamelyik alsó élen, de nem mehet át mindkét alsó élen.
Az ellenpélda 170px|jobbra A mellékelt gráf középen található csúcsához kapcsolódó három él közül csak kettő lehet része egy Hamilton-körnek, de a részgráfok tulajdonságai miatt mind a háromnak kellene. Ez a gráf tehát cáfolja Tait sejtését.
Források Wolfram MathWorld . Újraközölve: Scientific Papers, Vol. II. 85–98. o.
Fordítás
Kategória:Megcáfolt sejtések Kategória:Síkgráfok Kategória:Hamilton-utak és -körök