pith. sign in

arxiv: 2404.06445 · v3 · pith:5IRSVADHnew · submitted 2024-04-09 · 🧮 math.CO · cs.DM

Extremal minimal bipartite matching covered graphs

Amit Kumar Mallik , Ajit A. Diwan , Nishad Kothari This is my paper

Pith reviewed 2026-05-24 01:53 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords bipartite graphsmatching covered graphsminimal graphsextremal graphsear decompositionperfect matchingstrees
0
0 comments X

The pith

Every extremal minimal bipartite matching covered graph arises from two trees without degree-two vertices by joining their corresponding leaves.

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

The paper establishes a complete structural description of extremal minimal bipartite matching covered graphs. These are the graphs that attain the lower bound of exactly 2(m-n+2) degree-two vertices among all minimal matching covered graphs on n vertices and m edges. The construction takes two copies of any tree with no degree-two vertices and adds a perfect matching between their leaves. A reader would care because the result turns an abstract bound into an explicit family of graphs that can be generated and studied directly. The same approach yields characterizations for the other four extremal notions derived from Lovász-Plummer bounds, with two reduced to the tree-pair construction via standard matching operations.

Core claim

Every extremal minimal bipartite matching covered graph G is obtained from two copies of a tree T and T' devoid of degree-two vertices by adding edges, each of which joins a leaf of T with the corresponding leaf of T'. The same style of description covers two of the remaining extremal classes; the other two classes reduce to these via standard operations. The paper also records relationships among the five extremal classes and supplies tight examples and conjectures for the k-extendable case.

What carries the argument

The leaf-pairing construction on two copies of a degree-two-free tree, which forces minimality while meeting the exact count of 2(m-n+2) degree-two vertices.

If this is right

  • Every such graph is minimal: deleting any edge destroys the matching-covered property.
  • The number of degree-two vertices is precisely 2(m-n+2).
  • The five different extremal classes arising from the Lovász-Plummer bounds are related by inclusion or by reduction via matching operations.
  • Tight examples for the conjectured bounds on minimal k-extendable bipartite graphs are obtained by the same tree-pair construction.

Where Pith is reading between the lines

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

  • The leaf-pairing construction may generate infinite families of 3-regular bipartite graphs that are minimal matching covered when the trees are chosen to be paths or stars.
  • The same structural description could be used to decide in polynomial time whether a given bipartite graph belongs to any of the five extremal classes.
  • Conjectured bounds for k-extendable graphs would follow if the tree-pair graphs admit natural generalizations that remain minimal k-extendable.

Load-bearing premise

Hetyei's ear decomposition theorem supplies the lower bound of 2(m-n+2) degree-two vertices that defines extremality.

What would settle it

A connected bipartite graph on at least four vertices that is minimal matching covered, has exactly 2(m-n+2) degree-two vertices, yet cannot be produced by taking two degree-two-free trees and pairing their leaves.

Figures

Figures reproduced from arXiv: 2404.06445 by Ajit A. Diwan, Amit Kumar Mallik, Nishad Kothari.

