Wheel-like bricks and minimal matching covered graphs

Fuliang Lu; Jinxin Xue; Xiaoling He

REVIEW 3 major objections 3 minor 15 references

Wheel-like bricks and minimal matching covered graphs

T0 review · 3 major / 3 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A wheel-like brick is always obtainable by splicing odd wheels and K4-type graphs, and minimal matching covered graphs have minimum degree 2 or 3.

desk verdict Genuinely new theorems, but the main structural proof has an unsupported nonadjacency step; worth refereeing after repairs. read the letter →

arxiv 2412.16465 v2 pith:D4VBOAA2 submitted 2024-12-21 math.CO

Xiaoling He , Fuliang Lu , Jinxin Xue This is my paper · ORCID

classification math.CO MSC 05C7005C4005C75

keywords wheel-likebricksmatchingcoveredgraphsremovableedgesdoubletonstightcutssplicingminimumdegree

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper answers a structural question in matching theory: what must a brick look like when every removable class—an edge that can be deleted, or a pair of edges that can be deleted together, while every edge still lies in a perfect matching—has an edge incident with one special vertex? The proposed answer is Theorem 1.3: every such wheel-like brick belongs to $\mathcal{G}$, the recursively defined family of graphs obtained by splicing odd wheels (with possible multiple edges) and $K_4$-type graphs subject to conditions on hubs and nonremovable edges. The same machinery yields Theorem 1.4: every minimal matching covered graph with at least four vertices has minimum degree $2$ or $3$, so no minimal matching covered graph can be, for example, 4-regular. The significance is twofold: it resolves the necessary direction of the Lucchesi–Murty characterization problem, and it extends the known bipartite minimum-degree result to all matching covered graphs.

What carries the argument

The engine is the splicing operation $G(u) \odot H(v)$: it deletes vertices $u$ and $v$ and joins their incident edges according to a bijection, producing a new graph whose degree sequence is unchanged away from the splice. The paper builds the family $\mathcal{G}$ recursively from odd wheels, where an odd wheel $W_k$ is a cycle of odd length whose vertices are all joined to a hub. The proof of Theorem 1.3 runs on robust cuts: separating cuts that are not tight (do not meet every perfect matching in exactly one edge) and whose two contractions are near-bricks (graphs containing a single brick). Corollary 2.9 supplies a robust cut whose two double contractions yield a bipartite matching covered graph with the two contracted vertices in different color classes, and Lemma 2.10 says every edge incident with one of those contracted vertices is removable; these facts let the induction peel a wheel-like brick into smaller wheel-like bricks.

What would settle it

An explicit search would settle the matter: enumerate all minimal matching covered graphs on small vertex sets (allowing multiple edges) and look for one with minimum degree at least $4$; Theorem 1.4 predicts that none exists. For the structure theorem, take the smallest wheel-like brick not obviously in $\mathcal{G}$, apply the robust-cut decomposition of Corollary 2.9, and check whether the two pieces are again wheel-like and satisfy the splicing conditions; any wheel-like brick that cannot be rebuilt from smaller wheel-like bricks this way would falsify Theorem 1.3.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that wheel-like bricks are exactly the graphs obtainable by repeatedly splicing odd wheels: Theorem 1.3 states $G \in \mathcal{G}$ for every wheel-like brick $G$, where $\mathcal{G}$ is built level by level from wheel-like odd wheels (including $K_4$ with multiple edges) by splicing operations $G_j(u_j) \odot H_j(v_j)$ that obey two kinds of rules: the splicing vertex of one piece must be the hub (or the maximum-degree set) in a prescribed way, and any edge of the $K_4$-piece that is nonremovable must correspond, after splicing, to an edge that does not touch the hub of the other piece. The proof is an induction on the number of vertices. Every nonsolid brick is split by a robust cut; the double contraction is bipartite and matching covered, and the imported Lemma 2.10 guarantees that all edges incident with the contracted vertex are removable there. That forces both pieces of the split to be wheel-like, so the induction applies. Theorem 1.4 then uses barrier reduction to show that a minimal matching covered graph with minimum degree at least $4$ would force a bicritical graph with a removable edge and then a degree-$3$ vertex, a contradiction.

Load-bearing premise

The proof of the structure theorem assumes that every nonsolid brick can be split along a robust cut whose two contracted sides each contain only one brick and whose double contraction is bipartite with the two contracted vertices on opposite parts; if a single nonsolid brick failed to split this way, the induction that produces the characterization would break.

Editorial extensions

If this is right

Every wheel-like brick with more than four vertices has exactly one maximum-degree hub, and every edge incident with that hub is removable (Lemma 3.9).
The characterization problem for wheel-like bricks is reduced to identifying which members of $\mathcal{G}$ are wheel-like, since the paper shows the converse inclusion is false.
No minimal matching covered graph on at least four vertices can have minimum degree $4$ or more; the bound $\delta(G) \in \{2,3\}$ is sharp, attained by even cycles, $K_4$, and the triangular prism.
The earlier result that minimal matching covered bipartite graphs have minimum degree $2$ now extends to all matching covered graphs, without a bipartiteness assumption.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial inference: the recursive description of $\mathcal{G}$ gives a natural recognition procedure for wheel-like bricks: repeatedly split along robust cuts, verify each piece is an odd wheel or $K_4$-type graph, and check the splice conditions; this would turn the existence proof into an algorithm.
Editorial inference: because the paper notes that not every graph in $\mathcal{G}$ is wheel-like, the remaining open direction of the characterization is to describe exactly which graphs in $\mathcal{G}$ satisfy the extra wheel-like condition; Lemma 3.8 already does this for pure two-wheel splices.
Editorial inference: the minimum-degree theorem suggests a concrete strengthening to look for: in every minimal matching covered graph, the vertices of degree $2$ or $3$ should be locatable through the barrier contraction process used in the proof, possibly giving a canonical decomposition into low-degree cores and spliced even cycles.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's my take on arXiv:2412.16465. The two main results are genuinely new and worth having: a one-way structural decomposition for wheel-like bricks (Theorem 1.3) and a sharp minimum-degree theorem for minimal matching covered graphs (Theorem 1.4, delta between 2 and 3). The wheel-like result extends the planar case from the same group's preprint, and the min-degree theorem is a clean generalization of Lovasz-Plummer. The high-level strategy is sensible: induction via robust cuts for Theorem 1.3, and a barrier-contraction argument for Theorem 1.4.

