Proof
(related to Lemma: Biconnectivity is a Necessary Condition for a Hamiltonian Graph)
Let \(G(V,E)\) be a simple graph \(G(V,E)\).
- It is obvious, that if \(G\) is disconnected, then it is not Hamiltonian, because it otherwise does not contain a Hamiltonian cycle.
- If \(G\) is only connected, but not at least biconnected, then it contains by definition cutvertices.
- In this case, it cannot contain a Hamiltonian cycle. Otherwise, every closed walk, which contains every vertex of \(G\), passes a cutvertex at least twice.
- By contraposition, if \(G\) is Hamiltonian, then it must be at least biconnected.
∎
Thank you to the contributors under CC BY-SA 4.0!
- Github:
-
References
Bibliography
- Piotrowski, Andreas: Own Research, 2014