# zbMATH — the first resource for mathematics

On paths in planar graphs. (English) Zbl 0880.05059
Let $$G$$ be a 2-connected plane graph and let $$X_G$$ be the circuit bounding the infinite face. This paper generalizes the following result by C. Thomassen [J. Graph Theory 7, 169-176 (1983; Zbl 0515.05040)], which in turn was an improvement of an earlier theorem by W. T. Tutte [Trans. Am. Math. Soc. 82, 99-116 (1956; Zbl 0070.18403)]. Let $$u$$, $$v$$ be two vertices and $$e$$ be an edge of $$G$$. If $$u\neq v$$ and both $$u$$ and $$e$$ belong to $$X_G$$, then $$G$$ has a Tutte path from $$u$$ to $$v$$ containing $$e$$. (Tutte paths are a generalization of Hamilton paths, see the paper for the definition.) The main result of this article removes the restriction on the location of $$u$$, as follows. Let $$u$$, $$v$$ be two vertices and $$e$$ be an edge of $$G$$. If $$u\neq v$$ and $$e$$ belong to $$X_G$$, then $$G$$ has a Tutte path from $$u$$ to $$v$$ containing $$e$$. Two corollaries follow. (i) Let $$G$$ be 4-connected, $$u$$, $$v$$ be vertices and $$e\neq uv$$ be an edge of $$G$$. Then $$G$$ has a Hamiltonian path from $$u$$ to $$v$$ through $$e$$. (ii) Let $$G$$ be 4-connected. Then $$G$$ has a Hamiltonian cycle though any two of its edges.

##### MSC:
 05C38 Paths and cycles 05C10 Planar graphs; geometric and topological aspects of graph theory 05C45 Eulerian and Hamiltonian graphs
##### Keywords:
plane graph; Tutte path; Hamilton paths; Hamiltonian cycle
Full Text: