Pith. sign in

REVIEW 3 major objections 5 minor 32 references

Three-edge-coloring apex cubic graphs

T0 review · 3 major / 5 minor · reviewed 2026-08-28 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every 2-connected apex cubic graph is three-edge-colorable, and this completes the proof of Tutte's three-edge-coloring conjecture.

desk verdict If the computer checks hold up, this completes Tutte's three-edge-coloring conjecture; the proof is serious and the computational transparency is above average, but the cartwheel-search gap needs an independent audit. read the letter →

arxiv 2608.22870 v1 pith:COR2U6RQ submitted 2026-08-24 math.CO cs.CGcs.DMcs.DS

Yuta Inoue , Ken-ichi Kawarabayashi , Rintaro Matsuo , Atsuyuki Miyashita , Bojan Mohar , Tomohiro Sonobe This is my paper · ORCID
classification math.COcs.CGcs.DMcs.DS
keywords apexproofcubicgraphtheoremthree-edge-coloringadditionalchecks
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

A cubic graph is a graph where exactly three edges meet at every vertex. Edge-coloring with three colors means assigning a color to each edge so that no two edges meeting at the same vertex share a color. Cubic graphs with such a coloring are related to nowhere-zero 4-flows, and Tutte conjectured in 1966 that every 2-connected cubic graph without the Petersen graph as a minor can be three-edge-colored. Robertson, Seymour and Thomas reduced that conjecture in 1997 to two graph classes: doublecross graphs and apex graphs. The doublecross case was published in 2016, while the apex case had been announced but never written down. This paper supplies the missing apex case.

An apex graph becomes planar after deleting one vertex. The authors delete that vertex and work with the remaining planar subcubic graph and its planar dual, which looks like a triangulation with two or three digons (faces of length two). They prove two main facts by discharging: every minimal counterexample must contain one of 915 listed configurations, and every listed configuration is reducible, meaning it can be replaced by a smaller graph without changing non-colorability. Together these contradict minimality.

This is a computer-assisted proof. The discharge rules and reducibility checks are encoded in detailed pseudocode and source code on GitHub, and the authors report that two generative-AI systems independently re-implemented the checks from the pseudocode and reproduced the computational results. The theorem also gives a concrete O(n^2) algorithm for actually finding a three-edge-coloring of a 2-connected apex cubic graph.

Extended reading notes

Core claim

Theorem 1.4: Every 2-connected apex cubic graph is three-edge-colorable. If this theorem is correct, then together with Theorem 1.3 of Robertson-Seymour-Thomas and the doublecross result of Edwards-Sanders-Seymour-Thomas, it proves Tutte's three-edge-coloring conjecture for all 2-connected cubic graphs without a Petersen minor, and it yields an O(n^2)-time algorithm for the apex case.

Load-bearing premise

The load-bearing premise is the correctness and completeness of the computer-assisted verification. Lemmas B.1, B.2, and B.3 establish that combined discharging rules not blocked by the configuration set K have charge at most 5, that the cartwheel search for degrees 7 through 11 finds no counterexample, and that every island in the constructed family I is semi-reducible. These lemmas are established by running the provided algorithms, and the manuscript gives pseudocode and GitHub code but no formal machine-checked certificate and no pinned commit hash. An error in the implementation or in the pseudocode-to-code correspondence would collapse the discharging and reducibility argument even if the surrounding handwritten lemmas are correct. See Section 6.2, Section 6.3.3, and Section 7.1, with the computational lemmas stated as Lemma B.1, Lemma B.2, and Lemma B.3.

Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

  1. Claim #1: Theorem 1.4: Every 2-connected apex cubic graph is three-edge-colorable. If this theorem is correct, then together with Theorem 1.3 of Robertson-Seymour-Thomas and the doublecross result of Edwards-Sanders-Seymour-Thomas, it proves Tutte's three-edge-coloring conjecture for all 2-connected cubic graphs without a Petersen minor, and it yields an O(n^2)-time algorithm for the apex case.

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proves Theorem 1.4: every 2-connected apex cubic graph is three-edge-colorable. Since Robertson–Seymour–Thomas (Theorem 1.3) reduce Tutte's three-edge-coloring conjecture for all 2-connected cubic graphs without a Petersen minor to the doublecross and apex cases, and the doublecross case was already established by Edwards–Sanders–Seymour–Thomas, the paper claims to complete the proof of Tutte's conjecture. The proof follows the RSST97 paradigm: a minimal counterexample is reduced to a planar subcubic graph G whose dual G* is a triangulation with two or three digons; a set K of 915 normal configurations is used with a discharging system consisting of the 32 rules of RSST97 plus three new digon-handling rules. The discharging argument establishes that some configuration in K appears in G* (Theorem 6.7), and the reducibility argument establishes that this configuration yields a semi-reducible multi-boundary island in G (Theorem 7.1). Three computational lemmas are load-bearing: Lemma B.1 (free discharging combinations not blocked by K transfer charge at most 5), Lemma B.2 (the degree 7–11 cartwheel search finds no bad local structure), and Lemma B.3 (every island in the generated set I is semi-D- or semi-C-reducible). The appendix contains detailed pseudocode, and the authors provide GitHub code and independent AI-based reimplementations, explicitly stating that the AI reconstructions are not part of the mathematical justification.

