5-regular graphs and the 3-dimensional rigidity matroid

Anthony Nixon; Rebecca Monks

REVIEW 3 major objections 4 minor 20 references

5-regular graphs and the 3-dimensional rigidity matroid

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

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

Pith's one-line read Every 5-regular, 3-sparse graph is independent in the generic 3-dimensional rigidity matroid.

desk verdict A serious proof of the Jackson–Jordan 5-regular conjecture, but the black-box computer check in Lemma 4.5 and a compressed termination argument need to be fixed before the proof is fully verifiable. read the letter →

arxiv 2506.22214 v1 pith:HSFZBI4A submitted 2025-06-27 math.CO

Rebecca Monks , Anthony Nixon This is my paper · ORCID

classification math.CO MSC 52C2505B3505C75

keywords rigiditymatroidgeneric3-sparsegraphs5-regularbar-jointframeworksvertexsplitspiderMaxwellcount

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 proves that for 5-regular graphs, a purely combinatorial edge-counting condition is equivalent to being independent in the generic 3-dimensional rigidity matroid. Rigidity matroid independence means no edge of the graph is redundant given the others, so such a graph has no internal degree of freedom that a small perturbation of its vertices could exploit. This was the last open case of a 2005 conjecture about graphs whose vertex degrees are tightly bounded, and it provides one of the few infinite families of 3D graphs where Maxwell's necessary count is also sufficient. The proof is combinatorial: it shows any minimal counterexample would have to shrink by a valid reduction, and the only graphs that cannot shrink are handled by a computer check on 12 and 14 vertices.

What carries the argument

The carrying objects are the vertex split and spider split, inverse operations (edge contraction and spider contraction) that preserve $R_3$-independence in one direction and, when admissible, preserve 3-sparsity in the other. A 'blocker' is a small dense set that makes a reducible contraction non-admissible; the proof classifies blockers as 6-, 7-, or 8-sets and uses their intersections and closures to force the existence of an admissible reduction. The base case is a computer verification for 12 and 14 vertices, from which the case analysis starts.

What would settle it

Recompute the enumeration of connected 5-regular 3-sparse graphs on 12 and 14 vertices and compute the symbolic rank of their 3D rigidity matrices; finding a single such graph whose rows are dependent would refute Theorem 1.3. Alternatively, construct a 5-regular 3-sparse graph on 16 or more vertices that is an $R_3$-circuit, which would be a minimal counterexample of the kind the paper rules out.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.3: a 5-regular graph $G$ is $R_3$-independent if and only if it is 3-sparse, where 3-sparse means every induced subgraph on $n\ge 3$ vertices has at most $3n-6$ edges. The necessity is Maxwell's classical count. The sufficiency is the paper's contribution. The proof assumes a minimal counterexample, uses Corollary 2.5 to show it must be an $R_3$-circuit, invokes a computer check to push its order to at least 16, and then shows through a long case analysis that some reducible edge or vertex-pair can be contracted so that the result is still 3-sparse; by the split lemmas this would make the original graph $R_3$-independent, contradicting minimality. Thus no minimal counterexample exists.

Load-bearing premise

The whole proof leans on the computer-assisted claim that every connected 5-regular 3-sparse graph on 12 or 14 vertices is $R_3$-independent; if that enumeration or symbolic-rank check is wrong, the case analysis loses its base cases and the sufficiency proof collapses.

Editorial extensions

If this is right

A 5-regular, 3-sparse graph on 12 vertices is generically minimally rigid in 3D; on 14 or more vertices it is an independent set in the rigidity matroid, so adding any edge creates a circuit.
The class of 5-regular 3-sparse graphs can be recognized by a polynomial-time count: no subgraph on $n$ vertices may contain more than $3n-6$ edges.
The $d=3$, maximum-degree case of the bounded-degree characterization is now closed, and the proof supplies new admissible-reduction criteria for 5-regular graphs in the 3D matroid.
The reduction machinery applies to both edge contractions and spider contractions, giving a toolbox for future degree-constrained rigidity results in 3D.

Reading between the lines

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

Beyond the paper, the unpublished computer check of the 12- and 14-vertex base cases is the only non-hand-proved dependency; if the enumeration and symbolic-rank data were released, the whole theorem would become independently verifiable.
Beyond the paper, the blocker machinery may extend to classify finite exceptional families for other highly regular sparse graphs, for example $(d+2)$-regular $d$-sparse graphs in higher dimensions where infinite counterexamples are already known.
Beyond the paper, the same split-and-contraction strategy is a plausible route to an $\ell_p$ rigidity analogue, since the paper notes the bounded-degree theorem has already been adapted to $\ell_p$ rigidity.
Beyond the paper, a natural computational test is to search for 5-regular 3-sparse graphs on 16 vertices that are $R_3$-circuits; the theorem predicts none exist, and the blocker analysis predicts any near miss would reveal a new structural obstruction.

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.

