Pith. sign in

REVIEW 2 major objections 1 minor 1 cited by

The Gray graph is pseudo 2-factor isomorphic

T0 review · 2 major / 1 minor · reviewed 2026-05-22 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗

Pith's one-line read The Gray graph is pseudo 2-factor isomorphic, making it a counterexample to the conjecture.

desk verdict Gray graph is the second known counterexample to the pseudo 2-factor conjecture, this time at girth 8 on 54 vertices, found by direct computer check. read the letter →

arxiv 2504.12095 v2 submitted 2025-04-16 math.CO cs.DM

Marien Abreu , Jan Goedgebeur , Jorik Jooken , Federico Romaniello , Tibo Van den Eede This is my paper · ORCID
classification math.COcs.DM
keywords Graygraphpseudo2-factorisomorphiccubicbipartitegraphs2-factorscounterexamplegirth8computerenumeration
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

The paper shows that every 2-factor of the Gray graph has the same parity in the number of cycles it contains. This property defines a pseudo 2-factor isomorphic graph and places the Gray graph, with its 54 vertices and girth 8, as a second known counterexample to the claim that only K_{3,3}, the Heawood graph, and the Pappus graph satisfy the condition among essentially 4-edge-connected cubic bipartite graphs. Exhaustive computer enumeration of all 2-factors establishes the shared parity for the Gray graph and rules out any smaller counterexamples of girth 8 or any counterexamples up to 42 vertices of any girth. The same searches confirm that the related 2-factor Hamiltonian conjecture holds for cubic bipartite graphs of girth at least 8 up to 52 vertices and up to 42 vertices overall.

What carries the argument

Exhaustive computer enumeration of every 2-factor together with direct computation of the parity of its cycle count.

What would settle it

Discovery of a single 2-factor in the Gray graph whose number of cycles has opposite parity from the others.

Watch

Extended reading notes

Core claim

The Gray graph is pseudo 2-factor isomorphic because all of its 2-factors share the same parity of the number of cycles. This makes the graph a counterexample to the conjecture of Abreu et al. that only three named graphs possess the property. Computer search verifies the shared parity directly, shows the Gray graph is the sole additional counterexample found, confirms no smaller girth-8 examples exist, and finds no further examples up to 42 vertices or among known symmetrical graphs.

Load-bearing premise

The computer implementation correctly enumerates every 2-factor of the Gray graph and smaller graphs and accurately computes the parity of the number of cycles in each without omissions or bugs.

Editorial extensions

If this is right

  • The Gray graph joins the 30-vertex graph G as the only known counterexamples.
  • No counterexamples of girth 8 exist below 54 vertices.
  • No counterexamples of any girth exist below 43 vertices.
  • The 2-factor Hamiltonian conjecture holds for all cubic bipartite graphs of girth at least 8 up to 52 vertices.
  • The 2-factor Hamiltonian conjecture holds for all cubic bipartite graphs up to 42 vertices.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Further counterexamples may appear among larger graphs once enumeration methods improve.
  • The failure of uniqueness at girth 8 shows the conjecture does not hold only for low-girth graphs.
  • The absence of additional examples in symmetrical censuses suggests the property remains rare even among vertex-transitive graphs.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 1 minor

Summary. The manuscript claims that the Gray graph (54 vertices, girth 8) is pseudo 2-factor isomorphic, serving as a second counterexample to the Abreu et al. conjecture on essentially 4-edge-connected pseudo 2-factor isomorphic cubic bipartite graphs (after the 30-vertex girth-6 example of Goedgebeur). It reports, via computer search, that the Gray graph is the only known girth-8 counterexample, that no girth-8 counterexamples exist below 54 vertices, and that no counterexamples of any girth exist up to 42 vertices; it also verifies the Funk et al. 2-factor Hamiltonian conjecture for cubic bipartite graphs of girth at least 8 up to 52 vertices and up to 42 vertices for any girth, plus checks on known symmetrical graph censuses.

Significance. If the computational results hold, the paper supplies a new, higher-girth counterexample and useful upper bounds on the size of any further counterexamples, together with additional verification of the related 2-factor Hamiltonian conjecture. These are concrete contributions to the study of 2-factors in cubic bipartite graphs. The work does not ship reproducible code or machine-checked certificates, so the significance is conditional on the correctness of the underlying enumeration.

major comments (2)
  1. [Abstract] Abstract (second paragraph): the claim that the Gray graph is pseudo 2-factor isomorphic rests entirely on exhaustive enumeration of its 2-factors together with correct parity computation of the cycle count in each. No enumeration algorithm, pseudocode, search parameters, or source code is supplied, rendering the central result unverifiable from the manuscript alone.
  2. [Abstract] Abstract (third paragraph): the statements that no smaller girth-8 counterexamples exist and that no counterexamples of any girth exist up to 42 vertices are presented as outcomes of computer search, yet the manuscript gives neither the vertex-order bounds actually checked, the generation method for candidate graphs, nor any completeness argument for the enumeration.
