2020/01/14 by Davies, James, Thomassen, Carsten
#05C10 #05C35 #05C45 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2001.04836
We prove that every locally Hamiltonian graph with n≥ 3 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 graph on some 2-dimensional surface Σ (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 Σ is the same as the clockwise or anti-clockwise orientation around v on the sphere. If G contains no complete graph on 4 vertices and has at least 4 vertices, then the face-boundaries are the same in the two embeddings.