pith. sign in

arxiv: 2510.11486 · v2 · submitted 2025-10-13 · 🧮 math.CO

2-Factors in Graphs

Jan van den Heuvel , Bjarne Toft This is my paper

Pith reviewed 2026-05-18 07:39 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C70
keywords 2-factorsgraph theoryalternating chainsregular graphsPetersen's theoremfactor theoremsmaximal graphsleaves
0
0 comments X

The pith

Direct proofs and a complete characterization establish when graphs have 2-factors.

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

The paper supplies a direct graph-theoretic proof of the 2-Factor Theorem using alternating chains, presents a new variant of the theorem, and gives a full description of the maximal graphs that do not contain a 2-factor. It also proves that any (2k+1)-regular graph with at most 2k leaves has a 2-factor and identifies the extremal cases with one more leaf. A reader would care because these results simplify the understanding of factor existence in graphs and extend well-known theorems such as Petersen's on cubic graphs.

Core claim

Using the alternating chain theory from Gallai and Belck, the authors prove the 2-Factor Theorem directly and characterize all maximal graphs without 2-factors. They further show that (2k+1)-regular graphs with few leaves always have 2-factors and describe the exceptional connected graphs with exactly 2k+1 leaves that do not.

What carries the argument

Alternating chains, which detect deficiencies in factor structures by tracing paths that alternate between edges in and out of a potential factor.

If this is right

  • Any (2k+1)-regular graph with at most 2k leaves contains a 2-factor.
  • The connected (2k+1)-regular graphs with exactly 2k+1 leaves that lack a 2-factor are completely listed.
  • This generalizes Petersen's theorem that 3-regular graphs with at most two leaves have a 1-factor.
  • The maximal graphs without 2-factors are those where adding any missing edge creates a 2-factor, and they are described via alternating chain conditions.

Where Pith is reading between the lines

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

  • These characterizations may lead to efficient ways to check for 2-factors or to minimally augment graphs to ensure their existence.
  • Similar techniques could apply to other factor problems or to matching in hypergraphs.
  • The historical account might encourage revisiting other classic graph theorems with modern direct proofs.

Load-bearing premise

The alternating-chain theory developed in the 1950 papers of Gallai and Belck is accurate and transfers without gaps to the setting of 2-factors.

What would settle it

Discovery of a graph that is maximal without a 2-factor but does not fit the proposed characterization based on alternating chains, or a (2k+1)-regular graph with at most 2k leaves that has no 2-factor.

read the original abstract

An account of 2-factors in graphs and their history is presented. We give a direct graph-theoretic proof of the 2-Factor Theorem and a new variant of it, and also a new complete characterisation of the maximal graphs without 2-factors. This is based on the important works of Tibor Gallai on 1-factors and of Hans-Boris Belck on k-factors, both published in 1950 and independently containing the theory of alternating chains. We also present an easy proof that a $(2k+1)$-regular graph with at most $2k$ leaves has a 2-factor, and we describe all connected $(2k+1)$-regular graphs with exactly $2k+1$ leaves without a 2-factor. This generalises Julius Petersen's famous theorem, that any 3-regular graph with at most two leaves has a 1-factor, and it generalises the extremal graphs Sylvester discovered for that theorem.

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 / 2 minor

Summary. The manuscript gives a historical account of 2-factors, supplies a direct graph-theoretic proof of the 2-Factor Theorem together with a new variant, and states a new complete characterisation of the maximal graphs without 2-factors. The arguments rest on the alternating-chain theory of Gallai (1950) and Belck (1950). It also contains an elementary proof that every (2k+1)-regular graph with at most 2k leaves admits a 2-factor and a description of all connected (2k+1)-regular graphs with exactly 2k+1 leaves that lack a 2-factor, thereby generalising Petersen’s theorem and the extremal examples found by Sylvester.

Significance. If the direct proofs and the claimed characterisation are valid, the work would supply accessible graph-theoretic arguments for classical factor theorems and extend them to regular graphs that contain a controlled number of leaves. The explicit generalisation of Petersen’s 1-factor result to (2k+1)-factors with at most 2k leaves is a concrete strengthening that could be useful in extremal and structural graph theory.

major comments (2)
  1. [Proof of the 2-Factor Theorem and characterisation section] The central claims (direct proof of the 2-Factor Theorem, new variant, and complete characterisation of maximal graphs without 2-factors) are grounded in the alternating-chain results of Gallai and Belck. The manuscript must supply an explicit verification that the chain-augmentation and maximality-blocking properties transfer verbatim to the setting of 2-factors when the graph may contain up to 2k degree-1 vertices; without such a bridging argument the grounding of the new results remains incomplete.
  2. [Section on (2k+1)-regular graphs with leaves] The description of all connected (2k+1)-regular graphs with exactly 2k+1 leaves that lack a 2-factor must be accompanied by a self-contained argument showing both that these graphs indeed have no 2-factor and that every such graph is maximal with respect to the absence of a 2-factor; any missing case analysis on the placement of the 2k+1 leaves would render the characterisation incomplete.
