OFFSET
8,4
COMMENTS
A graph G is d-rigid, if every generic realization p in dimension d yields a framework (G,p) that is infinitesimally d-rigid; i.e., all its infinitesimal flexes are trivial. It is minimally d-rigid if it is d-rigid but looses this property upon deletion of any edge.
Every minimally 8-rigid graph with n>8 is (8,36)-sparse, that is every subgraph with n'>=8 vertices spans at most 8n'-36 edges. Minimally 8-rigid graphs have 8n-36 edges and hence are (8,36)-tight but not every (8,36)-tight graph is minimally 8-rigid.
LINKS
Matteo Gallet, Georg Grasegger, Matthias Himmelmann and Jan Legerský, PyRigi -- a general-purpose Python package for the rigidity and flexibility of bar-and-joint frameworks, ACM Transactions on Mathematical Software, 2026.
Georg Grasegger, Dataset of minimally d-rigid graphs, 2026.
Georg Grasegger, RigiComp - A Mathematica package for computational rigidity of graphs, 2022.
PyRigi Developers, Rigidity Theory, 2025.
Walter Whiteley, Some matroids from discrete applied geometry, 1996.
EXAMPLE
The complete graphs on eight and nine vertices are minimally 8-rigid. So is the complete graph on ten vertices with one edge removed. The three graphs that can be obtained from the previous one by adding a new vertex and connecting it to 8 of the existing vertices, are also minimally 8-rigid.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Georg Grasegger, Jun 12 2026
STATUS
approved