Tait gráfelméleti sejtése

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

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

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

• Tait's Hamiltonian Graph Conjecture Wolfram MathWorld
• Tait, P. G. (1884). „Listing's Topologie”. Philosophical Magazine (5th ser.) 17, 30–46. o.  . Újraközölve: Scientific Papers, Vol. II. 85–98. o.
• Tutte, W. T. (1946). „On Hamiltonian circuits”. Journal of the London Mathematical Society 21 (2), 98–101. o.  

Fordítás

Ez a szócikk részben vagy egészben a Tait's conjecture című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.