Welcome guest
You're not logged in.
286 users online, thereof 0 logged in

Theorem: Characterization of Planar Hamiltonian Graphs

(Note that finding a Hamiltonian cycle is an NP-hard problem and there is much research going on to find theoretical results about finding not only necessary but also sufficient criteria for a graph to be Hamiltonian. The following theorem is one such research1591 result in providing a necessary and sufficient criterion for a planar graph to be Hamiltonian. The theorem is also the main motivation for defining the concept of minimal tree decomposability \(\tau(G)\) of a graph \(G\).)

For all simple planar connected graphs \(G\), the following equivalence holds: \(G\) is Hamiltonian, if and only if the minimal tree decomposability of every of its dual graphs equals \(2\), formally:

\[\text{Simple and planar }G:~G\text{ is Hamiltonian}\quad\Longleftrightarrow\quad \tau(G^*)=2\text{ for all dual graphs }G^*\text{ of }G.\]


The idea for this equivalence is illustrated in the following example:

new:branchcorollary:The 4-colors Problem and Planar Hamiltonian Graphs

Let $G$ be a simple planar which is also Hamiltonian. Then it can be colored in

| | | | | created: 2017-01-19 16:43:36 | modified: 2020-04-13 10:37:09 | by: bookofproofs | references: [1591]

1.Proof: (related to "Characterization of Planar Hamiltonian Graphs")

Edit or AddNotationAxiomatic Method

This work was contributed under CC BY-SA 4.0 by:

This work is a derivative of:

Bibliography (further reading)

[1591] Piotrowski, Andreas: “”, Own Work, 2014