minor comments (1)
  1. [Abstract] The abstract refers to verification 'among the known censuses of symmetrical graphs' without naming the specific censuses or the vertex orders covered.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments on the verifiability of our computational results. We will revise the manuscript to provide the requested details on the enumeration methods and make supporting code available.

read point-by-point responses

  1. Referee: [Abstract] Abstract (second paragraph): the claim that the Gray graph is pseudo 2-factor isomorphic rests entirely on exhaustive enumeration of its 2-factors together with correct parity computation of the cycle count in each. No enumeration algorithm, pseudocode, search parameters, or source code is supplied, rendering the central result unverifiable from the manuscript alone.

    Authors: We agree that the manuscript as submitted does not include sufficient detail on the 2-factor enumeration procedure for the Gray graph. In the revision we will insert a dedicated methods section describing the enumeration algorithm (a backtracking search over perfect matchings in the line graph, with cycle parity computed via connected-component counting), the search parameters employed, and the verification steps. We will also deposit the source code in a public repository and reference it in the paper. revision: yes

  2. Referee: [Abstract] Abstract (third paragraph): the statements that no smaller girth-8 counterexamples exist and that no counterexamples of any girth exist up to 42 vertices are presented as outcomes of computer search, yet the manuscript gives neither the vertex-order bounds actually checked, the generation method for candidate graphs, nor any completeness argument for the enumeration.

    Authors: We concur that the description of the exhaustive searches is currently too terse. The revised manuscript will state the precise vertex-order ranges examined (girth-8 graphs up to 54 vertices; all cubic bipartite graphs up to 42 vertices), the generation procedure (filtering the output of the plantri/nauty generators for 3-regular bipartite graphs with prescribed girth), and the completeness argument (exhaustive generation of all non-isomorphic graphs in each class). The same section will document the additional checks performed on the known symmetric-graph censuses. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

Direct computational verification of graph properties with no circularity

full rationale

The paper establishes its claims via exhaustive computer enumeration of all 2-factors in the Gray graph (54 vertices) and smaller graphs, directly computing the parity of cycle counts to verify the pseudo 2-factor isomorphic property per the definition. This is a concrete, instance-specific check with no fitted parameters, self-referential equations, or reductions of predictions to inputs by construction. Self-citations to prior work (including by co-author Goedgebeur) supply historical context on the conjecture but are not load-bearing for the new results, which rest on independent computational verification against external graph censuses and definitions.

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

The claims rest on standard definitions of 2-factors and cycle parity together with the correctness of a graph enumeration program; no new free parameters or invented entities are introduced.

assumptions (1)
  • standard math Standard definitions of cubic bipartite graphs, 2-factors, cycle parity, girth, and essential 4-edge-connectivity.
    These definitions are invoked to state the conjecture and to interpret the computer output.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Gray graph is pseudo 2-factor isomorphic." pith.science (2026). https://pith.science/paper/2504.12095

@misc{pith2026250412095,
  author       = {Pith},
  title        = {Pith review of: The Gray graph is pseudo 2-factor isomorphic},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2504.12095}},
  note         = {Machine review of arXiv:2504.12095}
}
abstract

A graph is pseudo 2-factor isomorphic if all of its 2-factors have the same parity of number of cycles. Abreu et al. [J. Comb. Theory, Ser. B. 98 (2008) 432--442] conjectured that $K_{3,3}$, the Heawood graph and the Pappus graph are the only essentially 4-edge-connected pseudo 2-factor isomorphic cubic bipartite graphs. This conjecture was disproved by Goedgebeur [Discr. Appl. Math. 193 (2015) 57--60] who constructed a counterexample $\mathcal{G}$ (of girth 6) on 30 vertices. Using a computer search, he also showed that this is the only counterexample up to at least 40 vertices and that there are no counterexamples of girth greater than 6 up to at least 48 vertices. In this manuscript, we show that the Gray graph -- which has 54 vertices and girth 8 -- is also a counterexample to the pseudo 2-factor isomorphic graph conjecture. Next to the graph $\mathcal{G}$, this is the only other known counterexample. Using a computer search, we show that there are no smaller counterexamples of girth 8 and show that there are no other counterexamples up to at least 42 vertices of any girth. Moreover, we also verified that there are no further counterexamples among the known censuses of symmetrical graphs. Recall that a graph is 2-factor Hamiltonian if all of its 2-factors are Hamiltonian cycles. As a by-product of the computer searches performed for this paper, we have verified that the $2$-factor Hamiltonian conjecture of Funk et al. [J. Comb. Theory, Ser. B. 87(1) (2003) 138--144], which is still open, holds for cubic bipartite graphs of girth at least 8 up to 52 vertices, and up to 42 vertices for any girth.

