Tutte's theorem on Hamiltonian cycles

Last updated

In graph theory, a theorem of W. T. Tutte states that every 4-vertex-connected planar graph has a Hamiltonian cycle. [1] It strengthens an earlier theorem of Hassler Whitney according to which every 4-vertex-connected maximal planar graph has a Hamiltonian cycle. [2]

In turn, Tutte's theorem is strengthened by an analogous theorem of Robin Thomas and X. Yu for graphs on the projective plane, [3] and by the unproven Grünbaum–Nash-Williams conjecture, according to which every 4-vertex-connected toroidal graph has a Hamiltonian cycle. [4]

Tutte's theorem can be seen as a weakened version of Tait's conjecture on Hamiltonian cycles in 3-vertex-connected graphs, which was disproved by Tutte's discovery of the Tutte graph in 1946. [5] Instead, Barnette's conjecture, still unproven, weakens Tait's conjecture in a different way, to bipartite planar graphs. [6]

Tutte's original publication of the theorem in 1956 had a complicated proof; he included a simplification of the proof in a 1977 survey paper. [7]

References

  1. ↑ Tutte, W. T. (1956), "A theorem on planar graphs", Transactions of the American Mathematical Society , 82: 99–116, doi:10.1090/S0002-9947-1956-0081471-8, JSTOR   1992980, MR   0081471
  2. ↑ Whitney, Hassler (1931), "A theorem on graphs", Annals of Mathematics , 2nd Series, 32 (2): 378–390, doi:10.2307/1968197, MR   1503003
  3. ↑ Thomas, Robin; Yu, Xingxing (1994), "4-connected projective-planar graphs are Hamiltonian", Journal of Combinatorial Theory, Series B , 62 (1): 114–132, doi:10.1006/jctb.1994.1058, MR   1290634
  4. ↑ Kawarabayashi, Ken-ichi; Niu, Jianbing; Zhang, Cun-Quan (2007), "Chords of longest circuits in locally planar graphs", European Journal of Combinatorics , 28 (1): 315–321, doi:10.1016/j.ejc.2005.07.017, MR   2261821
  5. ↑ Tutte, W. T. (1946), "On Hamiltonian circuits", Journal of the London Mathematical Society , 21 (2): 98–101, doi:10.1112/jlms/s1-21.2.98
  6. ↑ Barnette, David W. (1969), "Conjecture 5", in Tutte, W. T. (ed.), Recent Progress in Combinatorics: Proceedings of the Third Waterloo Conference on Combinatorics, May 1968, New York: Academic Press, MR   0250896
  7. ↑ Tutte, W. T. (1977), "Bridges and Hamiltonian circuits in planar graphs", Aequationes Mathematicae , 15 (1): 1–33, doi:10.1007/BF01837870, MR   0465940
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.