Figure 1
Figure 1. Figure 1: a bipartite matching covered graph and its ear decomposition [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: illustration of Karpov’s characterization of extremal minimal 2-connected graphs [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: a member of H2 — deleting the 2-edges results in two copies of a Halin tree [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: (a) a member of H3: deleting the 2-edges results in two copies of a cubic Halin tree (b) a member of H4: deleting the 2-edges results in two copies of a star 5 [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: a counterexample to the converse of Proposition [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: extremal graphs that may not be obtained from a tree by isomorphic leaf matching [PITH_FULL_IMAGE:figures/full_fig_p008_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: an illustration of Theorem 1.9 that relates H0 and H2 To see an example of the above theorem, consider the graph G shown in Figure 7a and its partial retract Gb shown in Figure 7b. The reader may verify using Theorem 1.1 and Lemma 1.6 that G and Gb belong to H. Note that G ∈ H0 as |E2(G)| = m − n + 2. On the other hand, Gb ∈ H2 as |V2(Gb)| = 2(m − n + 2). Likewise, using the notion of partial retract, we a… view at source ↗
Figure 8
Figure 8. Figure 8: an illustration of Theorem 1.10 that relates H1 and H4 To see an example of the above theorem, consider the graph G shown in Figure 8a and its partial retract Gb shown in Figure 8b. The reader may verify using Theorem 1.1 and Lemma 1.6 that G and Gb belong to H. Note that G ∈ H1 as |E2(G)| = n+10 6 . On the other hand, Gb ∈ H4 as |E(Gb)| = 3n−6 2 . We have thus stated our characterizations for all of the e… view at source ↗
Figure 9
Figure 9. Figure 9: The Θ graph {Θ} H∗ 3 H∗ 4 H∗ 2 H1 H0 7.2 7.4 7.11 4.2 [PITH_FULL_IMAGE:figures/full_fig_p010_9.png] view at source ↗
Figure 11
Figure 11. Figure 11: illustrations for the proof of statement [PITH_FULL_IMAGE:figures/full_fig_p016_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: illustrations for the proof of statement [PITH_FULL_IMAGE:figures/full_fig_p017_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: illustration of balanced 2-cut decomposition and 2-edge splicing [PITH_FULL_IMAGE:figures/full_fig_p018_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: illustration for the proof of the Main Theorem [PITH_FULL_IMAGE:figures/full_fig_p021_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: an illustration of bicontracton and bisplitting [PITH_FULL_IMAGE:figures/full_fig_p024_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: an illustration of restricted bicontraction and restricted bisplitting [PITH_FULL_IMAGE:figures/full_fig_p024_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: an example of isomorphic k-leaf matching operation For instance, the graph G shown in Figure 17b is obtained from the tree T shown in Figure 17a by isomorphic 2-leaf matching; the green coloured vertices represent L(G) and L(T), respectively. Figures 18 and 19 also depict examples of the isomorphic k-leaf matching operation. The reader may verify that the isomorphic leaf matching operation defined in Subs… view at source ↗
Figure 18
Figure 18. Figure 18: J3,4 obtained from K1,4 by isomorphic 3-leaf matching Now, let G be the graph obtained from a double star Dp,q, where p, q ⩾ 2, by isomorphic k-leaf matching. We provide an alternative viewpoint for constructing G. Let M1, M2, M3 and M4 be the graphs obtained from the disjoint union of p − 1, k, q − 1 and k copies of K2, respectively, and let Ai and Bi denote fixed color classes of Mi for each i ∈ {1, 2, … view at source ↗
Figure 19
Figure 19. Figure 19: The graph obtained from D4,5 by isomorphic 2-leaf matching Proof. We use the alternative viewpoint that was described in the paragraph preceding the lemma statement, and the notation defined therein. Let A := A1∪A2∪A3∪A4, and likewise for B. Let S be any nonempty subset of A. If S meets each Ai , where i ∈ {1, 2, 3, 4}, then N(S) = B. Otherwise, there exists an i ∈ {1, 2, 3, 4} such that S ∩ Ai ̸= ∅ but S… view at source ↗
Figure 20
Figure 20. Figure 20: an illustration of replacing uv by J3,4 Now, suppose that e /∈ Mu ∪ Mr ∪ Mv; consequently, e ∈ ∂(Au, Br) ∪ ∂(Bv, Ar). Adjust notation so that e := uibj . If aj is matched in M then let vℓ ∈ Bv denote its matched neighbour; otherwise, since p ⩾ k, let vℓ denote any unmatched vertex in Bv; we shall define a perfect matching M′′ of G′ that contains M in both cases. By Corollary 8.22, the graph H := G − uyi −… view at source ↗
read the original abstract

A connected graph, on four or more vertices, is matching covered (aka 1-extendable) if every edge is present in some perfect matching. An ear decomposition theorem exists for bipartite matching covered graphs due to Hetyei. From the results and proofs of Lov\'asz and Plummer, that rely on Hetyei's theorem, one may deduce that any minimal bipartite matching covered graph has at least $2(m-n+2)$ vertices of degree two (where minimal means that deleting any edge results in a graph that is not matching covered); such a graph is said to be extremal if it attains the stated lower bound. In this paper, we provide a complete characterization of the class of extremal minimal bipartite matching covered graphs. In particular, we prove that every such graph $G$ is obtained from two copies of a tree devoid of degree two vertices, say $T$ and $T'$, by adding edges -- each of which joins a leaf of $T$ with the corresponding leaf of $T'$. Apart from the aforementioned bound, there are four other bounds that appear in, or may be deduced from, the work of Lov\'asz and Plummer. Each of these bounds leads to a notion of extremality. In this paper, we obtain a complete characterization of all of these extremal classes and also establish relationships between them. Two of our characterizations are in the same spirit as the one stated above. For the remaining two extremal classes, we reduce each of them to one of the already characterized extremal classes using standard matching theoretic operations. A connected graph is k-extendable if it has a matching of cardinality $k$ and each such matching extends to a perfect matching. We also discuss bounds proved by Lou (1999) for minimal k-extendable bipartite graphs. We conjecture stronger bounds and provide evidence for our conjectures by constructing tight examples that are straightforward generalizations of the ones that appear in the 1-extendable case.

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

0 major / 3 minor

Summary. The paper claims a complete structural characterization of extremal minimal bipartite matching covered graphs: every such graph arises from two copies T and T' of a tree with no degree-2 vertices by adding a perfect matching between their leaves. It further characterizes the four other extremal classes obtained from bounds deducible from Lovász-Plummer (via Hetyei ear decompositions), reduces two of them to the already-characterized classes via standard matching operations, and supplies conjectured stronger bounds for minimal k-extendable bipartite graphs together with tight constructions that generalize the 1-extendable case.

Significance. If the characterizations hold, they supply explicit, constructive descriptions of the extremal graphs attaining each of the five bounds, thereby clarifying the structure of minimal matching covered graphs and their ear decompositions. The constructions are parameter-free once the trees are chosen, and the converse directions rely on forcing the ear decomposition to split into two such trees; this is a concrete advance over the mere existence of the lower bound 2(m-n+2). The stress-test concern about post-hoc choices in ear arguments does not appear to affect the load-bearing counting or the decomposition steps.

minor comments (3)
  1. [Abstract] The abstract asserts that two of the four additional extremal classes are reduced to already-characterized ones, but does not name the matching-theoretic operations used; a single sentence in the introduction listing them would improve readability.
  2. [Main characterization theorem] Theorem statements for the main characterization (presumably in §3) should explicitly record that the added edges form a perfect matching between the leaf sets; the current wording “adding edges—each of which joins a leaf of T with the corresponding leaf of T'” is slightly ambiguous about bijectivity.
  3. [Section on k-extendable graphs] The k-extendable conjectures in the final section are supported only by constructions; if the manuscript contains any partial proof or obstruction argument, it should be stated explicitly so readers know the precise status of the conjectures.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the positive assessment, including the accurate summary of our structural characterizations and the recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation grounded in external theorem

full rationale

The paper's core result is a structural characterization of extremal minimal bipartite matching covered graphs, obtained by applying Hetyei's ear decomposition theorem (external, via Lovász-Plummer) to deduce the bound 2(m-n+2) on degree-2 vertices, then constructing graphs from two trees with no degree-2 vertices joined by a perfect matching on leaves, and proving the converse via ear decompositions. No step reduces by definition to its own inputs, renames a known result as new, or relies on a load-bearing self-citation; the cited theorems are independent prior results, and the new constructions attain the bound without statistical forcing or ansatz smuggling. The additional characterizations for other extremal classes similarly reduce to the main one or use standard operations, remaining self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on Hetyei's ear-decomposition theorem and on the four bounds deduced from Lovasz-Plummer; no free parameters or new entities are introduced.

axioms (1)
  • domain assumption Hetyei's ear decomposition theorem for bipartite matching covered graphs
    Invoked to obtain the lower bound 2(m-n+2) on degree-two vertices that defines the extremal classes.

pith-pipeline@v0.9.0 · 5904 in / 1181 out tokens · 23412 ms · 2026-05-24T01:53:29.498917+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

16 extracted references · 16 canonical work pages

  1. [1]

    J. A. Bondy and U. S. R. Murty. Graph Theory. Springer, 2008

    work page 2008

  2. [2]

    M. H. Carvalho, C. L. Lucchesi, and U. S. R. Murty. Graphs with independent perfect matchings. J. Graph Theory, 48:19–50, 2005

    work page 2005

  3. [3]

    G. A. Dirac. Minimally 2-connected graphs. 1967

    work page 1967

  4. [4]

    P. A. Fabres, N. Kothari, and M. H. Carvalho. Minimal braces. Journal of Graph Theory, 96(4):490–509, 2021

    work page 2021

  5. [5]

    R. Halin. Studies on minimally n-connected graphs. In Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) , pages 129–136, 1971

    work page 1969

  6. [6]

    G. Hetyei. Rectangular configurations which can be covered by 2 × 1 rectangles. P´ ecsi Tan. Foisk. K¨ ozl, 8:351–367, 1964

    work page 1964

  7. [7]

    Hoffmann-Ostenhof, K

    A. Hoffmann-Ostenhof, K. Noguchi, and K. Ozeki. On homeomorphically irreducible spanning trees in cubic graphs. Journal of Graph Theory , 89(2):93–100, 2018

    work page 2018

  8. [8]

    D. V. Karpov. Minimal k-connected graphs with minimal number of vertices of degree k. Journal of Mathematical Sciences , 212:666–682, 2016

    work page 2016

  9. [9]

    C. H. C. Little. A theorem on connected graphs in which every edge belongs to a 1-factor. Journal of the Australian Mathematical Society , 18(4):450–452, 1974

    work page 1974

  10. [10]

    D. Lou. On the structure of minimally n-extendable bipartite graphs. Discrete Mathe- matics, 202(1):173–181, 1999

    work page 1999

  11. [11]

    Lov´ asz and M

    L. Lov´ asz and M. D. Plummer. Matching Theory. Number 29 in Annals of Discrete Mathematics. Elsevier Science, 1986

    work page 1986

  12. [12]

    C. L. Lucchesi and U. S. R. Murty. Perfect Matchings: A Theory of Matching Covered Graphs. Algorithms and Computation in Mathematics. Springer Nature Switzerland, Imprint: Springer, 2024

    work page 2024

  13. [13]

    J. G. Oxley. On some extremal connectivity results for graphs and matroids. Discrete Mathematics, 41(2):181–198, 1982

    work page 1982

  14. [14]

    M. D. Plummer. On n-extendable graphs. Discrete Mathematics, 31(2):201–210, 1980

    work page 1980

  15. [15]

    M. D. Plummer. Matching extension in bipartite graphs. Technical report, 1986. 38

    work page 1986

  16. [16]

    H. Whitney. 2-isomorphic graphs. American Journal of Mathematics, 57:245–254, 1933. 39

    work page 1933