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
Explore this link on the map →related reading
- Hamiltonian path - Wikipediaen.wikipedia.org
- Planar graph - Wikipediaen.wikipedia.org
- claude-cycles.dviwww-cs-faculty.stanford.edu
- random subgraphs rainbowarxiv.org
- Steinitz's theorem - Wikipediaen.wikipedia.org
- nullstellensatzweb.math.princeton.edu
- [2004.10180] The regularity method for graphs with few 4-cyclesarxiv.org
- Rainbow Turán Problemspeople.math.ethz.ch
- rainbow-turan-full-version.pdfpeople.maths.ox.ac.uk
- Hamiltonian path problem - Wikipediaen.wikipedia.org
- Cubic graph - Wikipediaen.wikipedia.org
- parity edge coloringmilans.us