But the written proof has several gaps, and they are not cosmetic. The most serious is in Claim 1 of Theorem 1.3. The proof asserts that two lifted removable edges e1 and e2, one from each of the two contracted bricks, are nonadjacent. That does not follow: the two edges can meet at a vertex in V(G) minus (X' union X''). Without nonadjacency, the contradiction with wheel-likeness collapses, and since this is the step that forces G' and G'' to be wheel-like, the induction is unsupported. The same unjustified nonadjacency reappears when Lemma 2.18 is invoked. Separately, the lifting step itself ('both are removable in G by Lemmas 2.11 and 2.12') needs a more careful argument, because a single removable edge in one contraction need not lift to G unless it is removable in both contractions, which is not the case here.

Theorem 1.4 has a more mechanical problem: in Claim A, the proof defines H2 = H1/(Y -> y), says every edge incident with y is removable in H2, then says every such edge is not removable in H2. That is an internal contradiction; probably a typo (the two contractions got mixed up), but it needs fixing. There is also an omitted subcase: when the final bicritical graph G' has no removable edge, the proof jumps to the removable case; Prop 3.12 gives the needed degree-3 vertex, so this is repairable, but it is not in the text.

Finally, several key lemmas (2.10, 3.7, 3.8) come from an unpublished preprint by two of the same authors. That does not make them wrong, but it means the referees cannot verify the foundation without a second document.

My overall take: the results are likely true and the paper deserves a serious referee. But it is not ready as written; the nonadjacency gap is load-bearing. If the authors can supply a proof of that step (or a different route to the induction), this becomes a solid contribution.

Referee Report

3 major / 3 minor

Summary. The paper studies matching covered graphs, focusing on wheel-like bricks and minimal matching covered graphs. It defines a recursively constructed family G of graphs obtained by splicing odd wheels and K4-type graphs with prescribed conditions on hubs and non-removable edges, and claims in Theorem 1.3 that every wheel-like brick belongs to G. It then uses properties of wheel-like bricks to prove Theorem 1.4, that every minimal matching covered graph on at least four vertices has minimum degree 2 or 3. The proof is inductive and relies on the tight-cut decomposition theory of bricks, robust cuts, and splicing operations, together with several recent lemmas from the authors' own preprint [13] and from Carvalho-Lucchesi-Murty.

Significance. If correct, Theorem 1.3 gives a structural necessary condition for all wheel-like bricks, addressing a problem of Lucchesi and Murty, and Theorem 1.4 provides a sharp minimum-degree bound for all minimal matching covered graphs, extending the classical Lovász-Plummer result for bipartite graphs. The paper contributes a concrete recursive family G and shows that the structural result can be applied to a separate extremal problem. The proof strategy is plausible and the use of robust cuts and splicing is appropriate. However, the correctness of the central inductive proof is not yet established, because several non-adjacency assertions and some 'it can be checked' steps are not justified; these gaps are load-bearing for the main theorems.

major comments (3)

[Section 3, Proof of Theorem 1.3, Claim 1] The sentence "Note that e1 and e2 are nonadjacent" is not justified. The preceding construction only ensures that e1 is not incident with x' in G' and e2 is not incident with x'' in G''; the edges may share a vertex in V(G)\ (X' ∪ X'') or one may be incident with an endpoint of the other. The bipartiteness of H and the fact that x' and x'' lie in different color classes do not rule out adjacency. Since the contradiction with the wheel-like property requires two removable edges that are not both incident with the hub, this step is load-bearing. The same unjustified non-adjacency assertion recurs in Claim 2 when e1 and e3, or e and e0, are declared nonadjacent. Please supply a proof or a case analysis.
[Section 3, Lemma 3.13] In the subcase where H2 contains a removable edge and ∂H1(u) contains both removable and nonremovable edges, the proof states that V(H1)\ {u} contains a vertex s2 of degree 3 "by the minimality of V(G)". The minimality of G only rules out a smaller bicritical graph with all vertices except its hub of degree at least 4 and with some nonremovable edge incident with the hub. If the only degree-3 vertex in V(H1)\ {u} is the contracted vertex x, then H1 is not a counterexample and no vertex of G of degree 3 is obtained. The argument must rule out this possibility; otherwise Lemma 3.13, which is essential for Theorem 1.4, is not established.
[Section 4, Proof of Theorem 1.4, Claim A] The assertion "it can be checked that every edge of ∂H1(k) is not removable in H1" is nontrivial. Edges of ∂H1(k) lie in both ∂(V(K))-contractions, so Lemma 2.11 alone does not imply their non-removability in H1 from the minimality of G. Since this is the basis for concluding that H1 is minimal and for the subsequent contradiction with the minimal choice of G, a detailed verification is needed.

minor comments (3)

[Section 2, Lemma 2.10 and Section 3, Lemma 3.8] The proofs of Theorems 1.3 and 1.4 rely on Lemma 2.10 and Lemma 3.8 from the authors' unpublished preprint [13]. If the paper is intended to be self-contained, these dependencies should be stated more prominently, and the relevant statements should ideally be proved or clearly labeled as external.
[Section 2, Corollary 2.9] The proof of Corollary 2.9 contains two "it can be checked" steps in the maximum-barrier argument; please spell out these checks so that the proof can be independently verified.
[Section 1 and Section 3] There are minor textual issues: on page 5, "The the degree of u" should read "The degree of u"; the paragraph defining G states that "The vertex of a graph in G with the maximum degree is called a hub of it," which should be made conditional on the uniqueness of the maximum-degree vertex, as established in Lemma 3.9.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 1.3 is a one-way structural classification and Theorem 1.4 is an independent minimum-degree bound; same-author citations are load-bearing but do not encode the conclusions.

full rationale

The derivation chain does not reduce to its own inputs. Theorem 1.3 starts from the external solid-brick result (Proposition 3.1), and for nonsolid bricks uses Corollary 2.9, which is derived in the paper from Carvalho-Lucchesi-Murty's Theorem 2.8, to split a wheel-like brick into contractions G' and G''. The induction then propagates wheel-likeness via Lemmas 2.10 and 3.7 from the authors' preprint [13] and finally checks membership in the recursively defined family G. The hypothesis of the theorem is 'every removable class has an edge incident with a hub', while membership in G is a splicing/degree condition; the conclusion is not a restatement of the hypothesis. Theorem 1.4 is proved from internally proved lemmas (2.16, 2.17, 3.13) and external results (Lovasz-Plummer, Zhang-Wang-Yuan); it does not fit or reuse the target minimum-degree bound. The citations to [13] are technical lemmas about robust cuts and splicings whose stated assumptions do not include Theorem 1.3 or Theorem 1.4, so under the review rules they are independent support rather than circularity. The only internal weakness is the asserted nonadjacency of e1 and e2 in Claim 1 of the proof of Theorem 1.3, which is not justified in the text; that is a proof gap affecting correctness, not a circular reduction. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported from the authors to exclude alternatives, and no known pattern is merely renamed. The paper is therefore not circular, though its dependence on the unpublished co-authored preprint [13] is a verification risk.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper is a structural graph theory proof with no numerical free parameters. It imports a dozen results from prior literature, several from the co-authors' own arXiv preprint [13] (arXiv:2410.20692), which is not yet peer-reviewed. The most load-bearing external inputs are Theorem 2.8 ([5]) and Lemma 2.10 ([13]).

assumptions (6)

standard math Tutte's perfect matching theorem (Theorem 2.1)
Used throughout Section 2 to prove Corollary 2.2 and properties of barriers.
domain assumption Lovasz tight cut decomposition and uniqueness of bricks and braces
Defines bricks, near-bricks, and the decomposition used throughout the paper; cited to [12].
domain assumption Theorem 2.8: every nonsolid brick has a robust cut with one contraction solid
Foundation for Corollary 2.9, which drives the induction in Theorem 1.3; cited to [5].
domain assumption Lemma 2.10: for two robust cuts with bipartite H, every edge incident with x is removable in H
Used to lift removable edges from H to G in Claims 1 and 2 of Theorem 1.3; sourced to [13].
domain assumption Lemma 3.8: conditions for splicing of two odd wheels to be wheel-like
Used in the discussion after Theorem 1.3 and to determine wheel-like splicings; from the co-authored preprint [13].
domain assumption Propositions 3.1, 3.5, and 3.12 on solid bricks, six-vertex bricks, and bicritical graphs without removable edges
Used in base cases of Theorem 1.3 and in the proof of Theorem 1.4; cited to [8], [4], and [15].

how reviews work

0 comments

Cite this review

Pith. "Pith review of Wheel-like bricks and minimal matching covered graphs." pith.science (2026). https://pith.science/paper/D4VBOAA2

@misc{pith2026241216465,
  author       = {Pith},
  title        = {Pith review of: Wheel-like bricks and minimal matching covered graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/D4VBOAA2}},
  note         = {Machine review of arXiv:2412.16465}
}

read the original abstract

A connected graph G with at least two vertices is matching covered if each of its edges lies in a perfect matching. We say that an edge e in a matching covered graph G is removable if G-e is matching covered. A pair {e; f} of edges of a matching covered graph G is a removable doubleton if G-e-f is matching covered, but neither G-e nor G-f is. Removable edges and removable doubletons are called removable classes, introduced by Lovasz and Plummer in connection with ear decompositions of matching covered graphs. A 3-connected graph is a brick if the removal of any two distinct vertices, the left graph has a perfect matching. A brick G is wheel-like if G has a vertex h, such that every removable class of G has an edge incident with h. Lucchesi and Murty proposed a problem of characterizing wheel-like bricks. We show that every wheel-like brick may be obtained by splicing graphs whose underlying simple graphs are odd wheels in a certain manner. A matching covered graph is minimal if the removal of any edge, the left graph is not matching covered. Lovasz and Plummer proved that the minimum degree of a minimal matching covered bipartite graph different from K2 is 2 by ear decompositions in 1977. By the properties of wheel-like bricks, we prove that the minimum degree of a minimal matching covered graph other than K2 is 2 or 3.

Figures

Figures reproduced from arXiv: 2412.16465 by the authors.

**Figure 1.** R8. Lemma 3.4 ([13]). 1) Let G be a simple near-bipartite brick. Then G is wheel-like if and only if G is isomorphic to K4. 2) Let G be a simple planar brick with six vertices. Then G is a wheel-like brick if and only if G is isomorphic to W5. Proposition 3.5 ([4]). Let G be a simple brick on six vertices. Then G is either nonsolid or W5. Lemma 3.6. Let G be a wheel-like brick on 6 vertices and let h be the hub of G… view at source ↗

