Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Cubic bricks that every b-invariant edge is forcing

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

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

Pith's one-line read All cubic bricks in which every b-invariant edge is forcing are exactly ten: K4, the prism C6, the Petersen graph, and G2 through G8.

desk verdict Plausible and probably correct classification, but the |V|≥14 necessity proof has a real gap: Claim 7 does not handle Y→△ expansions at endpoints of a forcing edge. read the letter →

arxiv 2411.17295 v1 pith:V5DKWPCD submitted 2024-11-26 math.CO

Yaxian Zhang , Fuliang Lu , Heping Zhang This is my paper · ORCID
classification math.CO MSC 05C7005C75
keywords matchingcoveredgraphsbricksb-invariantedgesforcingsolitarycubicY-triangleoperationstightcutdecomposition
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

A graph is matching covered if every edge lies in some perfect matching, and a brick is a nonbipartite matching covered graph with no nontrivial tight cuts. In a brick, an edge is b-invariant if deleting it leaves a matching covered graph whose decomposition has exactly one brick, and an edge is forcing, or solitary, if it belongs to exactly one perfect matching. This paper classifies the cubic bricks in which all b-invariant edges are forcing: apart from K4, the prism C6, and the Petersen graph, the only such bricks are the seven graphs G2 through G8 drawn in Figure 7. The classification gives the complete answer for cubic bricks to a characterization problem posed in reference [16], and it supports the corollary that a cubic brick is extremal exactly when every b-invariant edge is solitary.

What carries the argument

The generating move is the Y-to-triangle operation, which replaces a degree-3 vertex by a triangle; Theorem 2.2 of [19] states that every 3-connected cubic graph with a forcing edge is built from K4 by repeated such operations. Two inheritance lemmas do the work. Corollary 2.7 shows that Y-to-triangle operations never increase the number of forcing edges and that every forcing edge of the larger graph comes from a unique forcing edge of the smaller one. Lemma 2.10 and Corollary 2.11 show that the bottom edge of a pyramid, meaning a triangle with one new vertex inserted on each of two sides and an edge joining the two new vertices, is always b-invariant, and if that bottom edge is not forcing in a smaller graph then it remains b-invariant and non-forcing in every larger graph built on the same base. Together these inheritance mechanisms reduce an infinite family to the seven explicitly drawn graphs.

What would settle it

Find a 3-connected cubic brick outside the set {K4, C6, Petersen, G2,...,G8} whose every b-invariant edge is forcing. The proof of Theorem 1.3 says no such graph exists; by the generation theorem of [19], such a graph would also be a counterexample to that theorem, so either discovery would settle the claim.

Watch

Extended reading notes

Core claim

Theorem 1.3 is the central claim: if G is a cubic brick other than K4, the prism C6, and the Petersen graph, then all b-invariant edges of G are forcing exactly when G is one of the seven graphs G2,...,G8 shown in Figure 7. Adding the three excluded graphs, which have no b-invariant edges at all, yields the full list of ten cubic bricks with the property. The sufficiency direction checks each Gi directly: every edge of Gi lies in a perfect matching that contains a forcing edge, and a short claim then forces any removable edge to be forcing. The necessity direction uses the generation theorem from [19] to assume K4 is a base, then shows through Y-to-triangle operations and pyramid subgraphs that every larger cubic brick inherits a b-invariant edge that is not forcing, leaving only the seven listed graphs.

Load-bearing premise

The load-bearing premise is Theorem 2.2 of [19], which says every 3-connected cubic graph with a forcing edge is generated from K4 by repeated Y-to-triangle operations; if that generation theorem has any hidden exception, then a cubic brick outside the ten listed graphs could satisfy the property.

Editorial extensions

