Grinberg's theorem

Key takeaways

Grinberg's theorem belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Grinberg's theorem to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Grinberg's theorem from memory before moving on to harder problems.

Reference excerpt

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 k {\displaystyle k} -gon if its boundary is formed by a cycle of k {\displaystyle k} vertices and k {\displaystyle k} edges of the graph drawing. A Hamiltonian cycle in a graph is a cycle that passes through each vertex exactly once. Let G {\displaystyle G} be a finite planar graph with a Hamiltonian cycle C {\displaystyle C} , with a fixed planar drawing. By the Jordan curve theorem, C {\displaystyle C} separates the plane into the subset inside of C {\displaystyle C} and the subset outside of C {\displaystyle C} ; every face belongs to one of these two subsets. Denote by f k {\displaystyle f_{k}} and g k {\displaystyle g_{k}} the number of k {\displaystyle k} -gonal faces of the drawing that are inside and outside of C {\displaystyle C} , respectively. Then Grinberg's theorem states that

∑ k ≥ 3 ( k − 2 ) ( f k − g k ) = 0. {\displaystyle \sum _{k\geq 3}(k-2)(f_{k}-g_{k})=0.}

The proof is an easy consequence of Euler's formula. As a corollary of this theorem, if an embedded planar graph has only one face whose number of sides is not 2 mod 3, and the remaining faces all have numbers of sides that are 2 mod 3, 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 f k {\displaystyle f_{k}} and g k {\displaystyle g_{k}} . Each face whose number of sides is 2 mod 3 contributes a multiple of three to the sum, because of the factor k − 2 {\displaystyle k-2} 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 cycle. For instance, for the graph in the figure, all the bounded faces have 5 or 8 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 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 K 4 {\displaystyle K_{4}} . In the example shown, all of the bounded faces have either five or eight edges, both of which are numbers that are 2 mod 3, but the unbounded face has nine edges, unequal to 2 mod 3. Therefore, by the corollary to Grinberg's theorem, the graph cannot be Hamiltonian. 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 2 mod 3. 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. 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 subgraphs.

… excerpt ends here. Continue reading the full article.

Illustrations

Worked examples

Example 1 — a first encounter with Grinberg's theorem

Start with the simplest possible case. Write down what Grinberg's theorem claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Grinberg's theorem before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Grinberg's theorem ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Grinberg's theorem

In research: Grinberg's theorem appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Grinberg's theorem in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Grinberg's theorem is common in secondary-school and first-year university syllabi. It links to neighbouring topics Hamiltonian paths and cycles, Statements about planar graphs, Theorems in graph theory, so understanding it makes those chapters shorter.
In everyday life: Look for Grinberg's theorem outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Grinberg's theorem in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Grinberg's theorem means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Grinberg's theorem out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Grinberg's theorem in simple terms?

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.

Why does Grinberg's theorem matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Grinberg's theorem?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Grinberg's theorem.