**Figure 2.** Nonplanar nonsolid bricks on six vertices, where the bold ed [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗

**Figure 3.** A brick in G3 which is not wheel-like (the bold edges are removable). Proposition 3.10. Let G be a brick such that every removable edge of it is incident with a vertex h. Then every edge of ∂(h) is removable or there exists a vertex u ∈ V (G) \ {h} such that dG(u) = 3. Proof. If G has a removable doubleton, then the underlying simple graph H of G is isomorphic to K4, the triangular prism or R8 by Theorem 3.3. If G =… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[13]

Planar wheel-like bricks

F. Lu and J. Xue, Planar wheel-like bricks, http://arxiv.org/abs /2410.20692

work page Pith review arXiv
[1]

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

work page 2008
[2]

M. H. Carvalho, C. L. Lucchesi, and U. S. R. Murty, Ear decompo sitions of matching covered graphs, Combinatorica, 19: 151-174, 1999

work page 1999
[3]

M. H. Carvalho, C. L. Lucchesi and U. S. R. Murty, On a conject ure of Lov´ asz concerning bricks. II. Bricks of ﬁnite characteristic, J. Combin. T heory Ser. B, 85: 137-180, 2002

work page 2002
[4]

M. H. Carvalho, C. L. Lucchesi and U. S. R. Murty, How to build a b rick, Discrete Mathematics, 306: 2383-2410, 2006

work page 2006
[5]

M. H. Carvalho, C. L. Lucchesi, and U. S. R. Murty, Graphs with in dependent perfect matchings, J. Graph Theory 48 (2005), 19-50

work page 2005
[6]

M. H. Carvalho, C. L. Lucchesi and U. S. R. Murty, Thin edges in b races, Electron. J. Combin., 22(4), #P4.14, 2015

work page 2015
[7]

Edmonds, L

J. Edmonds, L. Lov´ asz and W. R. Pulleyblank, Brick decompositio ns and the match- ing rank of graphs, Combinatorica, 2(3): 247-274, 1982

work page 1982

Show all 15 references

[8]

C. L. Lucchesi and U. S. R. Murty, Perfect Matchings, Springe r, 2024. 20

2024
[9]

Lov´ asz and M

L. Lov´ asz and M. D. Plummer, On minimal elementary bipartite gra phs, J. Combin. Theory Ser. B, 23: 127-138, 1977

1977
[10]

Lov´ asz and M

L. Lov´ asz and M. D. Plummer, Matching Theory, Annals of Discr ete Mathematics, vol. 29, Elsevier Science, 1986

1986
[11]

Lov´ asz

L. Lov´ asz. Ear decompositions of matching covered graphs, Combinatorica, 2: 105- 117, 1983

1983
[12]

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: 187-222, 1987

1987
[14]

W. T. Tutte, The factorization of linear graphs, J. Lond. Math . Soc. 22: 107-111, 1947

1947
[15]

Zhang, X

Y. Zhang, X. Wang and J. Yuan, Bicritical graphs without remov able edges, Discrete Applied Mathematics, 320: 1-10, 2022. 21

2022

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [13]

Planar wheel-like bricks

F. Lu and J. Xue, Planar wheel-like bricks, http://arxiv.org/abs /2410.20692

work page Pith review arXiv

[2] [1]

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

work page 2008

[3] [2]

M. H. Carvalho, C. L. Lucchesi, and U. S. R. Murty, Ear decompo sitions of matching covered graphs, Combinatorica, 19: 151-174, 1999

work page 1999

[4] [3]

M. H. Carvalho, C. L. Lucchesi and U. S. R. Murty, On a conject ure of Lov´ asz concerning bricks. II. Bricks of ﬁnite characteristic, J. Combin. T heory Ser. B, 85: 137-180, 2002

work page 2002

[5] [4]

M. H. Carvalho, C. L. Lucchesi and U. S. R. Murty, How to build a b rick, Discrete Mathematics, 306: 2383-2410, 2006

work page 2006

[6] [5]

M. H. Carvalho, C. L. Lucchesi, and U. S. R. Murty, Graphs with in dependent perfect matchings, J. Graph Theory 48 (2005), 19-50

work page 2005

[7] [6]

M. H. Carvalho, C. L. Lucchesi and U. S. R. Murty, Thin edges in b races, Electron. J. Combin., 22(4), #P4.14, 2015

work page 2015

[8] [7]

Edmonds, L

J. Edmonds, L. Lov´ asz and W. R. Pulleyblank, Brick decompositio ns and the match- ing rank of graphs, Combinatorica, 2(3): 247-274, 1982

work page 1982