pith. sign in

arxiv: 2604.17226 · v1 · submitted 2026-04-19 · 🧮 math.CO

Separating Matchings in Cubic Graphs

Juan Guti\'errez , Renzo G\'omez This is my paper

Pith reviewed 2026-05-10 06:30 UTC · model grok-4.3

classification 🧮 math.CO
keywords separating matchingscubic graphsmaximum matching sizematching cutsclaw-free graphsbipartite graphssubcubic graphsdisconnected factors
0
0 comments X

The pith

Cubic graphs that admit a separating matching always have one of size at least n/2 minus 2.

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

The paper defines a separating matching as any matching whose removal increases the number of connected components in the graph. It first establishes that every subcubic graph except exactly eight has at least one separating matching. The main result then gives a lower bound of n/2 minus 2 on the size of the largest separating matching in any cubic graph on n vertices that possesses such a matching at all. Tighter statements hold for claw-free cubic graphs, where the maximum size equals exactly n/2, and for bipartite cubic graphs under an extra assumption, where the bound improves to n/2 minus 1 except for four cases. These size guarantees extend earlier observations about matchings that disconnect graphs.

Core claim

Every cubic graph G on n vertices that admits a separating matching satisfies mms(G) greater than or equal to n/2 minus 2. For bipartite cubic graphs, assuming a conjecture, the problem reduces to a recursively defined class for which mms(G) is at least n/2 minus 1 up to four exceptional graphs. Every claw-free cubic graph satisfies mms(G) equal to n/2.

What carries the argument

A separating matching, defined as a matching whose removal increases the number of connected components, with mms(G) tracking its maximum possible size in G.

If this is right

  • All subcubic graphs except eight specific ones possess separating matchings.
  • Claw-free cubic graphs achieve a maximum separating matching of size exactly n/2.
  • Bipartite cubic graphs satisfy a bound of n/2 minus 1 under an additional assumption, aside from four exceptions.
  • The size guarantees apply directly to the study of matching cuts and disconnected 2-factors in cubic graphs.

Where Pith is reading between the lines

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

  • The same approach of bounding maximum separating matchings could be tested on graphs with maximum degree four or higher.
  • The eight exceptional subcubic graphs may indicate minimal structures that force small separating matchings.
  • Algorithms for constructing large separating matchings in cubic graphs could follow from the classification used in the proofs.
  • The results connect to questions about how matchings affect edge-connectivity in regular graphs.

Load-bearing premise

The lower bound applies only to cubic graphs that already possess at least one separating matching.

What would settle it

A cubic graph on n vertices that admits a separating matching but whose largest separating matching has size smaller than n/2 minus 2 would disprove the main result.

Figures

Figures reproduced from arXiv: 2604.17226 by Juan Guti\'errez, Renzo G\'omez.

