On paths in planar graphs.

*(English)*Zbl 0880.05059Let \(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.

Reviewer: R.Scapellato (Milano)