pith. sign in

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

The Gray graph is pseudo 2-factor isomorphic

Marien Abreu , Jan Goedgebeur , Jorik Jooken , Federico Romaniello , Tibo Van den Eede This is my paper

Pith reviewed 2026-05-22 20:20 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords Gray graphpseudo 2-factor isomorphiccubic bipartite graphs2-factorscounterexamplegirth 8computer enumeration
0
0 comments X

The pith

The Gray graph is pseudo 2-factor isomorphic, making it a counterexample to the conjecture.

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

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.

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.

What carries the argument

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

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.

Where Pith is reading between the lines

These are 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.

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.

What would settle it

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

Figures

Figures reproduced from arXiv: 2504.12095 by Federico Romaniello, Jan Goedgebeur, Jorik Jooken, Marien Abreu, Tibo Van den Eede.

Figure 1
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. 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 vertic… view at source ↗
Figure 3
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 ↗
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 52 vertices for girth at 6 [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
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 example of a cubic graph having the algebraic property of being semisymmetric, i.e. edge-transitive but not vertex-transitive. In other words, s… view at source ↗
Figure 6
Figure 6. Figure 6: The Gray graph, with its 2-factor types highlighted. [PITH_FULL_IMAGE:figures/full_fig_p008_6.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

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

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.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 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.

axioms (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.

pith-pipeline@v0.9.0 · 5916 in / 1292 out tokens · 83998 ms · 2026-05-22T20:20:15.226215+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

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.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

  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

  9. [9]

    Brinkmann

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

    work page 1996

  10. [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

    work page 2022

  11. [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

    work page 2015

  12. [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

    work page 2006

  13. [13]

    Conder and P

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

    work page arXiv 2025

  14. [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

    work page 2023

  15. [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

    work page 2011

  16. [16]

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

    work page arXiv 2024

  17. [17]

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

    work page 1967

  18. [18]

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

    work page 2003

  19. [19]

    Goedgebeur

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

    work page 2015

  20. [20]

    Gorsky, T

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

    work page 2025

  21. [21]

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

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

    work page 1991

  22. [22]

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

    work page 2014

  23. [23]

    Jooken and T

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

    work page 2025

  24. [24]

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

    work page 1972

  25. [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

    work page 1981

  26. [26]

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

    work page 2001

  27. [27]

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

    work page 2002

  28. [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

    work page

  29. [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

    work page 2022

  30. [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

    work page 2002

  31. [31]

    Marušič and T

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

    work page 2000

  32. [32]

    Meringer

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

    work page 1999

  33. [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

    work page 2007

  34. [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

    work page 2023