Question.
A graph is a locally Hamiltonian graph if for every vertex $v$ induced subgraph $G(N(v))$ is Hamiltonian.
Give an example of a locally Hamiltonian but not Hamiltonian graph.
Part of the solution that I came to
This planar triangulation (Pic 1.) is locally Hamiltonian but not a Hamiltonian graph.
How to prove it?
Pic 1.
Best Answer
Any planar triangulation will be locally Hamiltonian. I'm not sure if your definition of $N(v)$ includes the vertex $v$ itself, but it works either way. We can take a plane embedding (so, the edge $(1,5)$ in your drawing should be bent to avoid crossing $(2,3)$) and go around the neighbors of any vertex $v$ in clockwise order of the edges out of $v$. This will always form a cycle. If we want to include $v$ in the cycle as well, we can insert it at any point.
To see that this planar triangulation is not Hamiltonian, consider the vertex coloring below (vertices $\{1,3,5,7,9\}$ are red, and vertices $\{2,4,6,8,10,11\}$ are blue).
This coloring has the property that each blue vertex has only red neighbors. So, if there is a Hamiltonian cycle in the graph, then (if we give the Hamiltonian cycle a direction) the vertex that comes after every blue vertex must be red.
However, there are $6$ blue vertices, and only $5$ red vertices. That's not enough for a red vertex to come after every blue vertex! So a Hamiltonian cycle cannot exist.
(Essentially, this argument works by showing that this triangulation is not $1$-tough, whereas all Hamiltonian graphs are $1$-tough. I suspected that this would be the case, since this is a common strategy to prove that graphs are not Hamiltonian. To find the set $\{1,3,5,7,9\}$ whose removal leaves $6$ connected components, I began by including some very high-degree vertices such as $1,3,5,9$, then noticed that one of the remaining components had three vertices only "held together" by vertex $7$. This is a guessing strategy, not an algorithm.)
We can use this idea to construct many more examples of locally Hamiltonian graphs which are not Hamiltonian. Start with any $3$-edge-connected planar graph $G$ which has more faces than vertices. Then, construct a triangulation $H$ by adding a new vertex in the middle of every face of $G$, and connecting it to every vertex along that face. (If $G$ is not $3$-edge-connected, then some faces visit a vertex multiple times, and this construction fails - either $H$ will not be a simple graph, or $H$ will not be a triangulation.) The example above can be constructed in this way, by taking $G$ to be the skeleton graph of the triangular bipyramid.
The same proof works to show that $H$ is not Hamiltonian, if we color each of the old vertices red, and each of the new vertices blue.