The word "rigid" has two different meaning 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.) Rigidity of a framework 
, i.e., a structure with vertex coordinates 
and underlying graph 
having vertex set 
and edge set 
, can be thought of in two equivalent
ways: infinitesimal rigidity (which considers infinitesimal displacements corresponding
to velocity vectors) and static rigidity (which considers forces and loads on the
structure).
A framework consisting of bars is said to be (infinitesimally) rigid iff continuous motion of the points of the configuration
maintaining the bar constraints comes from a family of motions of all Euclidean
space which are distance-preserving. This is equivalent to the condition that
there exists an 
such that every framework 
which is equivalent to 
and satisfies 
for all 
is congruent to the framework 
.
A framework 
is infinitesimally rigid iff the rank of its rigidity
matrix 
satisfies
 |
where 
is the vertex count (Grasegger 2023).
Call a framework 
a generic realization of 
if the rigidity matrix 
is equal to the rigidity matroid 
. This occurs when the coordinates of all points 
are algebraically independent over the field of rationals
. A graph (as an abstract object with
no explicit embedding) is said to be rigid iff there is a
generic realization for which the framework is generically rigid. Similarly, a graph 
is said to be (generically) 
-rigid if, for almost all (i.e., an open dense set of) configurations
of 
, the framework 
is rigid in 
.
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. In general, however, a 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).