Desk Editor's Note

read the letter

Tom — this is the real thing: Monks and Nixon prove Jackson and Jordan's 2005 conjecture that every 5-regular, 3-sparse graph is R3-independent. That is not a routine extension. They need a new extension theorem (2.1) that allows one vertex of arbitrary degree, and a careful blocker analysis for edge and spider contractions. The overall architecture is sound and the combinatorics is genuinely intricate. Section 2's Theorem 2.1 is a useful standalone tool, since the existing bounded-degree result couldn't handle the high-degree vertex produced by a contraction.

The proof strategy is coherent: take a minimal counterexample, show it is an R3-circuit, rule out reducible contractions, analyze blockers, then use maximal proper cores. I read through the claims and the lemma chain; the sparse graph arguments check out as far as I can tell. The reliance on known tools (Whiteley splits, isostatic substitution, Jackson–Jordan's bounded-degree theorem) is appropriate.

The soft spots are real but localized. Lemma 4.5 is a computational assertion covering all connected 5-regular 3-sparse graphs on 12 and 14 vertices, with no code, data, or version numbers shipped. The footnote even says the authors didn't compute the exact number of sparse graphs. I believe the check is probably correct (the graph counts from Nauty are right, and PyRigi's rank computation is standard), but as submitted it is a black box, and the proof's base case |V| >= 16 depends entirely on it. That is fixable: the authors need to provide the enumeration script and output.

Second, the final paragraph of the main proof compresses the termination of the expanding process in Claim 11 and what follows. It says 'this process must terminate' after constructing p1, p2, etc., but the argument is sketched, not written. A referee will need to fill in a real induction. I don't think it is wrong, but it is under-specified.

There are also a few places in Section 4 where 'by symmetry' and 'similarly' cover a lot of case work. That's normal for this kind of paper; not a red flag, but it makes verification slow.

Bottom line: the central claim is new, important, and likely correct. The paper deserves a serious referee and will pass if the authors supply the computational artifact and tighten the termination argument. I would take it to reading group, but I'd warn people about Lemma 4.5.

Referee Report

3 major / 4 minor

Summary. The paper proves the Jackson–Jordán conjecture that every 5-regular 3-sparse graph is independent in the generic 3-dimensional rigidity matroid. The proof proceeds by a minimal counterexample, using a new bounded-degree extension (Theorem 2.1), a detailed analysis of edge and spider contractions that preserve 3-sparsity (Section 3), the isostatic substitution principle, and a computational base case for graphs on 12 and 14 vertices (Lemma 4.5).

