{"id":"82b43744-9f1d-4fdd-8e61-b4b4994fb3fa","arxiv_id":"2411.17295","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A cubic brick has every b-invariant edge forcing exactly when it is one of seven listed graphs, plus K4, the prism, and the Petersen graph.","lead":"This paper classifies all cubic graphs, called bricks, in which every edge that preserves the brick count after deletion is also the unique edge of a perfect matching. The authors show exactly seven such graphs exist beyond three known exceptions, settling the cubic case of an open problem in matching theory.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claim 7's case analysis omits Y→△-expansions of G5 at endpoints of forcing edges, so the classification may be incomplete for 14-vertex graphs.","rationale":"The reader's weakest_assumption pointed to the external generation theorem (Theorem 2.2 from [19]). That theorem is load-bearing but is a published result, so the more pressing concern is an internal gap in the necessity proof. Claim 7 attempts to rule out all possible expansions from G5 by considering only R3 and R4, then jumps to G7/G8. Since a Y→△-operation can be applied to any vertex, and operations on endpoints of forcing edges are known to destroy forcing properties (Lemma 2.6), the proof must either analyze those cases or show they lead to a contradiction. The central classification could be incomplete if a 14-vertex graph generated from G5 at u2 or u3 satisfies the property. The proposed concrete test settles the mathematical question. If the enumeration shows no counterexample, the theorem likely holds, but the written proof still needs to be extended; hence the reader's CONDITIONAL verdict remains appropriate.","tokens_in":12805,"tokens_out":15036,"duration_ms":126152,"concrete_test":"Enumerate all non-isomorphic 14-vertex cubic bricks obtained from G5 by exactly one Y→△-operation on each vertex of G5 (up to automorphism, at most |V(G5)| candidates). For each candidate H, compute the set of b-invariant edges and the set of forcing edges using the paper's definitions. If any H has a b-invariant edge that is not forcing, Theorem 1.3 is false. If none does, verify that each such H either is isomorphic to G7/G8 or contains R3 or R4 as a base; this would confirm that the gap is only in exposition, not in the result.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the necessity proof for |V(G)|≥14 (Claim 7), the authors conclude that since none of R0, R2, R3, R4 is a base of G, but G5 is a base, then G∈{G7,G8}. This inference is not justified. From G5 as base, a single Y→△-operation can be applied to any vertex of G5. The proof only rules out operations on v1 (giving R3) and on v2/v3 (giving R4), and it invokes Claim 6 to assert that v′ and w are vertices of G. But Claim 6 only rules out R2 as a base; it does not establish that v′ and w survive in G. More importantly, the proof never considers Y→△-operations on u2 or u3, endpoints of the forcing edge u2u3 in G5. By Lemma 2.6, the corresponding edge in the expanded graph is not forcing. The paper does not show that this edge is b-invariant, nor that the resulting graph is isomorphic to G7 or G8, nor that it contains a forbidden base. Thus the claimed dichotomy 'G∈{G7,G8}' does not follow from the stated exclusions, leaving a real gap in the necessity argument.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":91,"tokens_out":14083,"duration_ms":413892,"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":[{"comment":"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.","section":"Section 3, Claim 7"},{"comment":"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.","section":"Section 3, Claim 6"},{"comment":"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.","section":"Section 3, Sufficiency"}],"minor_comments":[{"comment":"There are typographical errors such as 'benze noid hydrocarons' and inconsistent use of 'the prism' versus C6; these should be corrected.","section":"Introduction"},{"comment":"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.","section":"Section 3, Necessity"},{"comment":"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.","section":"Section 3, Note 3.1"},{"comment":"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.","section":"Figures"}],"recommendation":"major_revision","confidential_remarks":"The gap in Claim 7 is central to the necessity direction. If the missing Y-to-triangle expansions at u2 or u3 produce additional graphs with all b-invariant edges forcing, then Theorem 1.3 would need to be revised; if they do not, the authors must show why. I believe the overall approach is sound and the result is likely repairable, so I recommend major revision rather than rejection. The sufficiency checks also need to be made explicit before the paper can be verified without trusting the authors' 'it can be checked' assertions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read. The paper does something real: it gives the first classification of cubic bricks in which every b-invariant edge is forcing, a natural cubic case of the Lucchesi–Murty problem. The sufficiency direction is solid, and the lemmas about how forcing and non-forcing behavior survive Y→△ operations are clean and useful. The reliance on Wu et al.'s generation theorem is legitimate; the proof is not circular and does not fit parameters. The corollary on extremal cubic bricks is a nice byproduct.\n\nThe soft spots are concentrated in the necessity proof. First, the assertion that every cubic brick on eight vertices is the bicorn is used without proof or citation. That is an easy fix but should be supplied. Second, several finite checks are waved at—\"it can be checked\" for the forcing edges and for S_i = E(G_i) in Fig. 7—and those should be documented or made available as machine-checkable data. Neither of these by itself sinks the paper.\n\nThe real problem is Claim 7. The stress-test note is on target. After establishing G5 as a base for |V|≥14, the authors rule out Y→△-expansions at v1 and at v2/v3, then assert that since none of R0, R2, R3, R4 is a base, G must be G7 or G8. That inference does not follow. G5 has twelve vertices, so there are many possible first expansions. In particular, expansions at u2 or u3—endpoints of the forcing edge u2u3—are never treated. Lemma 2.6 implies the corresponding edge is not forcing in the expanded graph, but the proof does not show that edge is b-invariant or that the expansion contains a forbidden base. Without that, the 14-vertex case is not closed. This is a load-bearing gap, not a cosmetic one.\n\nMy overall assessment: the classification is plausible and probably correct, and the sufficiency direction plus the lemmas are a real contribution. But the necessity proof for |V|≥14 is incomplete as written. The paper deserves peer review—the problem is worth settling and the gap looks fillable—but the referee should insist on a complete case analysis for all Y→△ expansions from G5, with the finite checks either proved or supplied as code.","headline":"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.","tokens_in":13523,"tokens_out":5590,"would_cite":false,"duration_ms":52202,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C70","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["matching covered graphs","bricks","b-invariant edges","forcing edges","solitary edges","cubic bricks","Y-triangle operations","tight cut decomposition"],"falsifier":"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.","tokens_in":12583,"feed_emoji":"📐","tokens_out":12371,"duration_ms":102618,"temperature":0.7,"pith_summary":"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.","feed_headline":"Exactly ten cubic bricks make every b-invariant edge forcing","feed_subtitle":"A matching-theory classification problem, open for cubic bricks, now has a ten-graph answer.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"It supplies the generation theorem that every 3-connected cubic graph with a forcing edge is generated from K4 by Y-to-triangle operations, which is the starting point of the necessity proof.","marker":"[19]"},{"why":"It proves that every brick other than K4, C6 and the Petersen graph has at least one b-invariant edge, so any other cubic brick with the forcing property must have a forcing edge.","marker":"[4]"},{"why":"It shows that cubic-brickness is preserved under Y-to-triangle operations and characterizes extremal cubic matching covered graphs, facts used both in the proof and in Corollary 1.4.","marker":"[2]"},{"why":"It gives the criterion that a connected graph with a unique perfect matching has a bridge, a test applied repeatedly to show that certain edges are not forcing.","marker":"[12]"},{"why":"It identifies the bicorn as the only brick with exactly one b-invariant edge, which is used in Claim 6 to rule out bases with too few forcing edges.","marker":"[5]"},{"why":"It poses the problem of characterizing bricks whose b-invariant edges are all solitary, the problem that this paper answers for cubic bricks.","marker":"[16]"}],"fun_headline_variants":["Ten cubic bricks settle b-invariant edge forcing","Only ten cubic bricks have all b-invariant edges forcing","Cubic bricks: ten graphs with every b-invariant edge forcing","Open cubic brick problem solved: exactly ten cases"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Ten cubic bricks settle b-invariant edge forcing","Only ten cubic bricks have all b-invariant edges forcing","Cubic bricks: ten graphs with every b-invariant edge forcing","Open cubic brick problem solved: exactly ten cases"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001136,"raw_usage":{"total_tokens":4692,"prompt_tokens":894,"completion_tokens":3798,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":510,"completion_tokens_details":{"reasoning_tokens":3733}},"tokens_in":510,"tokens_out":3798,"duration_ms":21444,"temperature":1.0,"reasoning_tokens":3733,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:19:58.585889+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies the generation theorem that every 3-connected cubic graph with a forcing edge is generated from K4 by Y-to-triangle operations, which is the starting point of the necessity proof."},{"cited_title":"de Carvalho, C.L","cited_arxiv_id":null,"evidence_quote":"It proves that every brick other than K4, C6 and the Petersen graph has at least one b-invariant edge, so any other cubic brick with the forcing property must have a forcing edge."},{"cited_title":"de Carvalho, C.L","cited_arxiv_id":null,"evidence_quote":"It shows that cubic-brickness is preserved under Y-to-triangle operations and characterizes extremal cubic matching covered graphs, facts used both in the proof and in Corollary 1.4."},{"cited_title":"Kotzig, On the theory of finite graphs with a linear factor II, Mat","cited_arxiv_id":null,"evidence_quote":"It gives the criterion that a connected graph with a unique perfect matching has a bridge, a test applied repeatedly to show that certain edges are not forcing."},{"cited_title":"de Carvalho, C.L","cited_arxiv_id":null,"evidence_quote":"It identifies the bicorn as the only brick with exactly one b-invariant edge, which is used in Claim 6 to rule out bases with too few forcing edges."},{"cited_title":"Lucchesi and U.S.R","cited_arxiv_id":null,"evidence_quote":"It poses the problem of characterizing bricks whose b-invariant edges are all solitary, the problem that this paper answers for cubic bricks."}],"review_version":1}