minor comments (2)
  1. [Introduction / Notation] Define the term “leaves” explicitly at first use and clarify whether the graphs under consideration are allowed to be disconnected or whether the statements apply only to connected graphs.
  2. [References] Provide complete bibliographic details for the 1950 papers of Gallai and Belck, including journal, volume, and page numbers.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and insightful comments on our manuscript. We appreciate the recognition of the potential significance of our direct proofs and generalizations. Below, we address each major comment in detail and outline the revisions we plan to make.

read point-by-point responses

  1. Referee: [Proof of the 2-Factor Theorem and characterisation section] The central claims (direct proof of the 2-Factor Theorem, new variant, and complete characterisation of the maximal graphs without 2-factors) are grounded in the alternating-chain results of Gallai and Belck. The manuscript must supply an explicit verification that the chain-augmentation and maximality-blocking properties transfer verbatim to the setting of 2-factors when the graph may contain up to 2k degree-1 vertices; without such a bridging argument the grounding of the new results remains incomplete.

    Authors: We agree that an explicit bridging argument would enhance the clarity and rigor of our presentation. Although the alternating-chain theory applies naturally to the 2-factor case by considering the appropriate parity and degree conditions, we will add a new subsection in the revised manuscript that carefully verifies the transfer of the chain-augmentation and maximality-blocking properties to graphs with up to 2k degree-1 vertices. This will include adapting the definitions and lemmas from Gallai and Belck to the 2-factor setting, ensuring the arguments are self-contained. revision: yes

  2. Referee: [Section on (2k+1)-regular graphs with leaves] The description of all connected (2k+1)-regular graphs with exactly 2k+1 leaves that lack a 2-factor must be accompanied by a self-contained argument showing both that these graphs indeed have no 2-factor and that every such graph is maximal with respect to the absence of a 2-factor; any missing case analysis on the placement of the 2k+1 leaves would render the characterisation incomplete.

    Authors: We acknowledge the need for a more detailed, self-contained proof in this section. In the revision, we will expand the characterization by providing a complete case analysis based on the possible placements and connections of the 2k+1 leaves in the (2k+1)-regular graph. For each case, we will explicitly demonstrate the absence of a 2-factor using the alternating chain method and prove maximality by showing that adding any edge would create a 2-factor. This will make the argument independent of external references where possible. revision: yes

Circularity Check

0 steps flagged

No significant circularity; proofs and characterization rest on external 1950 theorems

full rationale

The paper states that its direct graph-theoretic proof of the 2-Factor Theorem, the new variant, and the complete characterisation of maximal graphs without 2-factors are based on the alternating-chain theory from Gallai (1950) and Belck (1950). These are independent external results by different authors, not self-citations or internal fits. No equations or steps in the provided claims reduce a prediction or characterisation to a fitted parameter or self-defined input by construction. The derivation is presented as building upon cited foundational work rather than deriving from its own outputs, making the contribution self-contained against external benchmarks. Any questions about transfer of the 1950 results to the 2-factor case with leaves concern correctness or applicability, not circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard graph-theoretic background and the 1950 alternating-chain theory; no free parameters or invented entities are mentioned in the abstract.

axioms (2)
  • standard math Finite undirected graphs without multiple edges or loops are the objects under study.
    Implicit throughout all statements about regular graphs, leaves, and factors.
  • domain assumption The alternating-chain theory developed by Gallai and by Belck in 1950 is correct and directly applicable.
    The abstract states that the new proofs and characterization are based on those works.

