Minimal bricks

Robin Thomas; Serguei Norine

arxiv: 1907.00305 · v1 · pith:6Z6LRZTYnew · submitted 2019-06-30 · 🧮 math.CO · cs.DM

Minimal bricks

Serguei Norine , Robin Thomas This is my paper

Pith reviewed 2026-05-25 13:08 UTC · model grok-4.3

classification 🧮 math.CO cs.DM

keywords minimal bricksgeneration theorem3-connected graphsperfect matchingsedge boundsdegree sequencesbrick graphs

0 comments

The pith

A generation theorem constructs all minimal bricks and implies they have at most 5n-7 edges with at least three degree-three vertices.

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

The paper proves a generation theorem that recursively builds every minimal brick from smaller ones. This construction directly yields two bounds: on 2n vertices with n greater than 4, no minimal brick has more than 5n-7 edges, and every minimal brick must contain at least three vertices of degree three. A reader would care because bricks capture the essential 3-connected graphs that stay matchable after any two vertices are removed, and the minimal ones are the sparsest such examples. The theorem turns the abstract definition into an explicit recursive list.

Core claim

We prove a generation theorem for minimal bricks and two corollaries: for n>4, every minimal brick on 2n vertices has at most 5n-7 edges, and every minimal brick has at least three vertices of degree three.

What carries the argument

The generation theorem, a recursive construction that produces every minimal brick from base graphs by a fixed set of operations.

If this is right

For n>4, every minimal brick on 2n vertices has at most 5n-7 edges.
Every minimal brick has at least three vertices of degree three.
The generation theorem provides a complete recursive description of all minimal bricks.

Where Pith is reading between the lines

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

The recursive construction supplies a practical way to enumerate minimal bricks of moderate size.
The degree and edge bounds may be used to test candidate graphs for the minimal-brick property without checking every edge deletion.

Load-bearing premise

The generation theorem correctly enumerates every minimal brick without omissions or extraneous cases, allowing the edge-count and degree corollaries to follow directly from the recursive construction.

What would settle it

A minimal brick on 2n vertices (n>4) that has more than 5n-7 edges, or any minimal brick that has fewer than three vertices of degree three.

read the original abstract

A brick is a 3-connected graph such that the graph obtained from it by deleting any two distinct vertices has a perfect matching. A brick is minimal if for every edge e the deletion of e results in a graph that is not a brick. We prove a generation theorem for minimal bricks and two corollaries: (1) for n>4, every minimal brick on 2n vertices has at most 5n-7 edges, and (2) every minimal brick has at least three vertices of degree three.

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.

Desk Editor's Note private letter to a colleague

Norine and Thomas prove a generation theorem for minimal bricks that directly gives the 5n-7 edge bound and the three degree-3 vertices claim.

read the letter

The main point is that this paper supplies an explicit generation theorem for minimal bricks and uses it to prove two clean corollaries. The theorem describes how every minimal brick arises from smaller ones via a set of operations, and the corollaries follow at once: for n>4 every minimal brick on 2n vertices has at most 5n-7 edges, and every minimal brick has at least three degree-3 vertices. That is the actual new content. The construction is presented as new and the bounds are concrete numbers that were not previously on record in this form. The work sits squarely inside matching theory and the study of 3-connected graphs with perfect matchings after vertex deletions, so it is a natural next step for people already tracking bricks. The authors know the area, and the result gives usable structural information rather than just existence statements. The load-bearing step is the completeness of the generation: the edge and degree claims rest on every minimal brick being produced by the allowed operations. If the case analysis misses even one family, the bounds could be violated. The abstract gives no small-case enumeration or other independent check, so the proof of exhaustiveness is where any referee will focus. This is a paper for specialists in structural matching theory. It will not move the larger field but supplies precise facts inside the subfield. It deserves a serious referee because the claims are specific, the derivation is direct once the generation is accepted, and the topic is established enough that expert eyes should check the casework.

Referee Report

1 major / 0 minor

Summary. The paper defines a brick as a 3-connected graph G such that G minus any two distinct vertices has a perfect matching, and a minimal brick as one where deleting any single edge destroys the brick property. It proves a generation theorem that constructs all minimal bricks via a recursive set of operations, and derives two corollaries: for n>4 every minimal brick on 2n vertices has at most 5n-7 edges, and every minimal brick has at least three vertices of degree three.

Significance. If the generation theorem is complete, the result supplies an explicit recursive description of all minimal bricks and yields concrete, falsifiable bounds on edge count and minimum number of degree-3 vertices. These are derived directly from the construction rather than from external parameters or fitting, which strengthens the contribution to the structural theory of bricks and matching-covered graphs.

major comments (1)

[Generation theorem and proof of corollaries] The generation theorem (whose statement appears in the abstract and is invoked for both corollaries) is load-bearing: the edge upper bound of 5n-7 and the claim of at least three degree-3 vertices are obtained by induction over the recursive construction. No independent verification (e.g., exhaustive enumeration of all minimal bricks on 2n vertices for small n such as n=5 or n=6) is referenced to confirm that every minimal brick arises from the allowed operations and that no extraneous graphs are included.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their detailed review and for highlighting the central role of the generation theorem. We address the concern point by point below.

read point-by-point responses

Referee: [Generation theorem and proof of corollaries] The generation theorem (whose statement appears in the abstract and is invoked for both corollaries) is load-bearing: the edge upper bound of 5n-7 and the claim of at least three degree-3 vertices are obtained by induction over the recursive construction. No independent verification (e.g., exhaustive enumeration of all minimal bricks on 2n vertices for small n such as n=5 or n=6) is referenced to confirm that every minimal brick arises from the allowed operations and that no extraneous graphs are included.

Authors: The generation theorem is established by a direct, bidirectional proof: we show both that every minimal brick arises from the base cases via the listed operations and that every graph produced by the operations is a minimal brick. This equivalence is proved without external assumptions, so the construction is complete and contains no extraneous graphs by the logic of the argument itself. The two corollaries then follow by induction on the recursive structure, examining how the operations affect the number of edges and the degrees. Because the proof already guarantees that the construction enumerates precisely the minimal bricks, separate computational enumeration for small even orders is not required for correctness; it would only serve as an optional consistency check. We therefore maintain that the existing proof suffices and no revision is needed on this point. revision: no

Circularity Check

0 steps flagged

No circularity: direct proof of generation theorem with independent corollaries

full rationale

The paper states a generation theorem for minimal bricks and derives two corollaries directly from it. No self-definitional relations, fitted parameters renamed as predictions, or load-bearing self-citations appear. The structure is a standard mathematical proof establishing the theorem first, then obtaining bounds as consequences; the derivation chain does not reduce to its own inputs by construction. This is self-contained against external verification via the proof itself.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard definitions of 3-connectivity and perfect matchings together with the unstated details of the generation theorem itself; no free parameters or new entities are introduced.

axioms (1)

standard math Standard definitions of 3-connected graphs and perfect matchings in the definition of a brick
These are the background notions invoked to define the objects under study.

pith-pipeline@v0.9.0 · 5594 in / 1178 out tokens · 31234 ms · 2026-05-25T13:08:58.924281+00:00 · methodology

Minimal bricks

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)