The Rigidity of Graphs

We regard a graph G as a set <!-- MATH $\{ 1, \ldots , v \}$ --> together with a nonempty set E of two-element subsets of <!-- MATH $\{ 1, \ldots , v \}$ --> . Let <!-- MATH $p = ({p_1},\ldots,{p_v})$ --> be an element of <!-- MATH ${\textbf{R}^{nv}}$ --> representing v points in <!-- MATH ${\textbf{R}^n}$ --> . Consider the figure in <!-- MATH ${\textbf{R}^n}$ --> consisting of the line segments <!-- MATH $[{p_i},{p_j}]$ --> in <!-- MATH ${\textbf{R}^n}$ --> for <!-- MATH $\{ i,j\} \in E$ --> . The figure is said to be rigid in <!-- MATH ${\textbf{R}^n}$ --> if every continuous path in <!-- MATH ${\textbf{R}^{nv}}$ --> , beginning at p and preserving the edge lengths of , terminates at a point <!-- MATH $q \in {\textbf{R}^{nv}}$ --> which is the image <!-- MATH $(T{p_1}, \ldots ,T{p_v})$ --> of p under an isometry T of <!-- MATH ${\textbf{R}^n}$ --> . Otherwise, is flexible in <!-- MATH ${\textbf{R}^n}$ --> . Our main result establishes a formula for determining whether is rigid in <!-- MATH ${\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 <!-- MATH ${\textbf{R}^3}$ --> , and other related matters.