Significance. If the proof is correct, this settles a 2005 conjecture of Jackson and Jordán and provides one of the rare exact combinatorial characterizations of R3-independence for an infinite family of graphs. The paper makes good use of established tools (vertex/spider splits, isostatic substitution, Maxwell's condition), and the structural analysis in Section 3 is extensive. The main barriers to full verification are the unshipped computational lemma and the compressed final termination argument; if those are resolved, the contribution is substantial.

major comments (3)

[Lemma 4.5] Lemma 4.5 asserts that all connected 5-regular 3-sparse graphs on 12 or 14 vertices are R3-independent. The proof provides only the counts of all connected 5-regular graphs produced by Nauty (7848 and 3,459,383), states that 'one can compute the rank ... in, for example, PyRigi', and does not supply code, data, software versions, or exact counts of the 3-sparse subfamily. Footnote 1 explicitly says that the number of relevant sparse graphs was not calculated. Since this lemma is the only mechanism by which the proof excludes minimal counterexamples with |V| = 12 or 14, an error in the enumeration or symbolic rank computation would leave the base cases unproved. Please provide a complete reproducible certificate (versioned software, enumeration filters, exact arithmetic rank checks, and output files), or a human-verifiable proof of this lemma.
[Section 4.2, final paragraph of Claim 11] The proof closes by saying 'Since G is connected, V is finite and W ≠ V, this process must terminate giving either an admissible vertex-pair or a contradiction.' This iterative argument is not specified: no termination measure is given, the 'previous argument' is not formalized, and the cases in which the process produces an admissible pair versus a contradiction are not articulated. Because this step rules out the last remaining configuration in the minimal counterexample, it is load-bearing. Please expand it into a complete case analysis with an explicit well-founded induction or an alternative argument.
[Section 4.2, Claim 2] In Claim 2, after showing that at least one of G−at+ab and G−at+tc is 3-sparse, the proof states that at least one is connected and hence R3-independent by Theorem 2.1. Connectivity is not established: if at is a bridge, the argument depends on the locations of b and c in the two components of G−at. Please supply the missing connectivity argument (or adapt the reasoning to handle disconnected graphs), since Theorem 2.1 as stated requires a connected, indeed 2-connected, graph.

minor comments (4)

[Lemma 3.10] In the second paragraph of the proof, when |X| = 4 and X ∩ Y = {a,b} with ab ∈ E, the derivation i(X \ {a,b}) = 3|X \ {a,b}| − 5 does not contradict 3-sparsity because |X \ {a,b}| = 2 is below the threshold for the sparsity inequality. The case should be ruled out separately, or the lemma could be restricted to |X|,|Y| ≥ 5, which is all that is used in Section 4.
[Corollary 2.5] In the proof of Corollary 2.5, the invocation of Lemma 2.4(1) for the two disjoint components H1 and H2 should be a reference to Lemma 2.4(2), since H1 ∩ H2 is empty rather than Rd-rigid.
[Propositions 4.2 and 4.4] The stated hypothesis 'Y ∪ Z = Y ∪ Z = V' is redundant because Y ∪ Z = Y ∪ Z is trivially true; based on the proofs, the intended hypothesis appears to be 'Y ∪ Z = V'.
[Claim 10] The sentence 'Note next that all common neighbours of {u, w} are not in Y. If such a vertex was in Y then...' mixes an assertion with a counterfactual; please rephrase to make the argument by contradiction explicit.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 1.3 is proved from external rigidity theorems and independent internal case analysis; the computational base case is a verifiability caveat, not a circular dependency.

full rationale

The sufficiency direction of Theorem 1.3 is obtained by assuming a minimal counterexample G and deriving contradictions through a sequence of lemmas. Every load-bearing external input is an established, non-self-cited result: Maxwell's lemma (Lemma 1.1), Asimow–Roth, Jackson–Jordan's bounded-degree characterization (Theorem 1.2), Whiteley's vertex split/spider split and isostatic substitution lemmas (Lemmas 1.4 and 1.5), and Graver–Servatius–Servatius/Whiteley extension lemmas (Lemmas 2.2–2.4). The authors' new results (Theorem 2.1, contraction lemmas, blocker analysis) are proved combinatorially from these inputs without reusing the theorem being proved. Self-citations appear only incidentally: [7] and [4] are cited to illustrate sharpness or to point to related work, and neither citation supplies the central claim. Lemma 4.5 is a finite verification on graphs of order 12 and 14; it is not a fitted parameter or a renamed prediction, and its conclusion is not used to define the objects of the theorem. The unshipped code/data and the footnote admitting that the exact number of 3-sparse graphs was not computed are reproducibility limitations, but they do not make the argument circular. No equation or claim in the paper reduces by construction to its own input, and no uniqueness theorem from the authors' prior work is invoked to forbid alternatives. Hence the derivation is self-contained with respect to circularity, and the score is 0.

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

This is a pure mathematics proof; no parameters were fitted to data. The axioms are standard rigidity-theory results plus one tooling assumption about the correctness of finite computations in Lemma 4.5. No new physical or formal entities are postulated.

assumptions (7)

domain assumption Generic rigidity is a matroid property: rank of the rigidity matrix at generic coordinates depends only on the graph (Asimow-Roth).
Used throughout to justify working with the generic 3-dimensional rigidity matroid.
domain assumption Maxwell's sparsity is necessary for R3-independence (Lemma 1.1).
Load-bearing for the necessity direction of Theorem 1.3 and repeatedly used in sparsity arguments.
domain assumption Jackson and Jordan's bounded-degree characterization (Theorem 1.2) holds.
Used as the inductive base and to prove Corollary 2.5 and Theorem 2.1.
domain assumption Vertex split and spider split preserve R3-independence (Lemma 1.4, Whiteley).
Central to showing that a minimal counterexample cannot have an admissible reduction.
domain assumption Isostatic substitution preserves R3-independence (Lemma 1.5, Whiteley and Finbow-Ross-Whiteley).
Used in Claim 2 of the main proof to handle non-complete 6-sets.
domain assumption The extension, reduction, and gluing lemmas for 0- and 1-extensions (Lemmas 2.2, 2.3, 2.4) are correct.
Used in the proof of the new Theorem 2.1.
domain assumption Nauty's enumeration and PyRigi's symbolic rank computation in Lemma 4.5 are correct.
The paper provides no code, data, or version hashes for this finite check; correctness is assumed from tool documentation.

how reviews work

0 comments

Cite this review

Pith. "Pith review of 5-regular graphs and the 3-dimensional rigidity matroid." pith.science (2026). https://pith.science/paper/HSFZBI4A

@misc{pith2026250622214,
  author       = {Pith},
  title        = {Pith review of: 5-regular graphs and the 3-dimensional rigidity matroid},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HSFZBI4A}},
  note         = {Machine review of arXiv:2506.22214}
}

