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.
@article{10_37236_9286,
author = {James Davies and Carsten Thomassen},
title = {Locally {Hamiltonian} graphs and minimal size of maximal graphs on a surface},
journal = {The electronic journal of combinatorics},
year = {2020},
volume = {27},
number = {2},
doi = {10.37236/9286},
zbl = {1448.05049},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9286/}
}
TY - JOUR
AU - James Davies
AU - Carsten Thomassen
TI - Locally Hamiltonian graphs and minimal size of maximal graphs on a surface
JO - The electronic journal of combinatorics
PY - 2020
VL - 27
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/9286/
DO - 10.37236/9286
ID - 10_37236_9286
ER -
%0 Journal Article
%A James Davies
%A Carsten Thomassen
%T Locally Hamiltonian graphs and minimal size of maximal graphs on a surface
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/9286/
%R 10.37236/9286
%F 10_37236_9286
James Davies; Carsten Thomassen. Locally Hamiltonian graphs and minimal size of maximal graphs on a surface. The electronic journal of combinatorics, Tome 27 (2020) no. 2. doi: 10.37236/9286