If this is right

  • The cubic case of the characterization problem from [16] is closed: a cubic brick outside the ten listed graphs always has a b-invariant edge that is not forcing.
  • The classification is explicit and checkable: the seven graphs G2 through G8 are drawn in the paper, and the sufficiency argument shows directly that every edge of each is covered by a perfect matching containing a forcing edge.
  • The same ten graphs are exactly the cubic bricks in which every thin edge is forcing, where a thin edge is one whose removal leaves a single brick after repeatedly bicontracting degree-2 vertices.
  • As a corollary, a cubic brick is extremal if and only if every b-invariant edge of it is solitary, connecting the forcing-edge property to extremal matching covered graphs.

Reading between the lines

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

  • The inheritance lemmas suggest a general finite-obstruction scheme for b-invariant and forcing questions: any brick base carrying a non-forcing b-invariant edge transmits that edge to all Y-to-triangle descendants, so one can search for minimal bases instead of enumerating all bricks.
  • An independent computational audit is possible: generate all 3-connected cubic graphs through, say, 16 vertices, compute tight-cut decompositions, and test whether any brick outside the ten has all b-invariant edges forcing; the theorem predicts none.
  • The same pyramid and Y-to-triangle machinery could be adapted to other structured families of cubic bricks to see whether a similarly finite list governs the forcing-edge property.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper characterizes the cubic bricks in which every b-invariant edge is a forcing (solitary) edge. The main result, Theorem 1.3, states that apart from K4, C6 and the Petersen graph, the only cubic bricks with this property are the seven graphs G2 through G8 displayed in Fig. 7. The sufficiency direction is proved by direct inspection of these graphs together with a claim that every edge of each Gi lies in a perfect matching containing a forcing edge. The necessity direction starts from the theorem of Wu–Ye–Zhang that every 3-connected cubic graph with a forcing edge is generated from K4 by Y-to-triangle operations, and then analyzes through Claims 2–8 which intermediate graphs can survive as bases. The paper also states a Note 3.1 about thin edges.

Significance. If Theorem 1.3 is correct, it gives a complete solution of the Lucchesi–Murty problem for cubic bricks, and the resulting list of exactly ten graphs is a clean and publishable result. The paper makes good use of the generation theorem of Wu et al. and develops several useful lemmas (Lemmas 2.5, 2.6 and 2.10) describing how forcing and b-invariant edges behave under Y-to-triangle operations. These lemmas are likely to be of independent interest. However, the necessity proof contains at least one load-bearing gap that must be repaired before the classification can be accepted.

major comments (3)
  1. [Section 3, Claim 7] The final inference of Claim 7 is not justified. After establishing that G5 is a base of G and |V(G)| >= 14, the proof must account for every vertex y of G5 such that G = G△5(y), because a single Y-to-triangle operation adds two vertices. The text considers only y = v1 (giving R3) and y in {v2, v3} (giving R4), and it invokes earlier exclusions for R0 and R2. It never treats y = u2 or y = u3, which are endpoints of the forcing edge u2u3 of G5. Lemma 2.6 shows that the edge corresponding to u2u3 in G△5(u2) is not forcing, but it does not show that this edge is not b-invariant, nor that the graph is isomorphic to G7 or G8, nor that it has one of R0, R2, R3, R4 as a base. Thus the sentence 'Since none of R0, R2, R3 and R4 is a base of G, but G5 is a base of G and |V(G)| >= 14, G is an element of {G7, G8}' does not follow from the stated exclusions. The missing cases need to be either ruled out or included in the classification, and the b-invariant status of the corresponding edge must be computed.
  2. [Section 3, Claim 6] The elimination of R2 as a base for |V(G)| >= 14 is asserted rather than proved. The proof says that a Y-to-triangle operation on w, w', x' or u3 'will deduce' that a certain subgraph corresponding to a triangle in G3 contains no forcing edges, but this deduction is not shown. This step is load-bearing because Claim 7 later depends on 'R2 is not a base of G'. In addition, the sentence in Claim 7 that 'By Claim 6, v' and w are vertices of G' is not supported by the text of Claim 6, which concerns R2 and identifies w, w', x' and u3, not v'. Since Corollary 2.11 requires both endpoints of the bottom edge to survive in G*, the survival of v' and w must be proved explicitly rather than inferred from an earlier claim about a different graph.
  3. [Section 3, Sufficiency] The sufficiency of Theorem 1.3 rests on two finite assertions that are not demonstrated: 'it can be checked all bold edges of Gi are forcing edges' and 'we can check that Si = E(Gi)'. These checks are central because they are what force every b-invariant edge of each Gi to be a forcing edge. For seven graphs with up to 14 vertices, this verification is not immediate from Fig. 7. The authors should provide an explicit verification, for example a table listing for each Gi the perfect matchings containing the forcing edges, or an ancillary machine-checkable computation, so that the sufficiency direction is independently verifiable.