Figures

Figures reproduced from arXiv: 2504.12095 by the authors.

Figure 1
Figure 1. The Heawood graph on the left and the Pappus graph on the right. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. The pseudo 2-factor isomorphic graph G on 30 vertices. be restricted to graphs of girth at least 6. In [19] the second author refuted Conjecture 1.4 (and consequently also Conjecture 1.3) by constructing a counterexample using a computer search. In particular, he generated all cubic bipartite graphs with girth at least 6 up to 40 vertices and all cubic bipartite graphs with girth at least 8 up to 48 vertices and tes… view at source ↗
Figure 3
Figure 3. The counterexample G on 30 vertices, with its 2–factor types high￾lighted [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: The counterexample G on 30 vertices, as constructed in [2]. counterexample to Conjecture 1.4. In Section 3, we present the results of our computer searches. Our exhaustive search on cubic bipartite graphs has now been extended to 42 vertices for girth at least 6 and to…
Figure 5
Figure 5. Figure 5: The Gray graph GR. This graph was originally discovered, but never published, by Marion Cameron Gray in 1932. It was re-discovered independently by Bouwer in 1968 [8], in reply to a question posed by Folkman in 1967 [17]. GR is interesting as it is the first known exam…
Figure 6
Figure 6. Figure 6: The Gray graph, with its 2-factor types highlighted. [PITH_FULL_IMAGE:figures/full_fig_p008_6.png]

Discussion (0). Continue with ORCID to comment.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. New small regular graphs of given girth: the cage problem and beyond

    math.CO 2025-11 conditional novelty 7.0 of 10

    New computational constructions give new record upper bounds for n(k,g) in 11 cases, including n(4,10) ≤ 320, n(3,16) ≤ 936, and n(3,17) ≤ 2048.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages · cited by 1 Pith paper

  1. [1]

    Abreu, A.A

    M. Abreu, A.A. Diwan, B. Jackson, D. Labbate and J. Sheehan. Pseudo 2-factor isomorphic regular bipartite graphs,J. Combin. Theory, Ser. B, 98(2), (2008), 432–444

    work page 2008

  2. [2]

    Abreu, M

    M. Abreu, M. Funk, D. Labbate and F. Romaniello. A construction for a counterexample to the pseudo 2-factor isomorphic graph conjecture,Discr. Appl. Math., 328, (2023), 134–138

    work page 2023

  3. [3]

    Abreu, J.B

    M. Abreu, J.B. Gauci, D. Labbate, F. Romaniello and J.P. Zerafa. Per- fect matchings, Hamiltonian cycles and edge-colourings in a class of cubic graphs, Ars Math. Contemp., 23, (2023), #P3.01

    work page 2023

  4. [4]

    Abreu, D

    M. Abreu, D. Labbate, R. Rizzi and J. Sheehan. Odd 2-factored snarks, European J. Combin., 36, (2014), 460–472

    work page 2014

  5. [5]

    Abreu, D

    M. Abreu, D. Labbate and J. Sheehan. Irreducible pseudo2-factor isomor- phic cubic bipartite graphs,Des. Codes Cryptogr., 64 (2012), 153–160

    work page 2012

  6. [6]

    Aldred, M

    R.E.L. Aldred, M. Funk, B. Jackson, D. Labbate and J. Sheehan, Regular bipartite graphs with all 2-factors isomorphic,J. Combin. Theory, Ser. B, 92, (2004), 151–161. 13

    work page 2004

  7. [7]

    Bondy and U.S.R

    J.A. Bondy and U.S.R. Murty. Graph Theory.Springer Series: Graduate Texts in Mathematics, 244 (2008)

    work page 2008

  8. [8]

    I.Z. Bouwer. An edge but not vertex-transitive cubic graph,Can. Math. Bull., 11 (4), (1968), 533–535

    work page 1968

Show all 34 references
  1. [9]

    Brinkmann

    G. Brinkmann. Fast generation of cubic graphs,J. Graph Theory, 23(2), (1996), 139–149

    1996

  2. [10]

    Brinkmann, J

    G. Brinkmann, J. Goedgebeur and B.D. McKay. The Minimality of the Georges-Kelmans Graph,Math. Comp., 91(335), (2022), 1483–1500

    2022

  3. [11]

    R. Čada, S. Chiba, K. Ozeki, P Vrána and K. Yoshimoto, A Relation- ship Between Thomassen’s Conjecture and Bondy’s Conjecture,SIAM J. Discrete Math., 29(1), (2015), 26–35

    2015

  4. [12]

    Conder, A

    M. Conder, A. Malnič, D. Marušič and P. Potočnik. A census of semisym- metric cubic graphs on up to 768 vertices,J. Algebraic Combin., 23(3), (2006), 255–294

    2006

  5. [13]

    Conder and P

    M. Conder and P. Potočnik. Edge-transitive cubic graphs: Cataloguing and Enumeration, arXiv preprint arXiv:2502.02250(2025)

    2025

  6. [14]

    Coolsaet, S

    K. Coolsaet, S. D’hondt and J. Goedgebeur. House of Graphs 2.0: A database of interesting graphs and more,Discr. Appl. Math., 325, (2023), 97–107. Available athttps://houseofgraphs.org

    2023

  7. [15]

    Exoo and R

    G. Exoo and R. Jajcay. On the girth of voltage graph lifts.Europ. J. Com- bin., 32(4) (2011) 554–562

    2011

  8. [16]

    L.C. Eze, R. Jajcay, J. Jooken. On(k, g)- Graphs without(g + 1)-Cycles, arXiv preprint arXiv:2411.19023(2024)

    2024

  9. [17]

    J. Folkman. Regular line-symmetric graphs, J. Combin. Theory, 3(3), (1967), 215–232

    1967

  10. [18]

    M. Funk, B. Jackson, D. Labbate and J. Sheehan. 2-factor Hamiltonian graphs, J. Comb. Theory, Ser. B, 87(1), (2003), 138–144

    2003

  11. [19]

    Goedgebeur

    J. Goedgebeur. A counterexample to the pseudo2-factor isomorphic graph conjecture, Discr. Appl. Math., 193, (2015), 57–60

    2015

  12. [20]

    Gorsky, T

    M. Gorsky, T. Johanni and S. Wiederrecht, A note on the 2-factor Hamil- tonicity Conjecture,Discr. Math., 348, (2025), 114442

    2025

  13. [21]

    Graph Theory, 15(2), (1991), 121–157

    R.J.Gould.UpdatingtheHamiltonianproblem-asurvey, J. Graph Theory, 15(2), (1991), 121–157

    1991

  14. [22]

    R.J. Gould. Recent advances on the Hamiltonian problem: survey III, Graphs Comb., 30(1), (2014), 1–46. 14

    2014

  15. [23]

    Jooken and T

    J. Jooken and T. Van den Eede. 2-factor parity checker [GitHub repository] (2025). https://github.com/tiboat/2FactorParityChecker

    2025

  16. [24]

    R.M. Karp. Reducibility among Combinatorial Problems. InComplexity of Computer Computations, pages 85–103. Springer US, Boston, MA, (1972)

    1972

  17. [25]

    R. M. Karp and M. Sipser. Maximum Matching in Sparse Random Graphs. In 22nd Annual Symp. on Foundations of Computer Science (SFCS’81), (1981), 364–375

    1981

  18. [26]

    D. Labbate. On3-cut reductions of minimally1-factorable cubic bigraphs, Discr. Math., 231(1-3), (2001), 303–310

    2001

  19. [27]

    D. Labbate. Characterizing minimally 1-factorable r-regular bipartite graphs, Discr. Math., 248(1-3), (2002), 109–123

    2002

  20. [28]

    Labbate and F

    D. Labbate and F. Romaniello, A survey on2-factors of regular graphs, Bull. Inst. Combin. Appl. (to appear) https://arxiv.org/abs/2408. 04642

  21. [29]

    K. Kaya, J. Langguth, I. Panagiotas and B. Uçar. MatchMaker: A collec- tion of algorithms for finding maximum transversals or maximum match- ings in bipartite graphs. [Computer software] (2022). https://gitlab. inria.fr/bora-ucar/matchmaker

    2022

  22. [30]

    Malnič, D

    A. Malnič, D. Marušič, P. Potočnik, and C. Wang. An Infinite Family of Cubic Edge- but Not Vertex-Transitive Graphs,Discr. Math., 280, (2002), 133–148

    2002

  23. [31]

    Marušič and T

    D. Marušič and T. Pisanski. The Gray graph revisited,J. Graph Theory, 35, (2000), 1–7

    2000

  24. [32]

    Meringer

    M. Meringer. Fast generation of regular graphs and construction of cages, J. Graph Theory, 30(2), (1999), 137–146

    1999

  25. [33]

    Monson, T

    B. Monson, T. Pisanski, E. Schulte and A.I. Weiss. Semisymmetric Graphs from Polytopes,J. Combin. Theory, Ser. A, 114(3), (2007), 421–435

    2007

  26. [34]

    Romaniello and J.P

    F. Romaniello and J.P. Zerafa. Betwixt and Between 2-Factor Hamiltonian and Perfect-Matching-Hamiltonian Graphs, Electron. J. Combin., 30(2), (2023), #P2.5. 15

    2023

Pith tools

Reviewed May 22, 2026 · model on record in the stance chip above.