pith. sign in

arxiv: 2412.16018 · v2 · submitted 2024-12-20 · 🧮 math.CO

Stable cuts, NAC-colourings and flexible realisations of graphs

Katie Clinch , D\'aniel Garamv\"olgyi , John Haslegrave , Tony Huynh , Jan Legersk\'y , Anthony Nixon This is my paper

Pith reviewed 2026-05-23 06:50 UTC · model grok-4.3

classification 🧮 math.CO
keywords flexible graphsstable cutsNAC-colouringsminimally rigid graphsflexible realizationscombinatorial rigiditygraph colourings
0
0 comments X

The pith

Every flexible graph has a stable cut.

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

The paper proves that any graph flexible in the plane must contain a stable cut. This strengthens an earlier bound that applied only to sparse graphs. The existence of such a cut, combined with a known theorem on stable cuts, establishes a conjecture that fully characterizes the minimally rigid graphs admitting a flexible realization with positive edge lengths. The authors also give an upper bound on the number of NAC-colourings of any graph and exhibit families, including rigid ones, that realize exponentially many such colourings.

Core claim

Every flexible graph has a stable cut. Using a result of Le and Pfender on stable cuts, this fact proves the conjecture of Grasegger, Legerský and Schicho that characterises the minimally rigid graphs which admit a flexible realisation.

What carries the argument

Stable cut: a cut whose removal produces components whose edge counts and connectivity satisfy the stability conditions used to certify flexibility in realizations.

If this is right

  • The Grasegger-Legerský-Schicho conjecture holds, so the minimally rigid graphs that admit flexible realizations are exactly those with a stable cut of the required type.
  • Existence of a stable cut is sufficient for a graph to be flexible, though not necessary for the existence of some flexible realization.
  • The maximum number of NAC-colourings on an n-vertex graph is bounded above by a function of n.
  • There exist infinite families of rigid and minimally rigid graphs possessing exponentially many NAC-colourings.

Where Pith is reading between the lines

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

  • Stable cuts may serve as a practical certificate when testing whether a given rigid graph admits a non-generic flexible realization.
  • The exponential lower bounds on NAC-colourings suggest that enumeration algorithms for flexible realizations will face combinatorial explosion even on some rigid input graphs.
  • The stable-cut property could be checked in polynomial time for certain graph classes, offering a route to efficient recognition of graphs that admit flexible realizations.

Load-bearing premise

The theorem of Le and Pfender on stable cuts applies without change to the graphs obtained from generic realizations of the flexible graphs under study.

What would settle it

A single flexible graph (in the plane) that contains no stable cut would refute the central claim.

Figures

Figures reproduced from arXiv: 2412.16018 by Anthony Nixon, D\'aniel Garamv\"olgyi, Jan Legersk\'y, John Haslegrave, Katie Clinch, Tony Huynh.

