◀ ▲ ▶Branches / Graph-theory / Lemma: Dual Graph of a All Faces Contained in a Planar Hamiltonian Cycle is a Tree

Lemma: Dual Graph of a All Faces Contained in a Planar Hamiltonian Cycle is a Tree

Let \(G(V,E)\) be a simple, planar, and Hamiltonian graph with \(n\) vertices. In any planar drawing \(\mathcal D\) of \(G\) let \(G^\ast_{\mathcal D}\) be the corresponding dual graph. Furthermore, let \(C^n\) be a Hamiltonian cycle drawn in \(\mathcal D\) and let \(v_1,\ldots v_m\) be exactly those vertices of \(G^\ast_{\mathcal D}\), which are enclosed by \(C_n\) in \(\mathcal D\). Then the subgraph induced in \(G^\ast_{\mathcal D}\) by these vertices, i.e. the graph \(G^\ast_{\mathcal D}[v_1,\ldots v_m]\) is always a tree.

Table of Contents

Proofs: 1

Mentioned in:

Proofs: 1

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

Github:

References

Bibliography

1. Piotrowski, Andreas: Own Research, 2014