The Rigidity of Graphs
L. Asimow, B. Roth · Transactions of the American Mathematical Society · 1978
We regard a graph G as a set $\{ 1, \ldots , v \}$ together with a nonempty set E of two-element subsets of $\{ 1, \ldots , v \}$. Let $p = ({p_1},\ldots ,{p_v})$ be an element of ${\textbf {R}^{nv}}$ representing v points in ${\textbf {R}^n}$. Consider the figure $G(p)$ in ${\textbf {R}^n}$ consisting of the line segments $[{p_i},{p_j}]$ in ${\textbf {R}^n}$ for $\{ i,j\} \in E$. The figure $G(p)$ is said to be rigid in ${\textbf {R}^n}$ if every continuous path in ${\textbf {R}^{nv}}$, beginning at p and preserving the edge lengths of $G(p)$, terminates at a point $q \in {\textbf {R}^{nv}}$ which is the image $(T{p_1}, \ldots ,T{p_v})$ of p under an isometry T of ${\textbf {R}^n}$. Otherwise, $G(p)$ is flexible in ${\textbf {R}^n}$. Our main result establishes a formula for determining whether $G(p)$ is rigid in ${\textbf {R}^n}$ for almost all locations p of the vertices. Applications of the formula are made to complete graphs, planar graphs, convex polyhedra in ${\textbf {R}^3}$, and other related matters.