Proof
(related to Lemma: Dual Graph of a All Faces Contained in a Planar Hamiltonian Cycle is a Tree)
- 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
- Piotrowski, Andreas: Own Research, 2014