On Hamiltonian cycles through prescribed edges of a planar graph
Jochen Harant · Cologne Twente Workshop on Graphs and Combinatorial Optimization · 2010
We use [3] for terminology and notation not defined here and consider finite simple graphs only. The first major result on the existence of hamiltonian cycles in graphs embeddable in surfaces was by H. Whitney [12] in 1931, who proved that 4-connected maximal planar graphs are hamiltonian. In 1956, W.T. Tutte [10,11] generalized Whitney’s result from maximal planar graphs to arbitrary 4-connected planar graphs. Actually, Tutte proved that a 4-connected planar graph G has a hamiltonian cycle through any two edges of a given face of G. Moreover, in [7,8] it is proved that a 4-connected planar graph G has a hamiltonian cycle through any three edges of a given face of G or that face is a 3-gon. Improving a result of C. Thomassen [9], in 1997, D.P. Sanders [7] proved the following: