Grinberg's theorem
id:
grinberg-s-theorem-290-12557507
title:
Grinberg's theorem
text:
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 theore
brand slug:
wiki
category slug:
encyclopedia
description:
On Hamiltonian cycles in planar graphs
original url:
https://en.wikipedia.org/wiki/Grinberg%27s_theorem
date created:
date modified:
2023-01-28T18:58:43Z
main entity:
{"identifier":"Q5609384","url":"https://www.wikidata.org/entity/Q5609384"}
image:
{"content_url":"https://upload.wikimedia.org/wikipedia/commons/c/c7/Grinberg_5CEC_Nonhamiltonian_graph.svg","width":429,"height":429}
fields total:
13
integrity:
15