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
[szerkesztés]
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
[szerkesztés]
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
[szerkesztés]- 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
[szerkeszté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.