Grinberg's theorem
Encyclopedia
In graph theory
, Grinberg's theorem is a necessary condition on the planar graph
to contain a Hamiltonian cycle. The result has been widely used to construct non-Hamiltonian planar graphs with further properties, such as to give new counterexample
s to Tait's conjecture
(originally disproved by W.T. Tutte in 1946). This theorem was proved by a Latvia
n mathematician
Emanuel Grinberg in 1968.
Denote by ƒk and gk the number of k-gonal faces inside and outside of C, respectively. Then
The proof is an easy consequence of Euler's formula
.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, Grinberg's theorem is a necessary condition on the planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
to contain a Hamiltonian cycle. The result has been widely used to construct non-Hamiltonian planar graphs with further properties, such as to give new counterexample
Counterexample
In logic, and especially in its applications to mathematics and philosophy, a counterexample is an exception to a proposed general rule. For example, consider the proposition "all students are lazy"....
s to Tait's conjecture
Tait's conjecture
In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle through all its vertices". It was proposed by and disproved by , who constructed a counterexample with 25 faces, 69 edges and 46 vertices...
(originally disproved by W.T. Tutte in 1946). This theorem was proved by a Latvia
Latvia
Latvia , officially the Republic of Latvia , is a country in the Baltic region of Northern Europe. It is bordered to the north by Estonia , to the south by Lithuania , to the east by the Russian Federation , to the southeast by Belarus and shares maritime borders to the west with Sweden...
n mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
Emanuel Grinberg in 1968.
Precise formulation
Let G be a finite planar graph with a Hamiltonian cycle C.Denote by ƒk and gk the number of k-gonal faces inside and outside of C, respectively. Then
The proof is an easy consequence of Euler's formula
Euler characteristic
In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic is a topological invariant, a number that describes a topological space's shape or structure regardless of the way it is bent...
.
External links
- Grinberg Graphs, from MathWorldMathWorldMathWorld is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by and licensed to Wolfram Research, Inc. and was partially funded by the National Science Foundation's National Science Digital Library grant to the University of Illinois at...
.