Significance. If Theorem 1.4 is correct, this is a landmark result: it completes Tutte's three-edge-coloring conjecture and, with it, the long-standing classification of 3-edge-colorability for 2-connected cubic graphs without a Petersen minor. The proof framework is a genuine generalization of the RSST97 discharging and reducibility program to graphs with digons, and the manuscript is unusually transparent about its computational dependencies: it provides detailed pseudocode, source-code links, an explicit list of the auxiliary rules, and even reports an independent reproducibility check by generative-AI systems. The mathematical narrative is coherent, the structural lemmas are carefully written, and the proof does not appear to assume the target theorem; it relies instead on the Four Color Theorem, the RST97 reduction, ESST16's doublecross theorem, and the authors' own previously published algorithms. The main weakness is that the three computational lemmas are certified only by running custom software, with no pinned commit, no machine-readable certificates, and no formal proof of pseudocode-to-code correspondence.

major comments (3)
  1. [Section 6.2 / Lemma B.1] The claim that every free combination of discharging rules not blocked by K transfers charge at most 5 (Lemma B.1, supporting Lemma 6.5) is an assertion about the output of custom software. The manuscript gives pseudocode and a GitHub URL but no pinned commit hash, no machine-readable certificate, and no formalization of the algorithms. A single bug in the free-homomorphism routine, the pruning of combined rules, or the enforcement of single digon incidence would invalidate Lemma 6.5 and hence the discharging proof of Theorem 6.7 even if all handwritten lemmas are correct. I recommend that the authors provide a version-pinned source snapshot with output hashes, and ideally machine-checkable certificates or a formally verified implementation of Lemmas 6.9–6.12 and the final combinatorial check.
  2. [Section 6.3.3 / text after Algorithm B.3.16] The degree 7–11 cartwheel search is certified by Lemma B.2, which is exactly the assertion that the assertion in Algorithm B.3.15 does not fail in every call. Yet the manuscript states, immediately after Algorithm B.3.16, that the authors 'do not have source code that implements Algorithm B.3.16 literally' and instead used a shell script to loop over cartwheels. This breaks the pseudocode-to-code correspondence for the key check that establishes Lemma 6.17 and hence Lemma 6.6. The authors should either provide a literal implementation of Algorithm B.3.16, give a formal argument that the shell-script loop is equivalent to lines 3–5, or supply a hand-checkable certificate of the cartwheel search. Without this, Lemma 6.6 is not independently verifiable from the manuscript.
  3. [Section 7.1 / Lemma B.3] Lemma 7.5, which asserts that every multi-boundary island in I is semi-D- or semi-C-reducible, is backed only by the software described in Appendix B.4 and Lemma B.3. The reducibility checker must handle half-chains, all ring colorings beyond the usual parity-restricted set, and the full enumeration of deletable edge sets; these are exactly the places where an implementation error could go unnoticed. Because Theorem 7.1 and hence Theorem 1.4 depend on Lemma 7.5, the manuscript should include a machine-checkable certificate from the checker (for example, a witness semi-consistent set for each island, or a formally verified checker), or an independent deterministic reimplementation that is included in the mathematical justification rather than merely as a reproducibility aid.