abstract

A bar-joint framework $(G,p)$ in Euclidean $d$-space is rigid if the only edge-length-preserving continuous motions arise from isometries of $\mathbb{R}^d$. In the generic case, rigidity is determined by the generic $d$-dimensional rigidity matroid of $G$. The combinatorial nature of this matroid is well understood when $d=1,2$ but open when $d\geq 3$. Jackson and Jord\'an 2005 characterised independence in this matroid for connected graphs with minimum degree at most $d+1$ and maximum degree at most $d+2$. Their characterisation is known to be false for $(d+2)$-regular graphs when $d\geq 4$ but when $d=3$ it remained open. Indeed they conjectured that their characterisation extends to 5-regular graphs when $d=3$. The purpose of this article is to prove their conjecture. That is, we prove that every 5-regular graph that has at most $3n-6$ edges in any subgraph on $n\geq 3$ vertices is independent in the generic 3-dimensional rigidity matroid.

Figures

Figures reproduced from arXiv: 2506.22214 by the authors.

**Figure 2.** A schematic of the 3-dimensional spider split. [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** An illustration of the proof of Lemma 3.2. In (b) we find K− 6,6 and G[X] = K3,3. In fact any proper core in K− 6,6 induces a copy of K3,3. Hence {c, e} is a vertex-pair so et ∈ E and e needs another neighbour in X. If this is a vertex not previously labelled, say f, then {f, t} is a vertex-pair but t and f cannot have four common neighbours. So cv, ev ∈ E since ca ∈ E creates a triangle. The only remaining vertices… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[1]

T. G. Abbott, Generalizations of Kempe’s Universality Theorem , Masters thesis, MIT, 2008

work page 2008
[2]

Asimow and B

L. Asimow and B. Roth, The rigidity of graphs, Transactions of the American Mathematical Society, 245 (1978) 279–289

work page 1978
[3]

Clinch, B

K. Clinch, B. Jackson and S. Tanigawa, Abstract 3-Rigidity and Bivariate C1 2 -Splines II: Combinatorial Characterization, Discrete Analysis, 3 (2022) 32p

work page 2022
[4]

Dewar, D

S. Dewar, D. Kitson and A. Nixon, Which graphs are rigid in ℓd p?, Journal of global opti- mization, 83 (2022) 49–71. REFERENCES 26

work page 2022
[5]

Finbow, E

W. Finbow, E. Ross and W. Whiteley, The Rigidity of Spherical Frameworks: Swapping Blocks and Holes , SIAM Journal on Discrete Mathematics, 26:1 (2012)

work page 2012
[6]

PyRigi -- a general-purpose Python package for the rigidity and flexibility of bar-and-joint frameworks

M. Gallet, G. Grasegger, M. Himmelmann and J. Legersk´ y, (Maintainers). PyRigi – a general-purpose Python package for the rigidity and flexibility of bar-and-joint frameworks, arXiv:2505.22652, https://github.com/PyRigi/PyRigi

work page Pith review arXiv
[7]

Grasegger, H

G. Grasegger, H. Guler, B. Jackson and A. Nixon, Flexible circuits in the d-dimensional rigidity matroid, Journal of Graph Theory, 100:2 (2022) 315–330

work page 2022
[8]

Graver, B

J. Graver, B. Servatius and H. Servatius, Combinatorial rigidity, American Mathematical Society, Graduate Studies in Mathematics, Providence, RI, 1993

work page 1993

Show all 20 references

[9]

Jackson and T

B. Jackson and T. Jord´ an,The d-dimensional rigidity matroid of sparse graphs , Journal of Combinatorial Theory, Series B, 95 (2005) 118-133

2005
[10]

Jackson and T

B. Jackson and T. Jord´ an, The Dress conjectures on rank in the 3-dimensional rigidity matroid, Advances in Applied Mathematics, 35 (2005) 355–367

2005
[11]

Jord´ an, A note on generic rigidity of graphs in higher dimension , Discrete Applied Mathematics, 297 (2021) 97–101

T. Jord´ an, A note on generic rigidity of graphs in higher dimension , Discrete Applied Mathematics, 297 (2021) 97–101

2021
[12]

Laman, On graphs and rigidity of plane skeletal structures , Journal of Engineering Mathematics, 4 (1970) 331–340

G. Laman, On graphs and rigidity of plane skeletal structures , Journal of Engineering Mathematics, 4 (1970) 331–340

1970
[13]

J. C. Maxwell, On the Calculation of the Equilibrium and Stiffness of Frames , Philos. Mag., 27 (1864) 294–299
[14]

B. D. McKay and A. Piperno, Practical Graph Isomorphism, II, Journal of Symbolic Com- putation, 60 (2014), 94-112

2014
[15]

Pollaczek-Geiringer, Uber die Gliederung ebener Fachwerke, Zeitschrift fur Angewandte Mathematik und Mechanik (ZAMM), 7 (1927) 58-72

H. Pollaczek-Geiringer, Uber die Gliederung ebener Fachwerke, Zeitschrift fur Angewandte Mathematik und Mechanik (ZAMM), 7 (1927) 58-72

1927
[16]

Tay, On generically dependent bar frameworks in space , Structural Topology, 20 (1993) 27–48

T.-S. Tay, On generically dependent bar frameworks in space , Structural Topology, 20 (1993) 27–48

1993
[17]

Watson, Combinatorial rigidity: bounded degree graphs , PhD thesis, Queen Mary, Uni- versity of London, 2008

A. Watson, Combinatorial rigidity: bounded degree graphs , PhD thesis, Queen Mary, Uni- versity of London, 2008

2008
[18]

Whiteley, Infinitesimally rigid polyhedra

W. Whiteley, Infinitesimally rigid polyhedra. I. Statics of frameworks , Trans. Amer. Math. Soc. 285 (1984) 431–465

1984
[19]

Whiteley, Vertex splitting in isostatic frameworks, Structural Topology, 16 (1990) 23-30

W. Whiteley, Vertex splitting in isostatic frameworks, Structural Topology, 16 (1990) 23-30

1990
[20]

Whiteley, Some matroids from discrete applied geometry , in Matroid Theory , J

W. Whiteley, Some matroids from discrete applied geometry , in Matroid Theory , J. E. Bonin, J. G. Oxley, and B. Servatius eds., Contemporary Mathematics 197, American Mathematical Society, 1996, 171–313

1996

Pith tools

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

[1] [1]

T. G. Abbott, Generalizations of Kempe’s Universality Theorem , Masters thesis, MIT, 2008

work page 2008

[2] [2]

Asimow and B

L. Asimow and B. Roth, The rigidity of graphs, Transactions of the American Mathematical Society, 245 (1978) 279–289

work page 1978

[3] [3]

Clinch, B

K. Clinch, B. Jackson and S. Tanigawa, Abstract 3-Rigidity and Bivariate C1 2 -Splines II: Combinatorial Characterization, Discrete Analysis, 3 (2022) 32p

work page 2022

[4] [4]

Dewar, D

S. Dewar, D. Kitson and A. Nixon, Which graphs are rigid in ℓd p?, Journal of global opti- mization, 83 (2022) 49–71. REFERENCES 26

work page 2022

[5] [5]

Finbow, E

W. Finbow, E. Ross and W. Whiteley, The Rigidity of Spherical Frameworks: Swapping Blocks and Holes , SIAM Journal on Discrete Mathematics, 26:1 (2012)

work page 2012

[6] [6]

PyRigi -- a general-purpose Python package for the rigidity and flexibility of bar-and-joint frameworks

M. Gallet, G. Grasegger, M. Himmelmann and J. Legersk´ y, (Maintainers). PyRigi – a general-purpose Python package for the rigidity and flexibility of bar-and-joint frameworks, arXiv:2505.22652, https://github.com/PyRigi/PyRigi

work page Pith review arXiv

[7] [7]

Grasegger, H

G. Grasegger, H. Guler, B. Jackson and A. Nixon, Flexible circuits in the d-dimensional rigidity matroid, Journal of Graph Theory, 100:2 (2022) 315–330

work page 2022

[8] [8]

Graver, B

J. Graver, B. Servatius and H. Servatius, Combinatorial rigidity, American Mathematical Society, Graduate Studies in Mathematics, Providence, RI, 1993

work page 1993