pith. machine review for the scientific record. sign in

arxiv: 2603.27559 · v2 · submitted 2026-03-29 · 🧮 math.CO

Recognition: 2 theorem links

· Lean Theorem

Lifting and Folding: A Framework for Unstable Graphs and TF-Cousins

Russell Mizzi

Authors on Pith no claims yet

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

classification 🧮 math.CO
keywords unstable graphscanonical double coverTF-isomorphismsTF-cousinsswitching involutionslifting and foldingclaw graphsPetersen graph
0
0 comments X

The pith

Conjugacy classes of switching involutions unify unstable graphs and pairs of non-isomorphic graphs sharing a canonical double cover.

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

The paper establishes that unstable graphs, where the canonical double cover has more automorphisms than expected, and pairs of non-isomorphic graphs that share the same double cover, both arise from the same operations of lifting and guided folding. These operations are controlled by conjugacy classes of strongly switching involutions in the automorphism group of the double cover, expressed through two-fold isomorphisms. Lifting maps one graph to a digraph matching the alternating double cover, while folding produces a graph that is two-fold isomorphic to the original; non-isomorphism yields TF-cousins and isomorphism yields instability. The approach recovers prior results on shared covers and generates infinite families from cycle unions, including a claw graph family that produces TF-cousins precisely when the parameter is odd. Readers should care because it replaces isolated examples with a single mechanism that constructs and relates these graphs systematically.

Core claim

We unify both via lifting and guided folding, showing that they are governed by conjugacy classes of strongly switching involutions in Aut(CDC(G)). Using two-fold isomorphisms (TF-isomorphisms), lifting (α,β):G→H produces a digraph isomorphic to the alternating double cover of G, while folding yields a graph TF-isomorphic to G. If this graph is non-isomorphic to G, the pair forms TF-cousins; otherwise (α,β) is a non-trivial TF-automorphism and G is unstable. Distinct conjugacy classes of switching involutions in Aut(CDC(G)) produce non-isomorphic graphs with a common CDC, recovering a theorem of Pacco and Scapellato. The framework generates TF-cousin pairs and unstable graphs of arbitrary 0r

What carries the argument

lifting and guided folding governed by conjugacy classes of strongly switching involutions in Aut(CDC(G)), expressed through two-fold isomorphisms

If this is right

  • Distinct conjugacy classes of switching involutions produce non-isomorphic graphs with a common CDC.
  • The constructions generate TF-cousin pairs and unstable graphs of arbitrary order from the basic cycle unions (C_k ∪ C_k, C_{2k}).
  • Claw graphs CG(n) and CG'(n) are TF-cousins if and only if n is odd, yielding the Petersen graph and a cubic companion for n=1, plus new cubic graphs for odd n at least 3.
  • Every connected graph on at most nine vertices satisfies the cycle conjecture linking TF-cousins and unstable graphs to C_k and C_{2k} for some odd k.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the cycle conjecture holds in general, then all instability and cousin relations would reduce to the presence of paired odd and even cycles in the underlying graphs.
  • The same lifting and folding mechanism might apply directly to other covering graphs or to products beyond the canonical double cover.
  • A systematic search for counterexamples on graphs with ten or more vertices would test whether the unification is complete or requires additional conditions.

Load-bearing premise

That conjugacy classes of strongly switching involutions in Aut(CDC(G)) always produce distinct non-isomorphic graphs or TF-cousins, and that constructions from cycle unions extend to arbitrary orders without extra constraints on the graphs being connected or simple.

What would settle it

A concrete counterexample would be either a pair of non-isomorphic graphs sharing a CDC that cannot be produced as TF-cousins by lifting and folding from any conjugacy class of switching involution, or an unstable graph on more than nine vertices that lacks the cycle pair C_k and C_{2k} for odd k.

Figures

Figures reproduced from arXiv: 2603.27559 by Russell Mizzi.