minor comments (5)
  1. [General / GitHub reproducibility] The GitHub repositories should be described with pinned commit hashes, the software environment and dependencies, and SHA-256 or similar hashes of the generated data files and outputs, so that the reader can reproduce the exact results claimed in Lemmas B.1–B.3.
  2. [Section 1.1] In the sentence 'since G has two 6 or three vertices of degree two', the '6' appears to be a typographical artifact; the intended statement is presumably 'two or three vertices of degree two'.
  3. [Section 6.2] The notation R for the rule set and R_e for the set of rules applied to a dart e is clear in context, but the simultaneous use of R for a single rule and for the rule set in Definition 6.1 and Lemma 6.5 may confuse readers; a distinct symbol for the rule set, such as Script-R, would improve readability.
  4. [Section 7.1 / Algorithm B.4.1] The text says 'We add a footnote in this part of the algorithm,' but no footnote is present in the arXiv text; either include the footnote or remove the parenthetical reference to it.
  5. [Section 8 / formatting] The complexity expression 'Opn 2q' should be typeset as O(n^2) to match standard notation; this is a purely presentational issue.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the apex-coloring theorem is derived from independent discharging and reducibility checks plus external theorems; computational reproducibility gaps are not circularity.

full rationale

The paper's derivation chain is not circular. Theorem 1.4 is proved by contradiction from a minimal counterexample, using external results (4CT, RST97's reduction Theorem 1.3, ESST16's doublecross theorem) and two independent internal pillars: unavoidability (Theorem 6.7, via Lemmas 6.3, 6.5, 6.6) and reducibility (Theorem 7.1, via Lemma 7.5 and Lemmas 3.7, 3.10). The discharging set K and rule set R are selected, not derived from the target statement; their two required properties are each verified computationally or by hand after the fact. No fitted parameter is renamed as a prediction, and no uniqueness theorem from the authors' prior work is invoked to force a choice. The main caveats are correctness/reproducibility concerns: Lemmas B.1–B.3 are outputs of custom software, the text admits Algorithm B.3.16 is not implemented literally but run via a shell script, and no pinned commit or machine-checked certificate is given. Additionally, the paper relies on algorithmic correctness lemmas from the authors' prior [IKM'26] work (e.g., 'The proof in [IKM `26] with the above observation leads to the following lemma,' Lemma 6.9). However, that cited work does not presuppose the apex three-edge-coloring theorem, and the current paper supplies pseudocode and source links for independent checking. Such reliance affects verification confidence, not circular equivalence of the stated result with its inputs.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

No new physical entities are postulated. The free parameters are hand-designed combinatorial choices in the discharging framework: the charge scale, digon constants, the rule set, and the configuration set. The main unproved external inputs are the Four Color Theorem, the RST97 reduction, and the ESST16 doublecross theorem; the remaining load-bearing assumption is the correctness of the large computer checks.

free parameters (4)
  • Initial charge coefficient 10 = 10
    The charge function T0(v)=10(6-d(v)) is chosen by hand so that total charge is 60 or 80 and the discharging inequalities work.
  • Digon charge constants in Lemma 6.6 = 4, 5, 3, 2, 0 (cases i-iv)
    Hand-tuned per-digon constants assigned to vertices near digons; the proof requires the sum of these constants per digon to be below 20.
  • Discharging rule set R = 35 rules: 32 from RSST97 plus 3 new digon rules
    The set of rules is ad hoc and specifically designed so that Lemma 6.8 and the computer checks succeed.
  • Configuration set K = 915 normal configurations
    The unavoidable configuration set is hand-constructed from ESST16 configurations plus digon variants; all the discharging and reducibility arguments depend on this particular set.
assumptions (4)
  • standard math Four Color Theorem
    Used in Claim 3.14 to color bridgeless planar cubic components, and in Appendix A to show certain auxiliary planar graphs are colorable.
  • domain assumption RST97 reduction theorem (Theorem 1.3)
    The paper relies on the published result that Tutte's three-edge-coloring conjecture follows from the doublecross and apex cases.
  • domain assumption ESST16 doublecross theorem
    The other half of the reduction; also used in Appendix A when auxiliary single-cross graphs are asserted to be colorable.
  • ad hoc to paper Correctness of computer programs for Lemmas B.1-B.3
    The proof of Theorem 6.7 and Theorem 7.1 depends on these computational results and on the pseudocode-code correspondence; no formal machine-checked certificate is supplied.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Three-edge-coloring apex cubic graphs." pith.science (2026). https://pith.science/paper/COR2U6RQ

@misc{pith2026260822870,
  author       = {Pith},
  title        = {Pith review of: Three-edge-coloring apex cubic graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/COR2U6RQ}},
  note         = {Machine review of arXiv:2608.22870}
}
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.

Figures

Figures reproduced from arXiv: 2608.22870 by the authors.