minor comments (4)
  1. [Introduction] There are typographical errors such as 'benze noid hydrocarons' and inconsistent use of 'the prism' versus C6; these should be corrected.
  2. [Section 3, Necessity] In the sentence 'If |V(G)| = 8, then G is isomorphic to a bicorn', the justification is implicit: G contains K4 as a base and is obtained from K4 by two Y-to-triangle operations. As written, the sentence reads like a general classification of all 8-vertex cubic bricks, which is not what is proved; please add the explicit reasoning.
  3. [Section 3, Note 3.1] Note 3.1 states a new classification result about thin edges but gives only a sketch ('It can be checked...'). If this note is intended as a theorem, it needs a proof or a precise derivation from the previous arguments; otherwise it should be marked as a conjecture or removed.
  4. [Figures] In Fig. 7, several vertex labels (u', v', w', x', v1, v2, v3) are small and sometimes visually ambiguous; enlarging the labels and adding an explicit list of forcing edges for each Gi would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the classification rests on external generation theorems and independent lemmas, with no fitted parameters or predictions reducing to inputs.

full rationale

The derivation chain is not circular. Theorem 1.3 is proved by combining external structure theorems (Lovasz's brick decomposition, de Carvalho et al.'s theorem that every brick other than K4, C6 and the Petersen graph has a b-invariant edge, and Wu et al.'s theorem that every 3-connected cubic graph with a forcing edge is generated from K4 via Y-to-triangle operations) with the paper's own lemmas that track forcing edges and b-invariant edges under Y-to-triangle operations. No parameter is fitted to data, no quantity is renamed as a prediction, and no target conclusion is assumed inside the proof. The author-overlap citations ([15], [17], [20], [21]) appear only as background in the Introduction and are not load-bearing for the main theorem. The load-bearing generation theorem, Theorem 2.2, is cited from Wu, Ye and Zhang, which is a disjoint author set from the present paper, and it is used as an external hypothesis; even if one doubted its validity, that would be a correctness or completeness concern, not circularity. The sufficiency argument checks the finite list directly, while the necessity argument is a case analysis over bases and rules out the forbidden 'R' graphs by exhibiting explicit b-invariant but non-forcing edges, so the conclusion does not reduce by construction to its inputs. The skeptical concern about omitted cases in Claim 7 is a proof-gap issue, not a circularity issue; it does not make the paper's reasoning equivalent to its own assumptions. Therefore the honest finding is no circularity.

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

The paper introduces no free parameters and no new postulated entities. Its central claim rests on standard matching theory results about tight cuts, bricks, and generation by Y to triangle operations, plus finite checks of the listed graphs.

assumptions (7)
  • standard math Lovasz tight cut decomposition: every matching covered graph decomposes uniquely into bricks and braces.
    Invoked in the Introduction to define b(G), and used in Lemma 2.10 to compute b(G-e)=1 by contracting tight cuts.
  • standard math A graph is a brick if and only if it is 3-connected and bicritical.
    Used in Lemma 2.9 to verify that generalized Y to triangle operations preserve the brick property.
  • standard math Kotzig's theorem: every connected graph with a unique perfect matching has a bridge belonging to that matching.
    Used in Theorem 2.1 and Lemma 2.6 to analyze the structure of G-u-v when e=uv is a forcing edge.
  • domain assumption Theorem 1.1 from de Carvalho et al.: every brick other than K4, C6 and the Petersen graph has at least one b-invariant edge.
    Used in the necessity proof to guarantee that a cubic brick satisfying the property must contain a forcing edge.
  • domain assumption Theorem 2.2 from Wu et al.: every 3-connected cubic graph with a forcing edge is generated from K4 by Y to triangle operations.
    This is the main reduction of the proof; it confines the search to cubic bricks with K4 as a base.
  • domain assumption Theorem 2.3 from de Carvalho et al.: a Y to triangle operation on a cubic brick produces a cubic brick.
    Used repeatedly to propagate brick status from bases to expanded graphs, including in Proposition 2.4 and Lemma 2.10.
  • domain assumption The bicorn is the only brick with exactly one b-invariant edge.
    Used in Claim 6 to rule out bricks with at most one forcing edge, citing reference [5].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Cubic bricks that every b-invariant edge is forcing." pith.science (2026). https://pith.science/paper/V5DKWPCD

@misc{pith2026241117295,
  author       = {Pith},
  title        = {Pith review of: Cubic bricks that every b-invariant edge is forcing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V5DKWPCD}},
  note         = {Machine review of arXiv:2411.17295}
}
read the original abstract