Figure 1
Figure 1. Figure 1: A non-trivial TF-isomorphism from G to H, with α = (2 5) and β = (1 4)(3 6). equality holds when G has no non-trivial TF-automorphisms. However, an asymmetric graph G (one with |Aut(G)| = 1) may still admit non-trivial TF-automorphisms [11]. The canonical double cover of G, denoted CDC(G), has vertex set V (G) × Z2; the pairs ((u, 0),(v, 1)) and ((u, 1),(v, 0)) are arcs of CDC(G) whenever (u, v) is an arc … view at source ↗
Figure 2
Figure 2. Figure 2: The smallest known unstable asymmetric graph [13]. With γ = (1 2 3)(4 5 6)(7 8 9)(10 11 12), the pair (γ, γ−1 ) is a non-trivial TF-automorphism. 3. A-Trails and Alternating Double Covers The standard notion of a path carries an implicit direction even for undirected graphs: under an ordinary isomorphism α, the arcs (u, v) and (v, w) map to (α(u), α(v)) and (α(v), α(w)), sharing the common vertex α(v). Und… view at source ↗
Figure 3
Figure 3. Figure 3: The graph G ∼= C3 (left) and its lift G⃗ α,β ∼= ADC(G) (right). If (α, β) is a TF-isomorphism from H to K, then (α −1 , β−1 ) is a TF-isomorphism from K to H and K⃗ α,β ∼= H⃗ α−1,β−1 ; in particular, the lifts of TF-isomorphic base graphs are isomorphic, and replacing the arcs of any lift with undirected edges recovers the common CDC. The following two observations will be used in the constructions of Sect… view at source ↗
Figure 4
Figure 4. Figure 4: A TF-isomorphism from C3 ∪ C3 to C6. α(v1) β(v2) α(v3) β(v1) α(v2) β(v3) β(v4) α(v5) β(v6) α(v4) β(v5) α(v6) [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The lift G⃗ 0α,β corresponding to [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The three non-equivalent pairs of TF-cousins on six vertices obtain￾able from the seed pair by adding one, two, or three entangled edges. (a) (b) (c) [PITH_FULL_IMAGE:figures/full_fig_p007_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Pairs of isomorphic unstable symmetric graphs from the same seed pair, by adding one, two, or three complementary pairs of split-image edges. Construction 5.2 (Adding vertices via pins). The construction extends naturally to larger vertex sets. Adding an isolated vertex x to G0 and an isolated vertex y to H0, and extending (α, β) by α(x) = β(x) = y, makes x a pin. Connecting x to an entangled pair vi, vj i… view at source ↗
Figure 8
Figure 8. Figure 8: The Petersen graph as a claw graph (k = 3, n = 1). We fix k = 3 throughout this section so that the resulting graphs are cubic: claw centres and leaves both have degree 3, matching the two circuit neighbours of each circuit vertex. The general case k ≥ 2 is addressed in Remark 6.2. Definition 6.1. For a positive integer n, the claw graph CG(n) is constructed as follows. Take a circuit C6n with vertices u0,… view at source ↗
Figure 9
Figure 9. Figure 9: The claw graph CG(3): the case k = 3, n = 3. CG′ (n) (the two copies of C3n are even cycles, hence bipartite, with the same parity structure). Thus both graphs are bipartite. For any bipartite graph G, the CDC satisfies CDC(G) ∼= G ∪ G (the two sheets of the cover are isomorphic copies of G). Hence CDC(CG(n)) ∼= CG(n) ∪ CG(n) and CDC(CG′ (n)) ∼= CG′ (n) ∪ CG′ (n). These are isomorphic if and only if CG(n) … view at source ↗
Figure 10
Figure 10. Figure 10: The companion CG′ (3), which is TF-isomorphic but non-isomorphic to CG(3). Remark 6.2. The same construction and proof work for any integer k ≥ 2, replacing 3n by kn throughout. The seed pair Ckn ∪ Ckn and C2kn satisfies CDC(Ckn ∪ Ckn) ∼= CDC(C2kn) if and only if kn is odd, by the same CDC component-count argument used above. When kn is even, which is forced whenever k or n is even, no TF-cousin pair aris… view at source ↗
read the original abstract

A graph $G$ is \emph{unstable} if its canonical double cover CDC$(G)$ has more automorphisms than Aut$(G)\times \mathbb{Z}_2$. A related problem asks when two non-isomorphic graphs share the same CDC. We unify both via \emph{lifting} and \emph{guided folding}, showing that they are governed by conjugacy classes of strongly switching involutions in Aut(\CDC$(G)$). Using \emph{two-fold isomorphisms} (TF-isomorphisms), lifting $(\alpha,\beta):G\to H$ produces a digraph isomorphic to the alternating double cover of $G$, while folding yields a graph TF-isomorphic to $G$. If this graph is non-isomorphic to $G$, the pair forms TF-cousins; otherwise $(\alpha,\beta)$ is a non-trivial TF-automorphism and $G$ is unstable. Distinct conjugacy classes of switching involutions in Aut$(CDC(G))$ produce non-isomorphic graphs with a common CDC, recovering a theorem of Pacco and Scapellato. The framework generates TF-cousin pairs and unstable graphs of arbitrary order from $(C_k\cup C_k,\, C_{2k})$. We introduce the \emph{claw graph} family CG$(n)$ and show that CG$(n)$ and CG'$(n)$ are TF-cousins iff $n$ is odd. For $n=1$, this yields the Petersen graph and a cubic companion on $10$ vertices, both with the Desargues graph as CDC. For odd $n\geq 3$, we obtain new non-isomorphic cubic graphs sharing a CDC. We conjecture that every TF-cousin pair and unstable graph contains cycles $C_k$ and $C_{2k}$ for some odd $k$, verified for all connected graphs on at most $9$ vertices.

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

3 major / 2 minor

Summary. The paper introduces a framework using lifting and guided folding to unify the study of unstable graphs (where Aut(CDC(G)) properly contains Aut(G) × ℤ₂) and TF-cousin pairs (non-isomorphic graphs sharing a CDC). These phenomena are governed by conjugacy classes of strongly switching involutions in Aut(CDC(G)). Using TF-isomorphisms, lifting produces an alternating double cover while folding produces a TF-isomorphic graph; distinct classes are claimed to yield non-isomorphic outputs. Explicit constructions are given from the family (C_k ∪ C_k, C_{2k}) for arbitrary order and from the new claw-graph family CG(n), with CG(n) and CG'(n) shown to be TF-cousins precisely when n is odd. The case n=1 recovers the Petersen graph (with Desargues graph as CDC); for odd n ≥ 3 new cubic examples are obtained. A conjecture asserts that every such pair or unstable graph contains an odd-k cycle C_k together with C_{2k}, verified computationally for all connected graphs on ≤ 9 vertices.

Significance. If the framework and constructions are correct, the paper supplies a systematic, conjugacy-class-based method for generating unstable graphs and TF-cousin pairs of arbitrary order, recovers the Pacco–Scapellato theorem as a special case, and produces concrete new cubic examples. The explicit cycle-union and claw-graph families, together with the small-order verification, constitute reproducible constructions that could serve as a foundation for further classification results in the theory of canonical double covers.

major comments (3)
  1. [Construction from cycle unions and general production claim] The central claim that distinct conjugacy classes of strongly switching involutions always produce non-isomorphic TF-cousins or unstable graphs rests on an unverified extension from the (C_k ∪ C_k, C_{2k}) base cases. The manuscript must supply an explicit argument showing that the folding operation preserves distinctness of classes for arbitrary k without hidden automorphisms collapsing the outputs, and must confirm that the resulting graphs remain simple and connected.
  2. [Conjecture following claw-graph construction] The conjecture that every TF-cousin pair and unstable graph contains cycles C_k and C_{2k} for some odd k is supported only by verification up to 9 vertices. Because this conjecture is invoked to assert that the framework captures all such graphs, either a general proof or a substantially larger computational census (with explicit bounds) is required before the unification claim can be regarded as established.
  3. [Claw graph CG(n) section] For the claw-graph family, the statement that CG(n) and CG'(n) are TF-cousins if and only if n is odd, together with the recovery of the Petersen graph for n=1, depends on the conjugacy-class action in Aut(CDC(G)). The manuscript should provide the explicit involution representatives and the verification that no additional automorphisms identify the two graphs when n is even.
minor comments (2)
  1. [Definitions] The definitions of 'strongly switching involution' and 'TF-isomorphism' would benefit from a short illustrative example immediately after their introduction, including the explicit action on the double cover.
  2. [Introduction] The citation to the Pacco–Scapellato theorem should appear in the introduction with a precise statement of what is being recovered, rather than only in the abstract.

Simulated Author's Rebuttal

3 responses · 1 unresolved

We thank the referee for the thorough review and constructive comments on our manuscript. We address each major comment point by point below, indicating revisions where appropriate.

read point-by-point responses

  1. Referee: The central claim that distinct conjugacy classes of strongly switching involutions always produce non-isomorphic TF-cousins or unstable graphs rests on an unverified extension from the (C_k ∪ C_k, C_{2k}) base cases. The manuscript must supply an explicit argument showing that the folding operation preserves distinctness of classes for arbitrary k without hidden automorphisms collapsing the outputs, and must confirm that the resulting graphs remain simple and connected.

    Authors: We agree that an explicit argument is needed for the general case. In the revised manuscript we will insert a new lemma establishing that, for the cycle-union family, the folding operation maps distinct conjugacy classes to non-isomorphic outputs. The proof proceeds by showing that any isomorphism between the folded graphs would induce an automorphism of the CDC that conjugates one switching involution to the other, contradicting distinctness of classes; the argument uses the explicit wreath-product structure of Aut(CDC(C_k ∪ C_k)). We also add a short verification that all constructed graphs are simple (no multiple edges arise from the folding) and connected (inherited from the connectedness of C_{2k} for k ≥ 3). revision: yes

  2. Referee: The conjecture that every TF-cousin pair and unstable graph contains cycles C_k and C_{2k} for some odd k is supported only by verification up to 9 vertices. Because this conjecture is invoked to assert that the framework captures all such graphs, either a general proof or a substantially larger computational census (with explicit bounds) is required before the unification claim can be regarded as established.

    Authors: We will revise the text to clarify that the lifting-and-folding framework unifies all graphs that admit strongly switching involutions in their CDC automorphism group; the conjecture is presented as an independent observation suggesting that every such graph contains the indicated cycle pair. A general proof is not currently available. We will also report an extended computational check up to 12 vertices (still feasible with existing code) and state the limitation explicitly, but a substantially larger census lies outside the scope of the present work. revision: partial

  3. Referee: For the claw-graph family, the statement that CG(n) and CG'(n) are TF-cousins if and only if n is odd, together with the recovery of the Petersen graph for n=1, depends on the conjugacy-class action in Aut(CDC(G)). The manuscript should provide the explicit involution representatives and the verification that no additional automorphisms identify the two graphs when n is even.

    Authors: We will add an appendix subsection supplying explicit matrix or permutation representatives for the strongly switching involutions in Aut(CDC(CG(n))). For odd n the representative produces a non-trivial TF-isomorphism between CG(n) and CG'(n); for even n we show that the candidate involution either fails to be strongly switching or lies in a larger conjugacy class whose folding yields a graph isomorphic to the original via an automorphism of the CDC. The n=1 case is recovered explicitly as the Petersen–Desargues pair. These additions will make the iff statement fully rigorous. revision: yes

standing simulated objections not resolved
  • Request for a general proof of the conjecture that every TF-cousin pair or unstable graph contains an odd-k cycle pair C_k ∪ C_{2k}, or for a substantially larger computational census with explicit bounds.

Circularity Check

0 steps flagged

No circularity: framework built on independent definitions and external theorem recovery

full rationale

The derivation introduces new operations (lifting via pairs (α,β), guided folding, TF-isomorphisms) and relates them to conjugacy classes of strongly switching involutions in Aut(CDC(G)) by explicit construction. Unstable graphs and TF-cousin pairs are defined directly from these operations without any parameter fitted to the target output or any equation that reduces the claimed unification back to its inputs by construction. The recovery of the Pacco-Scapellato theorem is cited as an external result rather than a self-citation chain. Explicit families such as (C_k ∪ C_k, C_{2k}) and CG(n) are generated by the definitions themselves, and the conjecture on cycle content is presented as a separate observation verified only on small orders, not as a load-bearing premise inside the main argument. No self-definitional loops, fitted-input predictions, or ansatz smuggling appear in the provided text.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 3 invented entities

The paper builds a new framework on standard graph theory background with no numerical free parameters fitted to data. New concepts are introduced as definitions rather than postulated entities with independent evidence.

axioms (1)
  • standard math Standard definitions of graphs, automorphisms, canonical double covers, and involutions hold as in prior graph theory literature.
    The framework relies on these established concepts without re-deriving them.
invented entities (3)
  • TF-isomorphism no independent evidence
    purpose: Defines the lifting and folding operations that relate graphs to their covers and cousins.
    New relation introduced to unify the two problems.
  • strongly switching involution no independent evidence
    purpose: Governs the conjugacy classes that produce unstable graphs and TF-cousins.
    Central new object in the automorphism group of the CDC.
  • claw graph CG(n) no independent evidence
    purpose: Generates infinite families of TF-cousin pairs for odd n.
    New infinite family of cubic graphs introduced for explicit constructions.

pith-pipeline@v0.9.0 · 5646 in / 1711 out tokens · 51896 ms · 2026-05-14T22:22:11.538849+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.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    Abay-Asmerom, R

    G. Abay-Asmerom, R. Hammack, C. E. Larson, and D. T. Taylor. Direct product factorization of bipartite graphswithbipartition-reversinginvolutions.SIAM Journal on Discrete Mathematics, 23(4):2042–2052, 2010

    work page 2042

  2. [2]

    Bondy and U.S.R

    A. Bondy and U.S.R. Murty.Graph Theory (Graduate Texts in Mathematics). Springer, 2008. LIFTING AND FOLDING 13

    work page 2008

  3. [3]

    Buckley and F

    F. Buckley and F. Harary.Distance in graphs. The Advanced Book Program. Addison-Wesley Pub. Co., 1990

    work page 1990

  4. [4]

    The walks and cdc of graphs with the same main eigenspace.Discussiones Mathematicae Graph Theory, 2020

    Luke Collins and Irene Sciriha. The walks and cdc of graphs with the same main eigenspace.Discussiones Mathematicae Graph Theory, 2020

    work page 2020

  5. [5]

    Gross and Thomas W

    Jonathan L. Gross and Thomas W. Tucker.Topological Graph Theory. Wiley Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 1987

    work page 1987

  6. [6]

    Imrich and S

    W. Imrich and S. Klavzar.Product Graphs: Structure and Recognition. Wiley, 2000

    work page 2000

  7. [7]

    Imrich and T

    W. Imrich and T. Pisanski. Multiple Kronecker covering graphs.European Journal of Combinatorics, 29(5):1116–1122, 2008

    work page 2008

  8. [8]

    M. H. Klin, J. Lauri, and M. Ziv-Av. Links between two semisymmetric graphs on 112 vertices via association schemes.J. Symb. Comput., 47(10):1175–1191, 2012

    work page 2012

  9. [9]

    Krnc and T

    M. Krnc and T. Pisanski. Generalized Petersen graphs and Kronecker covers.Discrete Mathematics and Theoretical Computer Science, 21(4), 2019

    work page 2019

  10. [10]

    Lauri, R

    J. Lauri, R. Mizzi, and R. Scapellato. Two-fold orbital digraphs and other constructions.International J. of Pure and Applied Math., 1:63–93, 2004

    work page 2004

  11. [11]

    Lauri, R

    J. Lauri, R. Mizzi, and R. Scapellato. Two-fold automorphisms of graphs.Australasian J. Combinatorics., 49:165–176, 2011

    work page 2011

  12. [12]

    Lauri, R

    J. Lauri, R. Mizzi, and R. Scapellato. Unstable graphs: A fresh outlook via TF-automorphisms.Ars Mathe- matica Contemporanea, 8(1):115–131, 2015

    work page 2015

  13. [13]

    Lauri, R

    J. Lauri, R. Mizzi, and R. Scapellato. The construction of a smallest unstable asymmetric graph and a family of unstable asymmetric graphs with an arbitrarily high index of instability.Discrete Applied Mathe- matics, 266:85–91, 2019. Special issue: The Second Malta Conference in Graph Theory and Combinatorics (2MCGTC-2017)

    work page 2019

  14. [14]

    Lauri and R

    J. Lauri and R. Scapellato.Topics in Graph Automorphisms and Reconstruction. Cambridge University Press, 2003

    work page 2003

  15. [15]

    B. D. McKay. Combinatorial data: Graphs, 2024. Graph data available athttps://users.cecs.anu.edu. au/~bdm/data/graphs.html

    work page 2024

  16. [16]

    B. D. McKay and A. Piperno. Practical graph isomorphism, II.Journal of Symbolic Computation, 60:94–112, 2014

    work page 2014

  17. [17]

    Mizzi.Two-Fold Automorphisms

    R. Mizzi.Two-Fold Automorphisms. PhD thesis, University of Malta, Malta, 2015

    work page 2015

  18. [18]

    Pacco and R

    W. Pacco and R. Scapellato. Digraphs having the same canonical double covering.Discrete Math., 173(1– 3):291–296, 1997

    work page 1997

  19. [19]

    L. Porcu. Sul raddoppio di un grafo.Att. Ist. Lombardo (Rend. Sci.), A(110):453–480, 1976

    work page 1976

  20. [20]

    B. Zelinka. Isotopy of digraphs.Czechoslovak Mathematical Journal, 22(3):353–360, 1972. Department of Mathematics, University of Malta, Malta Email address:russell.mizzi@um.edu.mt

    work page 1972