Locally Hamiltonian Graphs and Minimal Size of Maximal Graphs on a Surface

Abstract

We prove that every locally Hamiltonian graph with $n$ vertices and possibly with multiple edges has at least $3n-6$ edges with equality if and only if it triangulates the sphere. As a consequence, every edge-maximal embedding of a graph $G$ on some 2-dimensional surface $\Sigma$ (not necessarily compact) has at least $3n-6$ edges with equality if and only if $G$ also triangulates the sphere. If, in addition, $G$ is simple, then for each vertex $v$, the cyclic ordering of the edges around $v$ on $\Sigma$ is the same as the clockwise or anti-clockwise orientation around $v$ on the sphere. If $G$ contains no complete graph on 4 vertices, then the face-boundaries are the same in the two embeddings.