A connected graph G is matching covered if every edge lies in some perfect matching of G. Lovasz proved that every matching covered graph G can be uniquely decomposed into a list of bricks (nonbipartite) and braces (bipartite) up to multiple edges. Denote by b(G) the number of bricks of G. An edge e of G is removable if G-e is also matching covered, and solitary (or forcing) if after the removal of the two end vertices of e, the left graph has a unique perfect matching. Furthermore, a removable edge e of a brick G is b-invariant if b(G-e) = 1. Lucchesi and Murty proposed a problem of characterizing bricks, distinct from K4, the prism and the Petersen graph, in which every b-invariant edge is forcing. We answer the problem for cubic bricks by showing that there are exactly ten cubic bricks, including K4, the prism and the Petersen graph, every b-invariant edge of which is forcing.

Figures

Figures reproduced from arXiv: 2411.17295 by the authors.

Figure 1
Figure 1. Performing a Y → △-operation on x [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Illustration for the proof of Lemma 2.6. [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Illustration for Proposition 2.8. Proposition 2.8. The graph R0 contains no forcing edges. Furthermore, all graphs with R0 as a base have no forcing edges. Proof. As shown in [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Performing a generalized Y → △-operation on x. Proof. Let S ′ be a vertex subset of G′ with size two, and T = x1x2x3x1 be the replacement￾triangle of G′ corresponding to x. If S ′ ∩ {x1, x2, x3} = ∅, then S ′ is a vertex subset of G. Since G is 3-connected bicritical, …
Figure 5
Figure 5. Figure 5: Illustration for Lemma 2.10: T ′ i = ((Ti − u3u4)/X1 → x1)/X2 → x2, where X1 = {u1, u3, u5}, X2 = {u2, u4, u6} and i = 1, 2. 7 [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]
Figure 6
Figure 6. Figure 6: Illustration for b(G∗ − e) = 1. △-operation on a vertex not adjacent to u3 (resp. u4) corresponds to a Y → △-operation on a vertex of degree 3. So ((G∗ − e)/X′ 1 )/X′ 2 can be obtained from ((G − e)/X1)/X2 via Y → △-operations on its vertices of degree 3, or via genera…
Figure 7
Figure 7. Figure 7: All possible bricks in Theorem 1.3: those bold edges are their fo [PITH_FULL_IMAGE:figures/full_fig_p010_7.png]
Figure 8
Figure 8. Figure 8: Performing a Y → △-operation on one end vertex of a forcing edge of G3. Claim 5. w ′x ′ is a b-invariant but not forcing edge of R2. Proof. In R2, since any perfect matching of the 4-cycle vv′ 1 v ′ 3wv can be extended to a perfect matching containing w ′x ′ , w ′x ′ i…
Figure 9
Figure 9. Figure 9: R3 = G △ 5 (v1), R4 = G △ 5 (v2) and R′ 4 = (R4 − u2u3)/X, where X = {u1, u2, u3, v′ , x′}. (G−u2u3)/X contains a brick R′ 4 = (R4−u2u3)/X as a base, (G−u2u3)/X is also a brick by Theorem 2.3. So u2u3 is also a b-invariant but not forcing edge of G, a contradiction. If…
Figure 10
Figure 10. Figure 10: R5 = G △ 4 (v1) and R6 = G △ 6 (v ′ 2 ). Next we show that |V (G)| ≤ 12 in this case. If |V (G)| ≥ 14, then either R5 (see [PITH_FULL_IMAGE:figures/full_fig_p013_10.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Solid bricks that every $b$-invariant edge is solitary

    math.CO 2025-07 conditional novelty 7.0 of 10

    For a solid brick other than K4, every b-invariant edge is solitary if and only if the graph is a wheel W_n, which forces n to be even.

Reference graph

Works this paper leans on

21 extracted references · 20 canonical work pages · cited by 1 Pith paper

  1. [1]

    de Carvalho, C.L

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

    work page 2012

  2. [2]

    de Carvalho, C.L

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

    work page 2005

  3. [3]

    de Carvalho, C.L

    M.H. de Carvalho, C.L. Lucchesi and U.S.R. Murty, How to build a bric k, Discrete Math. 306 (2006) 2383-2410

    work page 2006

  4. [4]

    de Carvalho, C.L

    M.H. de Carvalho, C.L. Lucchesi and U.S.R. Murty, On a conjectur e of Lov´ asz con- cerning bricks. I. The characteristic of a matching covered graph , J. Combin. Theory Ser. B 85 (2002) 94-136

    work page 2002

  5. [5]

    de Carvalho, C.L

    M.H. de Carvalho, C.L. Lucchesi and U.S.R. Murty, On a conjectur e of Lov´ asz con- cerning bricks. II. Bricks of Finite Characteristic, J. Combin. Theo ry Ser. B 85 (2002) 137-180. 14

    work page 2002

  6. [6]

    de Carvalho, C.L

    M.H. de Carvalho, C.L. Lucchesi and U.S.R. Murty, On tight cuts in m atching cov- ered graphs, J. Comb., 9 (1) (2018) 163-184

    work page 2018

  7. [7]

    Edmonds, L

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

    work page 1982

  8. [8]

    Harary, D.J

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

    work page 1991

Show all 21 references
  1. [9]

    Hansen, M

    P. Hansen, M. Zheng, Bonds fixed by fixing bonds, J. Chem. Info rm. Comput. Sci. 34 (1994) 297-304

    1994

  2. [10]

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

    1987

  3. [11]

    Kothari, M.H

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

    2020

  4. [12]

    Kotzig, On the theory of finite graphs with a linear factor II, Mat

    A. Kotzig, On the theory of finite graphs with a linear factor II, Mat. Fyz. ˇCasopis Slovensk. Akad. Vied 9 (1959) 136-159

    1959

  5. [13]

    Lov´ asz

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

    1987

  6. [14]

    Lov´ asz and M.D

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

    1986

  7. [15]

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

    2020

  8. [16]

    Lucchesi and U.S.R

    C.L. Lucchesi and U.S.R. Murty, Perfect Matchings. Springer, 2024

    2024

  9. [17]

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

    2024

  10. [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

  11. [19]

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

    2016

  12. [20]

    Zhang, X

    F. Zhang, X. Guo and R. Chen, Z-transformation graphs of pe rfect matchings of hexagonal systems, Discrete Math. 72 (1988) 405-415

    1988

  13. [21]

    Zhang and X

    F. Zhang and X. Li, Hexagonal systems with forcing edges, Disc rete Math. 140 (1995) 253-263. 15

    1995

Pith tools

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