Figure 1
Figure 1. An example of a configuration and its completion where every face is a triangle [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 3
Figure 3. The left figure: a configuration (dotted lines represent edges between the configuration and its [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. The domino graph These structures are illustrated in [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figures from the paper (11 more)
Figure 5
Figure 5. Figure 5: Tiny disks. The figure on the right represents a domino in [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]
Figure 7
Figure 7. Figure 7: An example of a multi-boundary island with two faces in FRpIq Definition 3.2 (appear). Let I be a multi-boundary island and G be a 2-connected subcubic plane graph. We say that I appears in G if I ´ ERpIq is a subgraph of G and every vertex whose degree is two or three…
Figure 8
Figure 8. Figure 8: The shape of vertices For a multi-boundary configuration K, we define a plane graph Kp as follows. Start with GpKq. For each directed edge e P D, let v “ headpeq, and let e ` be the directed edge immediately following e in the same clockwise boundary walk. Thus e ` has…
Figure 9
Figure 9. Figure 9: The rules used in [RSST97] (also in [ESST16]). [PITH_FULL_IMAGE:figures/full_fig_p019_9.png]
Figure 10
Figure 10. Figure 10: The new rules Rp33q, Rp34q, and Rp35q in R. A double line represents a pair of parallel edges that bound a digon. For a dart e in G˚, let Re Ď R be the set of rules applied to e, and define rpeq by the sum of rpRq for R P Re. This value is also called the amount of ch…
Figure 11
Figure 11. Figure 11: The subset of configurations Kp1q–Kp19q in K. (4) Ip5q “ Op7q, (5) Ip33q “ Op34q, and (6) Ip34q “ Op35q holds. Proof. Let e1, . . . , ed (d “ 5 or 6) be darts whose head is v in clockwise order in the embedding. Recall that for each non-symmetric rule in [PITH_FULL_I…
Figure 12
Figure 12. Figure 12: The right three rules, denoted by R1 aux,27, R2 aux,27, R3 aux,27 form a homomorphic cover of the left rule Raux,27 [PITH_FULL_IMAGE:figures/full_fig_p033_12.png]
Figure 13
Figure 13. Figure 13: The right three rules, denoted by R1 aux,31, R2 aux,31, R3 aux,31 form a homomorphic cover of the left rule Raux,31. We denote them by R. 33 [PITH_FULL_IMAGE:figures/full_fig_p033_13.png]
Figure 14
Figure 14. Figure 14: All possible GA ij , GB ij , excluding rotational symmetry [PITH_FULL_IMAGE:figures/full_fig_p044_14.png]
Figure 15
Figure 15. Figure 15: All possible GC ij , GD ij,kl, excluding rotational symmetry. The drawings of the graphs can be seen in [PITH_FULL_IMAGE:figures/full_fig_p044_15.png]
Figure 16
Figure 16. Figure 16: This is non-colorable because the coloring graph of the domino is the same as [PITH_FULL_IMAGE:figures/full_fig_p046_16.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

  1. [1]

    2001 , PAGES =

    Mohar, Bojan and Thomassen, Carsten , TITLE =. 2001 , PAGES =

    work page 2001

  2. [2]

    1969 , PAGES =

    Heesch, Heinrich , TITLE =. 1969 , PAGES =

    work page 1969

  3. [3]

    , TITLE =

    Steinberger, John P. , TITLE =. Trans. Amer. Math. Soc. , FJOURNAL =. 2010 , NUMBER =. doi:10.1090/S0002-9947-2010-05092-5 , URL =

    work page doi:10.1090/s0002-9947-2010-05092-5 2010

  4. [4]

    Allaire, Frank and Swart, Edward Reinier , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 1978 , NUMBER =. doi:10.1016/0095-8956(78)90010-2 , URL =

    work page doi:10.1016/0095-8956(78)90010-2 1978

  5. [5]

    Whitney, Hassler and Tutte, W. T. , TITLE =. Utilitas Math. , FJOURNAL =. 1972 , PAGES =

    work page 1972

  6. [6]

    1989 , PAGES =

    Appel, Kenneth and Haken, Wolfgang , TITLE =. 1989 , PAGES =. doi:10.1090/conm/098 , URL =

    work page doi:10.1090/conm/098 1989

  7. [7]

    and Haken, W

    Appel, K. and Haken, W. and Koch, J. , TITLE =. Illinois J. Math. , FJOURNAL =. 1977 , NUMBER =

    work page 1977

  8. [8]

    and Haken, W

    Appel, K. and Haken, W. , TITLE =. Illinois J. Math. , FJOURNAL =. 1977 , NUMBER =

    work page 1977

Show all 32 references
  1. [9]

    , TITLE =

    Birkhoff, George D. , TITLE =. Amer. J. Math. , FJOURNAL =. 1913 , NUMBER =

    1913

  2. [10]

    Robertson, Neil and Sanders, Daniel and Seymour, Paul and Thomas, Robin , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 1997 , NUMBER =

    1997

  3. [11]

    Hopcroft and Robert Endre Tarjan , title =

    John E. Hopcroft and Robert Endre Tarjan , title =. J. 1974 , url =. doi:10.1145/321850.321852 , timestamp =

    1974

  4. [12]

    Graph Coloring Problems , author=

  5. [13]

    Franklin, Philip , TITLE =. Amer. J. Math. , FJOURNAL =. 1922 , NUMBER =

    1922

  6. [14]

    Sanders and Paul Seymour and Robin Thomas , keywords =

    Katherine Edwards and Daniel P. Sanders and Paul Seymour and Robin Thomas , keywords =. Three-edge-colouring doublecross cubic graphs , journal =. 2016 , issn =. doi:https://doi.org/10.1016/j.jctb.2015.12.006 , url =

    2016 doi

  7. [15]

    The American Mathematical Monthly , volume=

    Infinite families of nontrivial trivalent graphs which are not Tait colorable , author=. The American Mathematical Monthly , volume=. 1975 , publisher=

    1975

  8. [16]

    Inoue, Yuta and Kawarabayashi, Ken-ichi and Miyashita, Atsuyuki and Mohar, Bojan and Sonobe, Tomohiro , title =. FOCS'24. ArXiv:2405.16586 , year =

    arXiv

  9. [17]

    Robertson, Neil and Seymour, Paul and Thomas, Robin , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 1997 , NUMBER =

    1997

  10. [18]

    Ars Combin

    Tait’s theorem for graphs with crossing number at most one , author=. Ars Combin. , volume=

  11. [19]

    and Seymour, Paul and Thomas, Robin , TITLE =

    Robertson, Neil and Sanders, Daniel P. and Seymour, Paul and Thomas, Robin , TITLE =. Proceedings of the. 1996 , ISBN =. doi:10.1145/237814.238005 , URL =

    1996

  12. [20]

    1966 , author =

    On the algebraic theory of graph colorings , journal =. 1966 , author =

    1966

  13. [21]

    2018 , PAGES =

    Diestel, Reinhard , TITLE =. 2018 , PAGES =

    2018

  14. [22]

    L'Intermédiaire des mathématiciens , author=

    Sur le théorème de. L'Intermédiaire des mathématiciens , author=. 1898 , pages=

  15. [23]

    Three-edge-coloring (

    Inoue, Yuta and Kawarabayashi, Ken-ichi and Miyashita, Atsuyuki and Mohar, Bojan and Sonobe, Tomohiro , journal=. Three-edge-coloring (

  16. [24]

    Arxiv: , year=

    Three-edge-coloring apex cubic graphs , author=. Arxiv: , year=

  17. [25]

    Bernhart , title =

    A. Bernhart , title =. Amer. J. Math. 6 , volume=

  18. [26]

    To appear in FOCS'26

    The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring , author=. To appear in FOCS'26. ArXiv preprint arXiv:2603.24880 , year=

    arXiv

  19. [27]

    Klein, Felix , TITLE =. Math. Ann. , FJOURNAL =. 1879 , NUMBER =. doi:10.1007/BF01444143 , URL =

    doi

  20. [28]

    , TITLE =

    Tutte, William T. , TITLE =. New directions in the theory of graphs (. 1973 , MRCLASS =

    1973

  21. [29]

    Seymour , title =

    Paul D. Seymour , title =. Academic Press , pages=

  22. [30]

    Seymour , title =

    Paul D. Seymour , title =. Journal of Combinatorial Theory, Series B , volume =

  23. [31]

    Journal of Combinatorial Theory, Series B , volume=

    Excluded minors in cubic graphs , author=. Journal of Combinatorial Theory, Series B , volume=. 2019 , publisher=

    2019

  24. [32]

    Seymour and Robin Thomas , keywords =

    Neil Robertson and P.D. Seymour and Robin Thomas , keywords =. Cyclically five-connected cubic graphs , journal =. 2017 , doi =

    2017

Pith tools

Reviewed August 28, 2026 · model on record in the stance chip above.