Grinberg's theorem
In graph theory, Grinberg's theorem is a necessary condition for a planar graph to contain a Hamiltonian cycle, based on the lengths of its face cycles. If a graph does not meet this condition, it is not Hamiltonian. The result has been widely used to prove that certain planar graphs constructed to have additional properties are not Hamiltonian; for instance it can prove non-Hamiltonicity of some counterexamples to Tait's conjecture that cubic polyhedral graphs are Hamiltonian.
Grinberg's theorem - Wikipedia Jump to content From Wikipedia, the free encyclopedia On Hamiltonian cycles in planar graphs A graph that can be proven non-Hamiltonian using Grinberg's theorem In graph theory , Grinberg's theorem is a necessary condition for a planar graph to contain a Hamiltonian cycle , based on the lengths of its face cycles. If a graph does not meet this condition, it is not Hamiltonian. The result has been widely used to prove that certain planar graphs constructed to have additional properties are not Hamiltonian; for instance it can prove non-Hamiltonicity of some counte
related reading
- Hamiltonian path - Wikipediaen.wikipedia.org
- A simpler proof of the KPR theorem | tcs mathtcsmath.wordpress.com
- Hamiltonian path problem - Wikipediaen.wikipedia.org
- Steinitz's theorem - Wikipediaen.wikipedia.org
- Planar graph - Wikipediaen.wikipedia.org
- Ch12.pdfmath.uni-hamburg.de
- Schröder–Bernstein theorem - Wikipediaen.wikipedia.org
- Exact Stability for Turan's Theoremarxiv.org
- Kőnig's lemma - Wikipediaen.wikipedia.org
- random subgraphs rainbowarxiv.org
- Complete graph - Wikipediaen.wikipedia.org
- quasikernelarxiv.org