pith-pipeline@v0.9.0 · 5690 in / 1450 out tokens · 52088 ms · 2026-05-18T07:39:40.627928+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    Akiyama and M

    J. Akiyama and M. Kano,Factors and Factorizations of Graphs. Proof Techniques in Factor Theory, Lecture Notes in Math. 2031, Springer, Heidelberg, 2011

    work page 2031

  2. [2]

    Baebler, ¨Uber die Zerlegung regul¨ arer Streckenkomplexe ungerader Ordnung,Com- ment

    F. Baebler, ¨Uber die Zerlegung regul¨ arer Streckenkomplexe ungerader Ordnung,Com- ment. Math. Helv.10(1938), 275–287

    work page 1938

  3. [3]

    Belck, Regul¨ are Faktoren von Graphen,J

    H.-B. Belck, Regul¨ are Faktoren von Graphen,J. Reine Angew. Math.188(1950), 228– 252

    work page 1950

  4. [4]

    Berge,th´ eorie des graphes et ses applications, Dunod, Paris, 1958

    C. Berge,th´ eorie des graphes et ses applications, Dunod, Paris, 1958. English translation by A. Doig,The Theory of Graphs and its Applications, Methuen, London and Wiley, New York, 1962; reprinted asThe Theory of Graphs, Dover, Mineola NY, 2001

    work page 1958

  5. [5]

    Bollob´ as,Extremal Graph Theory, Academic Press, London-New York, 1978, and Dover, Mineola NY, 2004

    B. Bollob´ as,Extremal Graph Theory, Academic Press, London-New York, 1978, and Dover, Mineola NY, 2004

    work page 1978

  6. [6]

    Edmonds, Paths, trees and flowers,Canadian

    J. Edmonds, Paths, trees and flowers,Canadian. J. Math.17(1965), 449–467. 15

    work page 1965

  7. [7]

    L.R. Ford Jr. and D.R. Fulkerson,Flows in Networks, Princeton, Princeton NJ, 1962

    work page 1962

  8. [8]

    Gallai, On factorisation of graphs,Acta Math

    T. Gallai, On factorisation of graphs,Acta Math. Acad. Sci. Hungar.1(1950), 133–153

    work page 1950

  9. [9]

    Hanson, C.O.M

    D. Hanson, C.O.M. Loten, and B. Toft, On interval colourings of bi-regular bipartite graphs,Ars Combin.50(1998), 23–32

    work page 1998

  10. [10]

    H¨ aggkvist,Bootstrapping Theorems by Petersen, Baebler, Belck and Gallai, Research Report 11 (2001), Dept

    R. H¨ aggkvist,Bootstrapping Theorems by Petersen, Baebler, Belck and Gallai, Research Report 11 (2001), Dept. of Mathematics, Ume˚ a University. At the meetingCombinatorics in Cambridgecelebrating B´ ela Bollob´ as’s 60th birthday, August 4–7, 2003, H¨ aggkvist presented a lectureFactors Galorewith material from the report and asked for information about...

    work page 2001

  11. [11]

    Kostochka, A

    A.V. Kostochka, A. Raspaud, B. Toft, D.B. West and D. Zirlin, Cut-edges and regular factors in graphs of odd degree,Graphs Combin.37(2021), 199–207

    work page 2021

  12. [12]

    K¨ onig,Theorie Der Endlichen und Unendlichen Graphen

    D. K¨ onig,Theorie Der Endlichen und Unendlichen Graphen. Kombinatorische Topolo- gie der Streckenkomplexie, Akademische Verlagsgesellshaft, Leipzig, 1936, Chelsea, New York, 1950, and Teubner, Leipzig, 1986. English translation by R. McCoart,Theory of Finite and Infinite Graphs, Birkh¨ auser, Boston MA, 1990

    work page 1936

  13. [13]

    Lov´ asz, Three short proofs in graph theory,J

    L. Lov´ asz, Three short proofs in graph theory,J. Combin. Theory Ser. B19(1975), 269–271

    work page 1975

  14. [14]

    Lov´ asz and M.D

    L. Lov´ asz and M.D. Plummer,Matching Theory, North Holland, Amsterdam, 1986, and Chelsea, Providence RI, 2009

    work page 1986

  15. [15]

    The factorization of linear graphs

    F.G. Maunsell, A note on Tutte’s paper “The factorization of linear graphs”,J. London Math. Soc.27(1952), 127–128

    work page 1952

  16. [16]

    Petersen, Die Theorie der regul¨ aren graphs1,Acta Math.15(1891), 193–220

    J. Petersen, Die Theorie der regul¨ aren graphs1,Acta Math.15(1891), 193–220

    work page

  17. [17]

    Sabidussi, Correspondence between Sylvester, Petersen, Hilbert and Klein on invari- ants and the factorization of graphs 1889–1891,Discrete Math.100(1992), 99–155

    G. Sabidussi, Correspondence between Sylvester, Petersen, Hilbert and Klein on invari- ants and the factorization of graphs 1889–1891,Discrete Math.100(1992), 99–155

    work page 1992

  18. [18]

    Tutte, The factorization of linear graphs,J

    W.T. Tutte, The factorization of linear graphs,J. London Math. Soc.22(1947), 107–111

    work page 1947

  19. [19]

    Tutte, The factors of graphs,Canad

    W.T. Tutte, The factors of graphs,Canad. J. Math.4(1952), 314–328. Reprinted in I. Gessel and G.-C. Rota (eds.),Classic papers in Combinatorics, Birkh¨ auser, Boston, 1987, pp. 164–178

    work page 1952

  20. [20]

    Tutte, A short proof of the factor theorem for finite graphs,Canad

    W.T. Tutte, A short proof of the factor theorem for finite graphs,Canad. J. Math.6 (1954), 347–352

    work page 1954

  21. [21]

    graph(s)

    Q.R. Yu and G. Liu,Graph Factors and Matching Extensions, Higher Education Press, Beijing, and Springer, Berlin, 2009. 1 Although Petersen wrote the paper in German, which normally uses capitals for nouns, he consistently uses “graph(s)” without capital. He explains the reason for that early in the paper: “Englische Verfasser haben f¨ ur ¨ ahnliche Figure...

    work page 2009