Locally Hamiltonian graphs and minimal size of maximal graphs on a surface (Q2185215): Difference between revisions

A graph \(G\) is called locally Hamiltonian if for each vertex \(v\) of \(G\) the subgraph induced by the neighborhood of \(v\) is Hamiltonian. The main result of the paper states: Every locally Hamiltonian multigraph \(G\) on \(n\) vertices, with no loops, has at least \(3n-6\) edges. The equality is attained iff \(G\) triangulates the sphere. Several consequence of this deep result are given as well.