pith. sign in

arxiv: 2607.00608 · v1 · pith:VVXFZXCUnew · submitted 2026-07-01 · 🧮 math.CO

Near-bipartite bricks in which every b-invariant edge is a forcing edge

Yaxian Zhang , Fuliang Lu This is my paper

Pith reviewed 2026-07-02 11:07 UTC · model grok-4.3

classification 🧮 math.CO
keywords near-bipartite bricksb-invariant edgesforcing edgesmatching covered graphsLovasz decompositionperfect matchingsbricks and braces
0
0 comments X

The pith

Near-bipartite bricks other than K4, the complement of C6, and the Petersen graph have every b-invariant edge as a forcing edge.

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

The paper solves the Lucchesi-Murty problem for the subclass of near-bipartite bricks. It supplies a complete characterization of those near-bipartite bricks, distinct from the three small excluded graphs, in which every b-invariant edge is a forcing edge. The work rests on the unique Lovasz decomposition of matching covered graphs into bricks and braces. A sympathetic reader cares because the result clarifies when a removable edge preserves the brick count b(G) versus lying in exactly one perfect matching. This advances the structural theory of bricks within matching covered graphs.

Core claim

A near-bipartite brick distinct from K4, the complement of C6, and the Petersen graph has the property that every b-invariant edge is a forcing edge, and the paper gives the explicit characterization of all such bricks.

What carries the argument

Near-bipartite brick under the Lovasz decomposition, the object for which b-invariant edges (removable edges that leave b(G) unchanged) are shown to coincide with forcing edges (edges in exactly one perfect matching).

If this is right

  • Any near-bipartite brick satisfying the stated conditions can be verified to have its b-invariant edges coincide exactly with its forcing edges.
  • The decomposition b(G) of a matching covered graph built from such bricks behaves predictably with respect to edge removal.
  • The characterization distinguishes the structural features that force an edge to be unique in the set of perfect matchings.

Where Pith is reading between the lines

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

  • The same coincidence between b-invariant and forcing edges may hold in other restricted classes of bricks beyond the near-bipartite case.
  • The result could be used to design a recognition procedure that checks the property directly on near-bipartite bricks.
  • Combining this characterization with existing results on other brick families might eventually classify all bricks with the property.
  • The work may illuminate how the number of bricks in a decomposition relates to the uniqueness of perfect matchings in larger matching covered graphs.

Load-bearing premise

The graphs under study are near-bipartite bricks distinct from the three excluded small graphs and the Lovasz decomposition into bricks is unique and well-defined.

What would settle it

Exhibit one near-bipartite brick, distinct from the three small graphs, that contains a b-invariant edge lying in more than one perfect matching.

Figures

Figures reproduced from arXiv: 2607.00608 by Fuliang Lu, Yaxian Zhang.

