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 and cyclic edge connectivity four, and another example (shown in the figure) with and cyclic edge connectivity five, the maximum possible cyclic edge connectivity for a cubic planar graph other In the example shown, all of the bounded faces have either five or eight edges, both of which are numbers that are but the unbounded face has nine edges, unequal to Therefore, by the corollary to Grinberg's theorem, the graph cannot be 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 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 faces from the other four, which is not 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 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 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,