The Entire Graph of a Bridgeless Connected Plane Graph is Panconnected
Ralph J. Faudree, RICHARD H. SCHELP · Journal of the London Mathematical Society · 1975
Recently A. M. Hobbs and J. Mitchem [7] proved that the entire graph of a bridgeless connected plane graph is Hamiltonian. In this paper we strengthen this result substantially by showing that entire graphs of such plane graphs are panconnected. (Between each pair of distinct vertices in a panconnected graph there exist paths of all lengths greater than or equal to the distance between the vertices.) This fits a pattern which indicates that Hamiltonian-connected graphs seem to have paths of " many " lengths between each pair of distinct points [1,2, 3]. The graphs we consider will be undirected, finite, and have no loops or multiple edges. A plane graph is a graph already embedded in the plane. If G is a plane graph, V(G), E(G) and F(G) denote the sets of its vertices, edges and faces, respectively. Two distinct vertices (edges, faces) of G are adjacent if they share a common edge (vertex, edge). A vertex and an edge, a vertex and a face, or an edge and a face, are adjacent if they are incident (in the obvious sense). The entire graph of G, denoted e(G), is the graph with vertex set V(G) u E(G) u F(G), with two vertices of e(G) adjacent if and only if they are adjacent in G. Hamiltonian and Eulerian properties of entire graphs