Английская Википедия: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 is named after Latvian mathematician Emanuel Grinberg, who proved it in 1968.
Formulation
A planar graph is a graph that can be drawn without crossings in the Euclidean plane. If the points belonging to vertices and edges are removed from the plane, the connected components of the remaining points form polygons, called faces, including an unbounded face extending to infinity. A face is a Шаблон:Nowrap if its boundary is formed by a cycle of Шаблон:Nowrap and Шаблон:Nowrap of the graph drawing. A Hamiltonian cycle in a graph is a cycle that passes through each vertex exactly once. Let <math>G</math> be a finite planar graph with a Hamiltonian Шаблон:Nowrap with a fixed planar drawing. By the Jordan curve theorem, <math>C</math> separates the plane into the subset inside Шаблон:Nowrap and the subset outside Шаблон:Nowrap every face belongs to one of these two subsets. Denote by <math>f_k</math> and <math>g_k</math> the number of Шаблон:Nowrap faces of the drawing that are inside and outside Шаблон:Nowrap respectively. Then Grinberg's theorem states that <math display=block>\sum_{k \geq 3} (k-2) (f_k-g_k) = 0.</math> The proof is an easy consequence of Шаблон:Nowrap
As a corollary of this theorem, if an embedded planar graph has only one face whose number of sides is not Шаблон:Nowrap and the remaining faces all have numbers of sides that are Шаблон:Nowrap then the graph is not Hamiltonian. To see this, consider a sum of the form given in the statement of the theorem, for an arbitrary partition of the faces into two subsets, counted by numbers <math>f_k</math> Шаблон:Nowrap Each face whose number of sides is Шаблон:Nowrap contributes a multiple of three to the sum, because of the factor <math>k-2</math> in the term to which it contributes, while the one remaining face does not. Therefore, the sum is not a multiple of three, and in particular is not zero. Since there is no way of partitioning the faces into two subsets that produce a sum obeying Grinberg's theorem, there can be no Hamiltonian Шаблон:Nowrap For instance, for the graph in the figure, all the bounded faces have Шаблон:Nowrap sides, but the unbounded face has 9 sides, so it satisfies this condition on numbers of sides and is not Hamiltonian.
Applications
Grinberg used his theorem to find non-Hamiltonian cubic polyhedral graphs with high cyclic edge connectivity. The cyclic edge connectivity of a graph is the smallest number of edges whose deletion leaves a subgraph with more than one cyclic component. The 46-vertex Tutte graph, and the smaller cubic non-Hamiltonian polyhedral graphs derived from it, have cyclic edge connectivity three. Grinberg used his theorem to find a non-Hamiltonian cubic polyhedral graph with Шаблон:Nowrap Шаблон:Nowrap and cyclic edge connectivity four, and another example (shown in the figure) with Шаблон:Nowrap Шаблон:Nowrap and cyclic edge connectivity five, the maximum possible cyclic edge connectivity for a cubic planar graph other Шаблон:Nowrap In the example shown, all of the bounded faces have either five or eight edges, both of which are numbers that are Шаблон:Nowrap but the unbounded face has nine edges, unequal to Шаблон:Nowrap Therefore, by the corollary to Grinberg's theorem, the graph cannot be Шаблон:Nowrap
Grinberg's theorem has also been used to find planar hypohamiltonian graphs, graphs that are not Hamiltonian but that can be made Hamiltonian by removing any single vertex. The construction again makes all but one face have a number of edges congruent to Шаблон:Nowrap Шаблон:Harvtxt uses the theorem in a somewhat more complicated way to find a planar cubic hypohamiltonian graph: the graph he constructs includes a 4-edge face adjacent to four 7-edge faces, and all other faces have five or eight edges. In order to satisfy Grinberg's theorem, a Hamiltonian cycle would have to separate one of the Шаблон:Nowrap faces from the other four, which is not Шаблон:Nowrap
It can also be applied to analyze the Hamiltonian cycles of certain non-planar graphs, such as generalized Petersen graphs, by finding large planar subgraphs of these graphs, using Grinberg's theorem to show that these subgraphs are non-Hamiltonian, and concluding that any Hamiltonian cycle must include some of the remaining edges that are not part of these Шаблон:Nowrap
Limitations
There exist planar non-Hamiltonian graphs in which all faces have five or eight sides. For these graphs, Grinberg's formula taken modulo three is always satisfied by any partition of the faces into two subsets, preventing the application of his theorem to proving non-Hamiltonicity in this Шаблон:Nowrap
It is not possible to use Grinberg's theorem to find counterexamples to Barnette's conjecture, that every cubic bipartite polyhedral graph is Hamiltonian. Every cubic bipartite polyhedral graph has a partition of the faces into two subsets satisfying Grinberg's theorem, regardless of whether it also has a Hamiltonian Шаблон:Nowrap
Notes
References
- Шаблон:Citation
- Шаблон:Citation; English translation by Dainis Zeps, Шаблон:Arxiv
- Шаблон:Citation
- Шаблон:Citation
- Шаблон:Citation
- Шаблон:Citation
- Шаблон:Citation
- Шаблон:Citation
External links
- Grinberg Graphs, from MathWorld.