Figure 1
Figure 1. Figure 1: Family D of nondecomposable subcubic graphs: (a) D0; (b) D1; (c) D2; (d) D3; (e) D4; (f) D5; (g) D6; and (h) D7. (i) every vertex of degree two is adjacent only to vertices of degree three in G. In what follows, we relate the study of nondecomposable subcubic graphs to the study of nondecomposable cubic multigraphs (graphs that may contain parallel edges and loops). In this regard, given a subcubic graph G… view at source ↗
Figure 2
Figure 2. Figure 2: Situations in the proof of Theorem 4 when a tie [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Situations in the proof of Theorem 4. In [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: (a) the Headwood graph; (b) K3,3; and (c) a star product between the Heawood graph and K3,3. Funk [6] studied this class of graphs and conjectured that the following holds. Conjecture 11 (Funk, 2003). Let G be a 2-factor Hamiltonian k-regular bipartite graph. Then, either k = 2 and G is a circuit or k = 3 and G ∈ F. Observe that the complement of a 2-factor in a cubic graph is a perfect matching. So, if a … view at source ↗
Figure 5
Figure 5. Figure 5: (a) Vertex u has degree 3 in F1; and (b) vertex u has degree 2 in F1. We depict by dashed lines the edges incident to u in F1. Moreover, highlighted lines indicate edges that belong to F. Finally, we depict by different kind of lines the colors in χ. Lemma 13. Let G1 and G2 be bicubic graphs such that G1 contains an almost 2-factor, and let u ∈ V (G1) and v ∈ V (G2). If G = (G1, u) ∗ (G2, v), then G has an… view at source ↗
Figure 6
Figure 6. Figure 6: these four special graphs. (a) (b) (d) (c) [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: (a) A maximum separating matching of H0; and (b) a maximum separating matching of F1. The curvy edges indicate the edges in the matching [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: The graphs (a) F2 and; (b) H1. The curvy edges induce a maximum separating matching. a separating matching, a contradiction. Therefore, either MA ⊆ S or MB ⊆ S, and |S| ≤ 5. Now, we consider the star product (F2, u) ∗ (K3,3, v). By symmetry, this product generates four different graphs (up to isomorphism) depending on the choice for u. Analogously as in the case of F1, we labeled with 1, 2, 3 and 4 the ver… view at source ↗
Figure 9
Figure 9. Figure 9: The graphs (a) H2; (b) H3; (c) H4; and (d) F3. The curvy edges induce a separating matching. a maximum separating matching has size |V (G)|/2. On the other hand, if G belongs to F, the size of maximum separating matching is |V (G)|/2 − 1, unless for F0, F1, F2 and F3, in which case, the maximum separating matching has size |V (G)|/2 − 2. Since these four graphs have constant size, the following result foll… view at source ↗
Figure 10
Figure 10. Figure 10: (a) H5; (b) H6; and (c) H7. The curvy edges induce a maximum separating matching. M. Let Gu be the component of G − uv containing u. Since M is perfect, Gu has even order. However, u has degree 2 in Gu, while every other vertex has degree 3, which is impossible. We will use the following characterization due to Oum [17]. Lemma 16 (Proposition 1 of [17]). A graph G is cubic, bridgeless, and claw-free if an… view at source ↗
Figure 11
Figure 11. Figure 11: (a) A ring of diamonds. (b) A claw-free cubic graph obtained from [PITH_FULL_IMAGE:figures/full_fig_p015_11.png] view at source ↗
read the original abstract

We study separating matchings in graphs, that is, matchings whose removal increases the number of connected components, and focus on determining the maximum size of such a matching in a graph $G$, denoted by $\mathrm{mms}(G)$. We show that every subcubic graph admits a separating matching, except for exactly eight graphs, which allows us to focus on bounding $\mathrm{mms}(G)$ for cubic graphs. Our main results show that every cubic graph $G$ on $n$ vertices that admits a separating matching satisfies $\mathrm{mms}(G) \ge n/2 - 2$. For bipartite cubic graphs, assuming a conjecture of Funk, the problem reduces to a recursively defined class $\mathcal{F}$, for which we prove that $\mathrm{mms}(G) \ge n/2 - 1$, up to four exceptional graphs. In contrast, we show that every claw-free cubic graph satisfies $\mathrm{mms}(G) = n/2$. These results extend previous work on matching cuts and disconnected $2$-factors, and provide the first systematic study of maximum separating matchings.

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

Summary. The manuscript studies separating matchings (matchings whose removal increases the number of connected components) and the function mms(G) giving the maximum size of such a matching. It first classifies all subcubic graphs and proves that exactly eight lack any separating matching. For every cubic graph G on n vertices that admits at least one separating matching, the paper proves mms(G) ≥ n/2 − 2. Stronger results are given for two subclasses: every claw-free cubic graph satisfies mms(G) = n/2, while for bipartite cubic graphs, assuming Funk’s conjecture, mms(G) ≥ n/2 − 1 holds up to four exceptional graphs after reduction to a recursively defined class F. The work extends earlier results on matching cuts and disconnected 2-factors.

Significance. If the proofs are correct, the paper supplies the first systematic treatment of maximum separating matchings in cubic graphs. The explicit classification of the eight exceptional subcubic graphs, the uniform n/2 − 2 lower bound for all other cubic graphs, the equality result for claw-free graphs, and the conditional improvement for bipartite graphs (via reduction to class F) are concrete advances. These bounds are falsifiable and directly extend prior work on matching cuts, making the manuscript a useful reference for further research in matching theory and cubic graph structure.

major comments (2)
  1. [§3] §3 (Classification theorem): the claim that precisely eight subcubic graphs lack separating matchings is load-bearing for the main bound; the case analysis must explicitly rule out all other small or low-connectivity configurations, and the proof should state whether the eight graphs were found by exhaustive enumeration or by structural argument.
  2. [§5] §5 (Bipartite case, reduction to F): the recursive definition of class F and the appeal to Funk’s conjecture are central to the n/2 − 1 claim; the manuscript should verify that the four exceptional graphs in F are indeed the only ones and that the induction step does not inadvertently assume the conjecture outside the stated scope.
minor comments (4)
  1. [Abstract] The abstract states the bipartite bound holds “up to four exceptional graphs” but does not name or reference them; adding a short table or explicit list in the abstract or §5 would improve clarity.
  2. [§1] Notation for mms(G) and separating matching is introduced in the abstract but not repeated at the start of §1; a one-sentence definition in the introduction would aid readers.
  3. [References] The citation for Funk’s conjecture is missing from the bibliography; please supply the full reference.
  4. [§3] If the eight exceptional graphs are illustrated, ensure the figures are cross-referenced in the text of §3 and that vertex counts are consistent with the n/2 − 2 statement.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the constructive comments. We address each major comment below and will incorporate the suggested clarifications to improve the exposition.

read point-by-point responses

  1. Referee: [§3] §3 (Classification theorem): the claim that precisely eight subcubic graphs lack separating matchings is load-bearing for the main bound; the case analysis must explicitly rule out all other small or low-connectivity configurations, and the proof should state whether the eight graphs were found by exhaustive enumeration or by structural argument.

    Authors: The classification in Section 3 proceeds by structural case analysis on the connectivity and block structure of subcubic graphs, rather than exhaustive enumeration. We partition into cases according to the presence of bridges, cut-vertices, and the 2-connected components, showing in each case either that a separating matching exists or that the graph must contain one of the eight exceptions as a subgraph. Low-connectivity configurations are handled explicitly by reducing to smaller components or by constructing a matching that separates a leaf block. We will revise the section to state this structural nature upfront and add a short paragraph summarizing the exhaustive coverage of low-connectivity cases. revision: yes

  2. Referee: [§5] §5 (Bipartite case, reduction to F): the recursive definition of class F and the appeal to Funk’s conjecture are central to the n/2 − 1 claim; the manuscript should verify that the four exceptional graphs in F are indeed the only ones and that the induction step does not inadvertently assume the conjecture outside the stated scope.

    Authors: The reduction to class F is constructed so that every graph in F either belongs to one of the four listed exceptions or admits a recursive decomposition to which the induction hypothesis applies directly. Funk’s conjecture is invoked only on the base cases of the recursion (which are explicitly checked) and never on graphs outside the reduced class. We will add a clarifying paragraph in Section 5 that (i) confirms the four exceptions are the only ones by outlining the verification for the finite base of the recursion and (ii) states that the induction step remains within the scope where the conjecture is assumed. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper first exhaustively classifies all subcubic graphs and proves that exactly eight lack any separating matching; this classification is independent of the subsequent size bound. For the remaining cubic graphs that admit at least one separating matching, the lower bound mms(G) ≥ n/2 - 2 is obtained via direct structural arguments on cubic graphs (case analysis on bridges, cut-vertices, and matching extensions). The claw-free case is handled by a separate equality proof, and the bipartite case is reduced to an external conjecture of Funk plus a recursive class F whose bound is proved by induction. No step equates a derived quantity to a fitted parameter, renames a known result, or relies on a self-citation whose content is itself unverified; the derivation chain is self-contained against external graph-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims rest on standard definitions of matchings, connectivity, and cubic graphs plus one external conjecture for the bipartite case; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • standard math Standard graph-theoretic definitions of matchings and connected components.
    Invoked throughout to define separating matchings and mms(G).

pith-pipeline@v0.9.0 · 5490 in / 1101 out tokens · 50121 ms · 2026-05-10T06:30:04.245420+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

20 extracted references · 20 canonical work pages

  1. [1]

    J. A. Bondy and U. S. R. Murty.Graph Theory, volume 244 ofGraduate Texts in Mathe- matics. Springer, 2008

    work page 2008

  2. [2]

    Bouquet and C

    V. Bouquet and C. Picouleau. The complexity of the perfect matching-cut problem.J. Graph Theory, 108(3):432–462, 2025

    work page 2025

  3. [3]

    V. Chvátal. Recognizing decomposable graphs.J. Graph Theory, 8(1):51–53, 1984

    work page 1984

  4. [4]

    Diestel.Graph theory, volume 173 ofGraduate Texts in Mathematics

    R. Diestel.Graph theory, volume 173 ofGraduate Texts in Mathematics. Springer, Berlin, fifth edition, 2018. 15

    work page 2018

  5. [5]

    A. Diwan. Disconnected 2-factors in planar cubic bridgeless graphs.J. Combin. Theory Ser. B, 84(2):249–259, 2002

    work page 2002

  6. [6]

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

    work page 2003

  7. [7]

    Gorsky, T

    M. Gorsky, T. Johanni, and S. Wiederrecht. A note on the 2-factor Hamiltonicity Conjec- ture.Discrete Math., 348(6):Paper No. 114442, 2025

    work page 2025

  8. [8]

    R. Graham. On primitive graphs and optimal vertex assignments.Ann. New York Acad. Sci., 175:170–186, 1970

    work page 1970

  9. [9]

    D. König. über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math. Ann., 77(4):453–465, 1916

    work page 1916

  10. [10]

    Las Vergnas

    M. Las Vergnas. A note on matchings in graphs.Cahiers du Centre d’Études de Recherche Opérationnelle, 17(2-3-4):257–260, 1975. Colloque sur la Théorie des Graphes (Paris, 1974)

    work page 1975

  11. [11]

    Le and V

    H. Le and V. B. Le. A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter.Theoret. Comput. Sci., 770:69–78, 2019

    work page 2019

  12. [12]

    Le and V

    H. Le and V. B. Le. Complexity results for matching cut problems in graphs without long induced paths. InGraph-theoretic concepts in computer science, volume 14093 ofLecture Notes in Comput. Sci., pages 417–431. Springer, Cham, 2023

    work page 2023

  13. [13]

    Maximizing matching cuts, 2023

    Van Bang Le, Felicia Lucke, Daniël Paulusma, and Bernard Ries. Maximizing matching cuts, 2023

    work page 2023

  14. [14]

    Lucke, D

    F. Lucke, D. Paulusma, and B. Ries. On the complexity of matching cut for graphs of bounded radius andH-free graphs.Theoret. Comput. Sci., 936:33–42, 2022

    work page 2022

  15. [15]

    Lucke, D

    F. Lucke, D. Paulusma, and B. Ries. Dichotomies for maximum matching cut:H-freeness, bounded diameter, bounded radius.Theoret. Comput. Sci., 1017:Paper No. 114795, 18, 2024

    work page 2024

  16. [16]

    A. Moshi. Matching cutsets in graphs.J. Graph Theory, 13(5):527–536, 1989

    work page 1989

  17. [17]

    S. Oum. Perfect matchings in claw-free cubic graphs.Electron. J. Combin., 18(1):Paper 62, 6, 2011

    work page 2011

  18. [18]

    Patrignani and M

    M. Patrignani and M. Pizzonia. The complexity of the matching-cut problem. InGraph- theoretic concepts in computer science (Boltenhagen, 2001), volume 2204 ofLecture Notes in Comput. Sci., pages 284–295. Springer, Berlin, 2001

    work page 2001

  19. [19]

    Petersen

    J. Petersen. Die Theorie der regulären graphs.Acta Math., 15(1):193–220, 1891

    work page

  20. [20]

    D. P. Sumner. Graphs with 1-factors.Proceedings of the American Mathematical Society, 42(1):8–12, 1974. 16

    work page 1974