Tait gráfelméleti sejtése

A Wikipédiából, a szabad enciklopédiából
(Tait-sejtés szócikkből átirányítva)
Ugrás a navigációhoz Ugrás a kereséshez

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]

TutteFrag.png

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]

PlanarNonHamil.png

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.