Figure 1
Figure 1. Figure 1: Illustration for Theorem 2. A pair {e1, e2} of edges in a matching covered graph G is a removable doubleton if G−e1 −e2 is matching covered, but neither G−e1 or G−e2 is. A nonbipartite matching covered graph G is near-bipartite if it has a removable doubleton such that its deletion will result in a bipartite matching covered subgraph. Near-bipartite graphs have also been studied from several other viewpoin… view at source ↗
Figure 2
Figure 2. Figure 2: Dashed lines indicate the edge classes that may have multiplicity [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Illustration for Claim 1: The graph R0. 7 [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Illustration of Case 1: the graph G8. By Theorem 7 (ii), each of u2 and v2 is incident with a b-invariant edges of G, which is a forcing edge of G. By Theorem 10, u2 ∈ NH(V e2 =3) = NH (v1) and v2 ∈ NH(U e1 =3) = NH(u1). Since dH(u2) = 3 and NH(u2) ⊆ V , |V | ≥ 3. Since dH(u1) = 2 and v2 ∈ NH(u1), |V (e2) ∪ NH(u1)| ≤ 3. By Theorem 13, |V | = |V (e2) ∪ NH(U e1 =3)| = |V (e2) ∪ NH(u1)| ≤ 3. So |V | = 3. Sinc… view at source ↗
Figure 5
Figure 5. Figure 5: Illustration of Case 2. For the vertex u2, |NH(u2)| = 3. Since {v2, v4} ⊆ NH (u2), either u2v3 ∈ E(G) or u2v1 ∈ E(G). For the case that u2v3 ∈ E(G), we have NG(u2) = {u1, v3, v4, v2}. Since dH(v1) = 2 and {u1, u2} ∩ NH(v1) = ∅, NG(v1) = {v2, u4, u3}. Next we consider the neighbors of u3. If dG(u3) = 3, by the symmetry of v3 and v4, then adjust notation such that u3v4 ∈ E(G). In this case, NG(u3) = {v4, v1,… view at source ↗
Figure 6
Figure 6. Figure 6: Illustration of Subclaim 2.1. Proof. Suppose, to the contrary, that |U| = |V | < 5. Then |U| = |V | = 4. Let U = {u1, u2, u3, u4} and V = {v1, v2, v3, v4}. Let n4 be the number of 4-degree vertices in U. Since dG(u1) = dG(u2) = 3, n4 = 1 or n4 = 2. If n4 = 2, then G ∼= R3 (see [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Illustration of Subclaim 2.2. Subcase 3.2. G contains a 6-cycle C ′ with |V (C ′ ) ∩ V (ei)| = 1 for i = 1, 2. Adjust notation such that C ′ = u1v3u3v1u4v4u1. If V (fi) ⊆ {v3, v4, u5, u6} for some 3 ≤ i ≤ 6, then C ′ must be an Mfi -alternating 6-cycle (see [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Illustration of Subclaim 2.3. By Theorem 7 (i), each of u3 and v5 is incident with at least one b-invariant edges of G, say f1 and f2, respectively. Since G contains no triangles, V (fi) ∩ V (R) = ∅ by Theorem 12. From above discussion, f1 6= f2 and we can assume that f1 = u3v4 and f2 = u4v5. Since f1 is a forcing edge, {f1, u1v3, u2v1, f2, u5v2} is the unique perfect 12 [PITH_FULL_IMAGE:figures/full_fig_… view at source ↗
Figure 9
Figure 9. Figure 9: Illustration for Case 3: The graph G10. From above discussion, all vertices of G, except for vertices in {u3, u5, v3, v5}, have degree three. Since G is not cubic, adjust notation such that dG(u3) ≥ 4 and dG(v3) ≥ 4. We can deduce that both u5 and v5 has degree three. Thus G ∼= G10, completing Case 3. The three cases prove Claim 2 and hence establish the classification when G is simple. Now we consider the… view at source ↗
read the original abstract

A connected graph is matching covered if it has at least one edge and every edge lies in some perfect matching.Lov\'asz proved that every matching covered graph G can be uniquely decomposed into a list of bricks and braces up to multiple edges. Denote by b(G) the number of bricks in such a decomposition. An edge e of G is removable if G-e is also matching covered; is b-invariant if e is removable and b(G-e)=b(G). Furthermore, an edge e of G is a forcing edge if it lies in precisely one perfect matching of G. Lucchesi and Murty proposed the problem of characterizing bricks, distinct from K_4, \overline{C_6}, and the Petersen graph, in which every b-invariant edge is a forcing edge. In this paper, we solve this problem for near-bipartite bricks by providing a complete characterization.

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

Summary. The paper solves the Lucchesi-Murty problem for the subclass of near-bipartite bricks (distinct from K_4, ar{C_6}, and the Petersen graph) by providing a complete characterization of those bricks in which every b-invariant edge is a forcing edge. It relies on Lovász's unique decomposition of matching covered graphs into bricks and braces, with b(G) denoting the number of bricks.

Significance. If the characterization holds, the result advances matching theory by identifying structural conditions under which b-invariant edges coincide with forcing edges in near-bipartite bricks. The work builds directly on established prior results (Lovász decomposition uniqueness) without introducing free parameters or ad-hoc axioms.

minor comments (1)
  1. [Abstract] The abstract asserts a complete characterization but provides no outline of the main theorem statement, the precise definition of near-bipartite bricks used, or the form of the characterization (e.g., forbidden subgraphs or degree conditions).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their review and for the positive summary recognizing that the paper provides a complete characterization solving the Lucchesi-Murty problem for near-bipartite bricks. No specific major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper states a characterization theorem for near-bipartite bricks (excluding three small graphs) in which every b-invariant edge is forcing. It rests on the Lovász uniqueness theorem for brick decompositions, which is cited as prior independent work by Lovász rather than a self-citation or internal definition. No equations, fitted parameters, ansatzes, or load-bearing self-citations appear; the derivation chain consists of standard matching-covered graph definitions and an external uniqueness result. The central claim therefore remains independent of its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on Lovasz's decomposition theorem and standard definitions of matching covered graphs, bricks, removable edges, b-invariant edges, and forcing edges; no free parameters, new axioms, or invented entities are introduced in the abstract.

axioms (1)
  • standard math Lovasz's unique decomposition of matching covered graphs into bricks and braces
    Cited in the abstract as the basis for defining b(G).

pith-pipeline@v0.9.1-grok · 5679 in / 1024 out tokens · 29701 ms · 2026-07-02T11:07:07.768364+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

26 extracted references · 4 canonical work pages

  1. [1]

    de Carvalho, C.L

    M.H. de Carvalho, C.L. Lucchesi, U.S.R. Murty, On a conjecture of Lov´ asz concerning bricks. II. Bricks of Finite Characteristic, J. Combin. Theory Ser. B, 85 (2002) 137- 180

    2002

  2. [2]

    de Carvalho, C.L

    M.H. de Carvalho, C.L. Lucchesi, U.S.R. Murty, Graphs with indepen dent perfect matchings, J. Graph Theory, 48 (1) (2005) 19-50

    2005

  3. [3]

    de Carvalho, C.L

    M.H. de Carvalho, C.L. Lucchesi, U.S.R. Murty, On tight cuts in matc hing covered graphs, J. Comb., 9 (1) (2018) 163-184

    2018

  4. [4]

    de Carvalho, C.L

    M.H. de Carvalho, C.L. Lucchesi, U.S.R. Murty, A generalization of L ittle’s theorem on Pfaffian graphs, J. Combin. Theory Ser. B, 102 (2012) 1241-12 66

    2012

  5. [5]

    Edmonds, L

    J. Edmonds, L. Lov´ asz, W.R. Pulleyblank, Brick decompositions a nd the matching rank of graphs, Combinatorica, 2 (3) (1982) 247-274

    1982

  6. [6]

    Fischer, C.H.C

    I. Fischer, C.H.C. Little, A characterization of Pfaffian near-bipa rtite graphs, J. Combin. Theory Ser. B, 82 (2001) 175-222

    2001

  7. [7]

    Goedgebeur, D

    J. Goedgebeur, D. Mattiolo, G. Mazzuoccolo, J. Renders, I.H. W olf, Cubic graphs with edges in exactly one perfect matching, J. Graph Theory, 112 ( 3) (2026) 276-289

    2026

  8. [8]

    Harary, D.J

    F. Harary, D.J. Klein, T.P. ˇZivkovi´ c, Graphical properties of polyhexes: perfect matching vector and forcing, J. Math. Chem., 6 (1991) 295-306

    1991

  9. [9]

    Klein, M

    D.J. Klein, M. Randi´ c, Innate degree of freedom of a graph, J. Comput. Chem., 8 (1987) 516-521

    1987

  10. [10]

    Lov´ asz, M.D

    L. Lov´ asz, M.D. Plummer, Matching Theory, Ann. Discrete Mat h. 29, Elsevier Sci- ence, Amsterdam, 1986

    1986

  11. [11]

    Lucchesi, U.S.R

    C.L. Lucchesi, U.S.R. Murty, Perfect Matchings: A Theory of Ma tching Covered Graphs, Springer, Cham, 2024

    2024

  12. [12]

    Kothari, M.H

    N. Kothari, M.H. de Carvalho, C.L. Lucchesi, C.H.C. Little, On esse ntially 4-edge- connected cubic bricks, Electron. J. Combin., 27 (1) (2020) #P1.22

    2020

  13. [13]

    Kothari, Generating near-bipartite bricks, J

    N. Kothari, Generating near-bipartite bricks, J. Graph Theor y, 90 (2019) 565-590

    2019

  14. [14]

    F. Lu, X. Feng, W. Yan, b-invariant edges in essentially 4-edge-connected near- bipartite cubic bricks, Electron. J. Combin., 27 (1) (2020) #P1.55

    2020

  15. [15]

    Lov´ asz, Matching structure and the matching lattice, J

    L. Lov´ asz, Matching structure and the matching lattice, J. C ombin. Theory Ser. B, 43 (2) (1987) 187-222. 14

    1987

  16. [16]

    Miranda, C.L

    A.A.A. Miranda, C.L. Lucchesi, Recognizing near-bipartite Pfaffia n graphs in poly- nomial time, Discrete Appl. Math., 158 (2010) 1275-1278

    2010

  17. [17]

    C. Sun, Y. Zhang, H. Zhang, The polyomino graphs whose reson ance graphs have a 1-degree vertex, Appl. Math. Comput., 474 (2024) 128704

    2024

  18. [18]

    Szigeti, Perfect matchings versus odd cuts, Combinatorica , 22 (4) (2002) 575-589

    Z. Szigeti, Perfect matchings versus odd cuts, Combinatorica , 22 (4) (2002) 575-589

    2002

  19. [19]

    Y. Wu, D. Ye, C.-Q. Zhang, Uniquely forced perfect matching an d unique 3-edge- coloring, Discrete Appl. Math., 215 (2016) 203-207

    2016

  20. [20]

    Zhang, X

    F. Zhang, X. Guo, R. Chen, Z-transformation graphs of perfect matchings of hexag- onal systems, Discrete Math., 72 (1988) 405-415

    1988

  21. [21]

    Zhang, X

    F. Zhang, X. Li, Hexagonal systems with forcing edges, Discre te Math., 140 (1995) 253-263

    1995

  22. [22]

    Zhang, F

    Y. Zhang, F. Lu, H. Zhang, b-invariant edges in near-bipartite bricks, J. Graph Theory, (2026) 1-11. https://doi.org/10.1002/jgt.70078

    work page doi:10.1002/jgt.70078 2026

  23. [23]

    Zhang, F

    Y. Zhang, F. Lu, X. Wang, J. Yuan, Removable edges in near-bip artite bricks, J. Graph Theory, 108 (2025) 113-135

    2025

  24. [24]

    Zhang, F

    Y. Zhang, F. Lu, H. Zhang, Cubic bricks that every b-invariant edge is forcing, arXiv: 2411.17295, 2024

    work page arXiv 2024

  25. [25]

    Zhang, X

    Y. Zhang, X. Wang, Solid bricks that every b-invariant edge is solitary, arXiv: 2507.21565, 2025

    work page arXiv 2025

  26. [26]

    Zhang, X

    Y. Zhang, X. Wang, Claw-free bricks that every b-invariant edge is solitary, arXiv: 2509.23114v1, 2025. 15

    work page arXiv 2025