Grinberg's theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
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. The result has been widely used to construct non-Hamiltonian planar graphs with further properties, such as to give new counterexamples to Tait's conjecture (originally disproved by W.T. Tutte in 1946). This theorem was proved by Latvian mathematician Emanuel Grinberg in 1968.

Precise formulation[edit]

Let G be a finite plane graph with a Hamiltonian cycle C. Denote by ƒk and gk the number of k-gonal faces inside and outside of C, respectively. Then

\sum_{k \geq 3} (k-2) (f_k-g_k) = 0.

The proof is an easy consequence of Euler's formula.

Applications[edit]

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 that may be deleted in such a way that the remaining graph has 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 44 vertices, 24 faces, and cyclic edge connectivity four, and another example (shown in the figure) with 46 vertices, 25 faces, and cyclic edge connectivity five, the maximum possible cyclic edge connectivity for a cubic planar graph other than K4. In the example shown, all of the bounded faces have either five or eight edges, and therefore (because of the factor of k − 2 in the sum) they contribute zero modulo 3 to the sum in Grinberg's theorem, regardless of whether they are inside or outside of any Hamiltonian cycle C. The unbounded face, however, has nine edges, and contributes a nonzero term modulo three to the sum. Therefore, the overall summation has a value that is nonzero modulo three, and Grinberg's theorem implies that the graph cannot be Hamiltonian.

Grinberg's theorem has also been used to find planar hypohamiltonian graphs, again by making all but one face have a number of edges congruent to 2 mod 3 (Thomassen 1976, Wiener & Araya 2009). Thomassen (1981) 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 4- or 7-edge faces from the other four, which is not possible.

Limitations[edit]

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 case (Zaks 1977).

It is not possible to use Grinberg's theorem to find counterexamples to Barnette's conjecture, that every cubic bipartite polyhedral graph is Hamiltonian. For, in such graphs, there always exists a partition of the faces into two subsets satisfying Grinberg's theorem, regardless of Hamiltonicity (Krooss 2004).

References[edit]

External links[edit]