Three-edge-coloring (Tait coloring) cubic graphs on the torus: A proof of Grünbaum's conjecture

Yuta Inoue, Ken‐ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Tomohiro SonobearXiv 2025 · DOI · arXiv

TL;DR

This paper provides a definitive proof of a long-standing 1968 conjecture by Branko Grünbaum regarding the colorability of graphs on a torus. The authors demonstrate that almost all "cubic" (3-regular) graphs on the torus can be 3-edge-colored, with the only exceptions being a specific family of "Petersen-like" graphs.

What Problem Does This Paper Address?

In the world of graph theory, the Four Color Theorem is the most famous result, stating that any map on a plane can be colored with just four colors such that no two adjacent regions share a color. For "cubic" graphs (where every vertex has exactly three connections), this is equivalent to saying the edges can be colored with three colors (a Tait coloring).

However, when we move from a flat plane to a torus (a donut shape), the rules change. Some graphs that are embeddable on a torus cannot be 3-edge-colored; these are known as "snarks." In 1968, Grünbaum conjectured a specific structural condition that would identify these non-colorable graphs. This paper finally proves a strengthened version of that conjecture, providing a complete characterization of which toroidal cubic graphs are colorable and which are not.

Methods

The proof utilizes a sophisticated version of the discharging method, the same technique used to prove the Four Color Theorem. The process involves two main stages:

  1. Reducibility: The authors identify a set of "reducible configurations"—subgraphs that are guaranteed to appear in any potential counterexample but can be replaced by smaller subgraphs to simplify the problem. If the smaller graph is colorable, the original is too.
  2. Discharging: The authors assign an initial "charge" to vertices based on their degree. They then use "discharging rules" to move these charges around. If they can show that every vertex ends up with a non-positive charge, they create a contradiction that proves no counterexample can exist.

Because the torus has an Euler characteristic of zero (unlike the plane, which is two), the discharging process is significantly more complex. The authors had to handle "flat cases" where the total charge is zero and develop "annular configurations" to deal with cycles that wrap around the donut's holes.

Datasets

While not a traditional machine learning paper, the research relies on a massive "dataset" of mathematical structures:

  • Reducible Configurations: The authors generated and verified over 14,000 reducible configurations. For comparison, the original proof of the Four Color Theorem required about 600, and the projective plane version required about 5,700.
  • Computer Verification: The authors provided extensive source code (available on GitHub) to verify these configurations, ensuring the proof's robustness through automated checking.

Key Insights and Ideas

  • The Petersen Exception: The "Petersen graph" is the smallest snark. The authors show that all toroidal snarks are essentially built from the Petersen graph using a specific "dot product" operation.
  • Zero Euler Characteristic: The most significant hurdle was the torus's geometry. In planar proofs, the positive Euler characteristic provides a "surplus" of charge that makes finding a reducible configuration easier. On the torus, the authors had to prove that a reducible configuration exists even when the final charge of every vertex is exactly zero.
  • Annular Configurations: The authors introduced a new way to handle subgraphs that "wrap around" the torus, treating them as being embedded in an annulus (a cylinder) rather than a simple disk.

Key Results

  • Proof of Grünbaum’s Conjecture: Every cyclically 4-edge-connected cubic graph on the torus is 3-edge-colorable unless it is "Petersen-like."
  • Tutte 4-Flow Conjecture: The result provides a "very strong version" of Tutte’s 4-Flow Conjecture specifically for toroidal graphs, showing they admit a nowhere-zero 4-flow unless they are Petersen-like.
  • Algorithmic Efficiency: The authors derived a quadratic-time algorithm ($O(n^2)$) for 3-edge-coloring cubic graphs of genus one (toroidal graphs), which is a significant practical contribution to computational graph theory.

Limitations and Future Work

The primary limitation, common to proofs of this type, is the heavy reliance on computer verification for the 14,000+ configurations. While the logic is sound, a "human-only" proof remains out of reach due to the sheer volume of cases.

Future work could involve extending these techniques to surfaces with higher "genus" (more holes, like a double-donut). However, as the genus increases, the number of required configurations likely grows exponentially, suggesting that entirely new mathematical insights—rather than just more computing power—will be needed.

Summary updated

Abstract

We prove that every cyclically 4-edge-connected cubic graph that can be embedded in the torus, with the exceptional graph class called "Petersen-like", is 3-edge-colorable. This means every (non-trivial) toroidal snark can be obtained from several copies of the Petersen graph using the dot product operation. The first two snarks in this family are the Petersen graph and one of Blanuša snarks; the rest are exposed by Vodopivec in 2008. This proves a strengthening of the well-known, long-standing conjecture of Grünbaum from 1968. This implies that a 2-connected cubic (multi)graph that can be embedded in the torus is not 3-edge-colorable if and only if it can be obtained from a dot product of copies of the Petersen graph by replacing its vertices with 2-edge-connected planar cubic (multi)graphs. Here, replacing a vertex $v$ in a cubic graph $G$ is the operation that takes a 2-connected planar cubic multigraph $H$ and one of its vertices $u$ of degree 3, unifying $G-v$ and $H-u$ and connecting the neighbors of $v$ in $G-v$ with the neighbors of $u$ in $H-u$ with a matching. This result is a highly nontrivial generalization of the Four Color Theorem, and its proof requires a combination of extensive computer verification and computer-free extension of existing proofs on colorability. An important consequence of this result is a very strong version of the Tutte 4-Flow Conjecture for toroidal graphs. We show that a 2-edge connected graph embedded in the torus admits a nowhere-zero 4-flow unless it is Petersen-like (in which case it does not admit nowhere-zero 4-flows). Observe that this is a vast strengthening over the Tutte 4-Flow Conjecture on the torus, which assumes that the graph does not contain the Petersen graph as a minor because almost all toroidal graphs contain the Petersen graph minor, but almost none are Petersen-like.
BibTeX
@misc{inoue2025three,
  author = {Yuta Inoue and Ken‐ichi Kawarabayashi and Atsuyuki Miyashita and Bojan Mohar and Tomohiro Sonobe},
  title = {{Three-edge-coloring (Tait coloring) cubic graphs on the torus: A proof of Grünbaum's conjecture}},
  year = {2025},
  eprint = {2505.07002},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.07002},
  howpublished = {arXiv},
}

Loading related content...

Figure