Figure 1
Figure 1. Figure 1: The 3-prism and K3,3 are rigid, but both have flexible realisations (the figures with empty vertices and grey edges). The 3-prism has a unique NAC-colouring modulo swapping colours, while all NAC-colourings of K3,3 are isomorphic to the two displayed ones [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The numbers of minimally rigid graphs on 7 (blue), 8 (red), 9 (green) and 10 vertices (yellow) according to the number of NAC-colourings. The maximal values for each number of vertices are indicated by the labels. On 6 vertices, there are 5 graphs with no NAC-colouring, 5 with NAC#(G) = 1, 3 with NAC#(G) = 2, and the complete bipartite graph K3,3 with NAC#(K3,3) = 15. The numbers were determined compu￾tati… view at source ↗
Figure 3
Figure 3. Figure 3: The numbers of minimally rigid graphs on 11 (green) and 12 vertices (yellow) according to the number of NAC-colourings. The numbers were determined computationally using the code supporting [18] and the generator of minimally rigid graphs [17] [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Some graphs maximising the number of NAC-colourings among minimally rigid graphs on 8 (top left), 9 (top middle and right), 10 (bottom left), 11 (bottom middle) and 12 vertices (bottom right). On 7 vertices the unique graph attaining the maximum is K3,3 with one open 0-extension. the next four edges so that Gk[{ai , ai+1, ai+2, bi , bi+1, bi+2}] has no almost-monochromatic cycle (see [PITH_FULL_IMAGE:figu… view at source ↗
Figure 5
Figure 5. Figure 5: The graph Gk. or or or or [PITH_FULL_IMAGE:figures/full_fig_p014_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The diagram shows how two consecutive parts of the graph G′ k can be coloured. Thus e = aiai+1 or e = bibi+1 for some 2 ≤ i ≤ k − 2. Consider the two edges aibi+1 and biai+1. Both are chords of C, and if either is blue then one of the two cycles formed by adding that edge to C is almost-blue and avoids a1 or ak, a contradiction. So both are red, but then aiai+1bibi+1ai is almost-red, and c ′ is not a local… view at source ↗
Figure 7
Figure 7. Figure 7: An 18-vertex minimally-rigid graph H with NAC#(H) = 180 607 (computed us￾ing [18]), which can be obtained by 0-extensions from the 12-vertex graph in [PITH_FULL_IMAGE:figures/full_fig_p015_7.png] view at source ↗
read the original abstract

A (2-dimensional) realisation of a graph $G$ is a pair $(G,p)$, where $p$ maps the vertices of $G$ to $\mathbb{R}^2$. A realisation is flexible if it can be continuously deformed while keeping the edge lengths fixed, and rigid otherwise. We say that $G$ is rigid if every generic realisation of $G$ is rigid; otherwise, $G$ is flexible. In this paper, we investigate the relationship between stable cuts and graphs which are either flexible, or admit a flexible (not necessarily generic) realisation with positive edge lengths. We strengthen a result of Chen and Yu, who proved that every $n$-vertex graph with at most $2n-4$ edges has a stable cut, by showing that every flexible graph has a stable cut. The existence of a stable cut is a sufficient, but not necessary, condition for a flexible realisation to exist. Using a result of Le and Pfender on stable cuts, we prove a conjecture of Grasegger, Legersk\'y and Schicho that characterises the minimally rigid graphs which admit a flexible realisation. Additionally, we investigate the number of NAC-colourings in various graphs. A NAC-colouring is a type of edge colouring introduced by Grasegger, Legersk\'y and Schicho, who showed that the existence of such a colouring characterises the existence of a flexible realisation with positive edge lengths. We provide an upper bound on the number of NAC-colourings for arbitrary graphs, and construct families of graphs, including rigid and minimally rigid ones, for which this number is exponential in the number of vertices.

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.

Referee Report

1 major / 2 minor

Summary. The manuscript proves that every flexible graph has a stable cut (strengthening Chen-Yu), then invokes a result of Le and Pfender on stable cuts to prove the Grasegger-Legerský-Schicho conjecture characterizing minimally rigid graphs that admit flexible realizations. It also establishes an upper bound on the number of NAC-colourings for arbitrary graphs and constructs families (including rigid and minimally rigid graphs) with exponentially many NAC-colourings in the number of vertices.

Significance. If the central claims hold, the work resolves a conjecture in combinatorial rigidity theory and supplies new results on stable cuts and NAC-colourings. The exponential constructions and the bound on NAC-colourings are concrete contributions; the conjecture proof would be a notable application of stable-cut techniques if the invocation of prior results is fully justified.

major comments (1)
  1. [the section applying Le and Pfender to prove the conjecture] The proof that every flexible graph has a stable cut is used to invoke Le and Pfender and thereby establish the conjecture. The manuscript does not explicitly verify that the stable cuts obtained for graphs arising from generic realizations satisfy any additional hypotheses (e.g., on edge lengths, genericity, or the precise stability definition) required by the Le-Pfender theorem. This step is load-bearing for the conjecture characterization.
minor comments (2)
  1. [Introduction] Clarify in the introduction whether the upper bound on NAC-colourings is tight and whether the exponential families are minimally rigid or merely rigid.
  2. [the paragraph stating the stable-cut theorem] The statement of the strengthened Chen-Yu result could include a brief comparison of the edge-count hypotheses.

Simulated Author's Rebuttal

1 responses · 0 unresolved

Thank you for the careful review and for highlighting the need for explicit verification when invoking the Le-Pfender result. We address the single major comment below and will revise the manuscript to incorporate the requested clarification.

read point-by-point responses

  1. Referee: [the section applying Le and Pfender to prove the conjecture] The proof that every flexible graph has a stable cut is used to invoke Le and Pfender and thereby establish the conjecture. The manuscript does not explicitly verify that the stable cuts obtained for graphs arising from generic realizations satisfy any additional hypotheses (e.g., on edge lengths, genericity, or the precise stability definition) required by the Le-Pfender theorem. This step is load-bearing for the conjecture characterization.

    Authors: We agree that the manuscript would benefit from an explicit verification paragraph. Our Theorem establishing the existence of a stable cut is purely combinatorial and produces a cut whose stability is defined exactly as in Le and Pfender; the construction does not depend on a particular realization or on edge lengths. The graphs to which the conjecture applies are the same abstract graphs, and the flexible realizations whose existence is guaranteed by Le and Pfender are non-generic, so no extra genericity or length hypotheses are imposed by their statement. Nevertheless, to make the matching of definitions transparent, we will insert a short subsection (or paragraph) immediately before the invocation of Le and Pfender that records this verification. We therefore mark the revision as yes. revision: yes

Circularity Check

0 steps flagged

No circularity; new theorem proved from graph definitions and external results

full rationale

The paper proves every flexible graph has a stable cut by strengthening Chen-Yu (new combinatorial argument on flexible graphs), then applies the external Le-Pfender theorem on stable cuts to resolve the Grasegger-Legerský-Schicho conjecture. No derivation step reduces by construction to its own inputs, fitted parameters, or self-citation chains; the central claims rest on independent external theorems and standard definitions of rigidity/flexibility. Author overlap with the conjecture is irrelevant because the conjecture is the target being proved, not a premise.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard axioms of finite undirected graphs and the definition of generic realizations in the plane; no free parameters or invented entities are introduced.

axioms (1)
  • standard math Graphs are finite, simple, undirected; realizations map vertices to R^2 with Euclidean distances.
    Invoked throughout the definitions of rigidity and flexibility.

pith-pipeline@v0.9.0 · 5854 in / 1212 out tokens · 26693 ms · 2026-05-23T06:50:55.114813+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

  1. [1]

    Asimow and B

    L. Asimow and B. Roth. The rigidity of graphs. Transactions of the American Mathematical Society, 245:279–289, 1978.doi:10.2307/1998867

    work page doi:10.2307/1998867 1978

  2. [2]

    Blass and Y

    A. Blass and Y. Gurevich. On the unique satisfiability problem.Information and Control, 55(1-3):80–88,

    work page

  3. [3]

    doi:10.1016/S0019-9958(82)90439-9

    work page doi:10.1016/s0019-9958(82)90439-9

  4. [4]

    Capco, M

    J. Capco, M. Gallet, G. Grasegger, C. Koutschan, N. Lubbes, and J. Schicho. The number of realizations of all Laman graphs with at most 12 vertices. Zenodo, 2018.doi:10.5281/zenodo.1245517. 17

    work page doi:10.5281/zenodo.1245517 2018

  5. [5]

    Chen and X

    G. Chen and X. Yu. A note on fragile graphs.Discrete Mathematics, 249(1-3):41–43, 2002. Combinatorics, graph theory and computing (Louisville, KY, 1999).doi:10.1016/S0012-365X(01)00226-6

    work page doi:10.1016/s0012-365x(01)00226-6 2002

  6. [6]

    Chernyshev, J

    V. Chernyshev, J. Rauch, and D. Rautenbach. Forest Cuts in Sparse Graphs, 2024. arXiv preprint.doi: 10.48550/arXiv.2409.17724

    work page doi:10.48550/arxiv.2409.17724 2024

  7. [7]

    A. Dixon. On certain deformable frameworks.Messenger, 29(2):1–21, 1899

    work page

  8. [8]

    Point-hyperplaneframeworks, slider joints, and rigidity preserving transformations.Journal of Combinatorial Theory

    Y.Eftekhari, B.Jackson, A.Nixon, B.Schulze, S.Tanigawa, andW.Whiteley. Point-hyperplaneframeworks, slider joints, and rigidity preserving transformations.Journal of Combinatorial Theory. Series B, 135:44–74,

    work page

  9. [9]

    doi:10.1016/j.jctb.2018.07.008

    work page doi:10.1016/j.jctb.2018.07.008 2018

  10. [10]

    P. C. Fishburn and P. L. Hammer. Bipartite dimensions and bipartite degrees of graphs.Discrete Mathe- matics, 160(1-3):127–148, 1996.doi:10.1016/0012-365X(95)00154-O

    work page doi:10.1016/0012-365x(95)00154-o 1996

  11. [11]

    Gallet, G

    M. Gallet, G. Grasegger, J. Legerský, and J. Schicho. On the existence of paradoxical motions of generically rigid graphs on the sphere.SIAM Journal on Discrete Mathematics, 35(1):325–361, 2021.doi:10.1137/ 19M1289467

    work page 2021

  12. [12]

    Globalrigidityof(quasi-)injectiveframeworksontheline

    D.Garamvölgyi. Globalrigidityof(quasi-)injectiveframeworksontheline. Discrete Mathematics, 345(2):Pa- per No. 112687, 8, 2022.doi:10.1016/j.disc.2021.112687

    work page doi:10.1016/j.disc.2021.112687 2022

  13. [13]

    Grasegger, J

    G. Grasegger, J. Legerský, and J. Schicho. Graphs with flexible labelings. Discrete & Computational Geometry, 62(2):461–480, 2019.doi:10.1007/s00454-018-0026-9

    work page doi:10.1007/s00454-018-0026-9 2019

  14. [14]

    Grasegger, J

    G. Grasegger, J. Legerský, and J. Schicho. Graphs with flexible labelings allowing injective realizations. Discrete Mathematics, 343(6):111713, 14, 2020.doi:10.1016/j.disc.2019.111713

    work page doi:10.1016/j.disc.2019.111713 2020

  15. [15]

    Grasegger and J

    G. Grasegger and J. Legerský. FlexRiLoG — A SageMath Package for Motions of Graphs. InMathemat- ical Software – ICMS 2020, volume 12097 ofLecture Notes in Computer Science, pages 442–450. Springer International Publishing, 2020.doi:10.1007/978-3-030-52200-1_44

    work page doi:10.1007/978-3-030-52200-1_44 2020

  16. [16]

    T. Jordán. Combinatorial Rigidity: Graphs and Matroids in the Theory of Rigid Frameworks. InDiscrete Geometric Analysis, volume 34 ofMSJ Mem., pages 33–112. Math. Soc. Japan, Tokyo, 2016

    work page 2016

  17. [17]

    A. Kempe. On Conjugate Four-piece Linkages.Proceedings of the London Mathematical Society, s1-9(1):133– 149, 11 1877. doi:10.1112/plms/s1-9.1.133

    work page doi:10.1112/plms/s1-9.1.133

  18. [18]

    G. Laman. On graphs and rigidity of plane skeletal structures.Journal of Engineering Mathematics, 4:331– 340, 1970. doi:10.1007/BF01534980

    work page doi:10.1007/bf01534980 1970

  19. [19]

    M. Larsson. Nauty Laman plugin.https://github.com/martinkjlarsson/nauty-laman-plugin, 2020

    work page 2020

  20. [20]

    Laštovička and J

    P. Laštovička and J. Legerský. Flexible realizations existence: NP-completeness on sparse graphs and algorithms, 2024. arXiv preprint.doi:10.48550/arXiv.2412.13721

    work page doi:10.48550/arxiv.2412.13721 2024

  21. [21]

    V. B. Le and F. Pfender. Extremal graphs having no stable cutsets.Electronic Journal of Combinatorics, 20(1):Paper 35, 7, 2013.doi:10.37236/2513

    work page doi:10.37236/2513 2013

  22. [22]

    V. B. Le and B. Randerath. On stable cutsets in line graphs.Theoretical Computer Science, 301(1-3):463– 475, 2003. doi:10.1016/S0304-3975(03)00048-3

    work page doi:10.1016/s0304-3975(03)00048-3 2003

  23. [23]

    Lee and I

    A. Lee and I. Streinu. Pebble game algorithms and sparse graphs.Discrete Mathematics, 308(8):1425–1437,

    work page

  24. [24]

    doi:10.1016/J.DISC.2007.07.104

    work page doi:10.1016/j.disc.2007.07.104 2007

  25. [25]

    Pollaczek-Geiringer

    H. Pollaczek-Geiringer. Über die Gliederung ebener Fachwerke.Zeitschrift für Angewandte Mathematik und Mechanik, 7(1):58–72, 1927.doi:10.1002/zamm.19270070107

    work page doi:10.1002/zamm.19270070107 1927

  26. [26]

    Rauch and D

    J. Rauch and D. Rautenbach. Revisiting extremal graphs having no stable cutsets, 2024. arXiv preprint. doi:10.48550/arXiv.2412.00337

    work page doi:10.48550/arxiv.2412.00337 2024

  27. [27]

    Whiteley

    W. Whiteley. Cones, infinity and 1-story buildings. Structural Topology, 8:53–70, 1983. URL: https: //hdl.handle.net/2099/1003

    work page 1983

  28. [28]

    Whiteley

    W. Whiteley. Vertex splitting in isostatic frameworks.Structural Topology, 16:23–30, 1990. URL:https: //hdl.handle.net/2099/1055. 18

    work page 1990