Three-edge-coloring apex cubic graphs
2026-08-24 • Computational Geometry
Computational GeometryDiscrete MathematicsData Structures and Algorithms
AI summaryⓘ
The authors prove that any 2-connected cubic graph that becomes planar after removing one vertex can be colored using only three colors on its edges without conflicts. This result completes the proof of a long-standing conjecture by Tutte from 1966. Their proof is constructive, meaning it provides a way to find such a coloring efficiently. They also verify their computer-based parts by having independent AI-assisted implementations reproduce the calculations to confirm reliability.
apex graphplanar graphcubic graphthree-edge-coloringTutte's conjectureFour Color Theoremdischarging methodreducibilitygraph coloringcomputational proof
Authors
Yuta Inoue, Ken-ichi Kawarabayashi, Rintaro Matsuo, Atsuyuki Miyashita, Bojan Mohar, Tomohiro Sonobe
Abstract
A graph $G$ is \emph{apex} if $G$ has a vertex $v$ such that $G-v$ is planar. We prove that every $2$-connected apex cubic graph is three-edge-colorable. This result gives the final piece of the proof for the well-known Tutte's three-edge-coloring conjecture from 1966 \cite{tutte}. The proof, as well as the result, generalizes that of the Four Color Theorem, which requires computer checks. As in the previous proof of the Four Color Theorem, the proof is constructive. More precisely, given a $2$-connected apex cubic graph $G$ on $n$ vertices, our reducibility and discharging procedure yields a three-edge-coloring of $G$ in $O(n^2)$ time. As an additional reproducibility check for our computer checks, independent implementations reconstructed from the detailed pseudocode (given in the appendix) using generative AI systems reproduced the required computational results. These reconstructions are not part of the mathematical justification of the theorem, but provide additional evidence for the reproducibility of the computations.