Tutte's theorem on Hamiltonian cycles
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
[edit]- ^ 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
- ^ Whitney, Hassler (1931), "A theorem on graphs", Annals of Mathematics, 2nd Series, 32 (2): 378–390, doi:10.2307/1968197, MR 1503003
- ^ 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
- ^ 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
- ^ 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
- ^ 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
- ^ Tutte, W. T. (1977), "Bridges and Hamiltonian circuits in planar graphs", Aequationes Mathematicae, 15 (1): 1–33, doi:10.1007/BF01837870, MR 0465940