The word "rigid" has two different meanings when applied to a graph. Firstly, a rigid graph may refer to a graph having a graph automorphism group containing a single element. In this work, such a graph is instead referred to using the more common term "identity graph" (e.g., Albertson and Collins 1996).
The more common meaning of rigidity considers a graph's resistance to deformation, where graph edges are commonly taken as rigid straight bars or rods that are connected
to incident vertices via flexible hinges. (Other edge elements such as cables and
struts are sometimes also considered.) A framework consists of an underlying graph
and a placement
of its vertices in Euclidean
space. Two placements are equivalent when corresponding edges
have equal lengths. The framework is rigid iff
there exists
such that every equivalent placement
with
for every
is congruent to
. Here congruence requires agreement
of all pairwise distances between vertices, not only
edge lengths.
Infinitesimal rigidity instead concerns velocity vectors satisfying
on every graph
edge
. A framework is infinitesimally
rigid when all such assignments are induced by translations and infinitesimal rotations
of the ambient Euclidean space. Infinitesimal
rigidity implies rigidity, and the converse holds at generic placements. The converse
can fail at nongeneric placements (Asimow and Roth 1978). The equivalent static formulation
asks whether equilibrium loads can be resolved by forces along the bars (Crapo and
Whiteley 1982). Self-balancing bar forces are described by an equilibrium
stress.
For a framework in whose points affinely span
,
infinitesimal rigidity is equivalent to the matrix rank
condition
Here is the rigidity
matrix and
is the vertex count. For a placement spanning the
plane, this becomes
.
A realization is generic when all its point coordinates are algebraically independent over . A graph is generically
d-rigid when its generic realizations in
are rigid. This is equivalent to rigidity for an open dense
set of placements (Asimow and Roth 1978).
A graph that is not rigid is said to be flexible (Maehara 1992).
Any embeding of the triangle graph is rigid, while any embedding of the square
graph
is flexible.
A flexible graph cannot have a rigid embedding. However, in general, a rigid graph may have both rigid and flexible embeddings. For
example, an embedding of the utility graph in the plane is rigid unless its
six vertices lie on a conic (Bolker and Roth 1980,
Maehara 1992), some examples of which are illustrated above.
Cauchy (1813) proved the rigidity theorem, one of the first results in rigidity theory. Although rigidity problems were of immense interest to engineers, intensive mathematical study of these types of problems has occurred only relatively recently (Connelly 1993, Graver et al. 1993).
Deleting edges or vertices gives different optimization problems for generic planar rigidity. Cong et al. (2026) proved that finding the smallest number of edges whose deletion destroys rigidity is NP-hard, while the corresponding vertex-deletion problem is solvable in polynomial time. For generic global rigidity, both unweighted deletion problems are solvable in polynomial time. With positive integer deletion costs, all four problems are NP-hard, even on generically globally rigid inputs. Cong et al. (2026) attribute discovery of the main result to an AI system using GPT-6 Astra.