# Proof

• Assume, $$G(V,E)$$ is a simple, planar, and Hamiltonian graph with $$n$$ vertices.
• Take any planar drawing $$\mathcal D$$ of $$G$$.
• Construct the corresponding dual graph $$G^\ast_{\mathcal D}$$.
• Draw the Hamiltonian cycle $$C^n$$ of $$G$$ in $$\mathcal D$$ and identify vertices $$v_1,\ldots v_m$$ of $$G^\ast_{\mathcal D}$$, which are enclosed by $$C_n$$ in $$\mathcal D$$.
• We claim that the subgraph induced in $$G^\ast_{\mathcal D}$$ by those vertices, i.e. the graph $$G^\ast_{\mathcal D}[v_1,\ldots v_m]$$ is always a tree. Proof by contradiction:
• Assume, $$G^\ast_{\mathcal D}[v_1,\ldots v_m]$$ is not a tree.
• Then it contains at least one cycle, say $$C_k^\ast$$.
• Therefore, the drawing of $$C_k^\ast$$ inside the planar drawing $$D$$ contains at least one face, since either $$C_k^\ast$$ is a face itself, or it has some chords forming a face. Denote this face by $$f^\ast$$.
• By definition of the dual graph $$G^\ast_{\mathcal D}$$, there must be a vertex $$w$$ of $$G$$ inside the face $$f^\ast$$ we find in the planar drawing of the cyclic subgraph $$G^*_{\mathcal D}[v_1,\ldots v_m]$$.
• But $$w\in f^\ast$$ cannot be contained in the Hamiltonian cycle $$C^n$$, since $$C^n$$ surrounds the hole subgraph subgraph $$G^\ast_{\mathcal D}[v_1,\ldots v_m]$$, and thus is not adjacent to $$w$$.
• This a contradiction to the hypothesis that $$C^n$$ is a Hamiltonian cycle.
• Therefore, $$G^\ast_{\mathcal D}[v_1,\ldots v_m]$$ must be a tree.

Thank you to the contributors under CC BY-SA 4.0!

Github:

### References

#### Bibliography

1. Piotrowski, Andreas: Own Research, 2014