9 Laman’s theorem
In this section we prove Laman’s theorem [ PG27 , Lam70 ] in the form stated in section 4: a graph on at least two vertices is generically rigid in the plane if and only if it has a spanning subgraph that is Laman (theorem 9.14). Jordán [ Jor16 ] states it in an equivalent form as his Theorem 2.2.2: a graph is generically minimally rigid in the plane if and only if it is Laman.
We first specialize the edge count of section 6 to the plane, and then prove the two directions in turn. That every Laman graph is generically rigid in the plane is proved by induction on the number of vertices, with the Henneberg moves of section 5 and the fact that they preserve rigidity (section 7). For the converse we study the rows of the rigidity map of a generically rigid graph \(G\) at a suitable framework. Some \(2|V| - 3\) edges of \(G\) have linearly independent rows. A bound on the rank of the rigidity map, which comes from the trivial motions of section 8, shows that these edges form a Laman graph. The last subsection combines the two directions.
Throughout, \(G\) is a graph on a set \(V\), which is finite where a statement says so. Frameworks, the rigidity map \(R(G, p)\), and infinitesimal and generic rigidity are as in section 6. As there, we write \(uv\) for the edge with endpoints \(u\) and \(v\).
9.1 The edge count in the plane
In the plane, the edge-count bound (theorem 6.18) says that a generically rigid graph on \(V\) has at least \(2|V| - 3\) edges, as many as a Laman graph on \(V\).
Let \(V\) be finite, and let \(G\) be generically rigid in dimension \(2\). Then
Specialize theorem 6.18 to \(d = 2\), where \(d(d+1)/2 = 3\).
9.2 The \(\Leftarrow \) direction
The sufficiency half of Laman’s theorem [ Lam70 ] says that every Laman graph is generically rigid in the plane. We prove it by induction on the number of vertices, along the reverse decomposition of section 5.4. The step for each Henneberg move needs an injective framework (section 7), so the induction proves the stronger statement for injective generic rigidity.
Let \(V\) be finite, and let \(G\) be a Laman graph on \(V\). Then \(G\) is generically rigid in dimension \(2\).
We show by strong induction on \(|V|\) that \(G\) is injectively generically rigid in dimension \(2\) (definition 6.8). An injectively generically rigid graph is generically rigid.
Since \(|E(G)| + 3 = 2|V|\), the set \(V\) has at least two elements. If \(|V| = 2\), then \(G\) is the complete graph on \(V\) (lemma 4.4), which is isomorphic to \(K_2\). The graph \(K_2\) is injectively generically rigid in dimension \(2\) (theorem 6.20). This property passes along isomorphisms (lemma 6.16), so \(G\) has it too.
Let \(|V| \ge 3\). The reverse decomposition (theorem 5.12) gives a vertex \(v\) of \(G\) of degree two or three. Suppose first that \(v\) has degree two, with neighbours \(a\) and \(b\), and that \(G - v\) is Laman. The graph \(G - v\) has \(|V| - 1\) vertices, so by induction it is injectively generically rigid. Hence so is the graph obtained from \(G - v\) by the Type I move at \(a\) and \(b\) (theorem 7.2). This graph is isomorphic to \(G\), by the map that sends its new vertex to \(v\) and fixes every other vertex (section 5.4). So \(G\) is injectively generically rigid (lemma 6.16).
Otherwise \(v\) has degree three, with neighbours \(a\), \(b\) and \(c\), where \(a\) and \(b\) are not adjacent, and \(G - v + ab\) is Laman. By induction, \(G - v + ab\) is injectively generically rigid. Hence so is the graph obtained from it by the Type II move on \(ab\) and \(c\) (theorem 7.5). This move deletes the edge \(ab\) again, and the graph it gives is isomorphic to \(G\) in the same way. So \(G\) is injectively generically rigid, as before.
9.3 The \(\Rightarrow \) direction
We now prove that every graph that is generically rigid in the plane contains a Laman spanning subgraph. This is the necessity half of Laman’s theorem [ Lam70 ] . We find the edges of the subgraph among the rows of the rigidity map. Let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{2}\). A set \(I\) of edges is row-independent at \(p\) when the rows of \(R(G, p)\) at the edges of \(I\) are linearly independent (definition 9.3). We prove two facts about such sets.
First, if no three of the points \(p_v\) are collinear, then the edges of every row-independent set form a \((2,3)\)-sparse graph (lemma 9.12). The necessity of this count for minimal rigidity goes back to Maxwell [ Max64 ] . Whiteley [ Whi96 ] proves the count in every dimension as his \(d\)-Counting Lemma 11.1.3, and Jordán [ Jor16 ] as his Lemma 1.3.1.
Second, if \(p\) is infinitesimally rigid for \(G\), then \(R(G, p)\) has rank at least \(2|V| - 3\). So some \(2|V| - 3\) edges are row-independent at \(p\) (see the proof of lemma 9.9). Infinitesimal rigidity is an open condition (lemma 6.17). So an infinitesimally rigid framework can be moved slightly to one that is still infinitesimally rigid and has no three points collinear (lemma 9.11). There the \(2|V| - 3\) row-independent edges form a \((2,3)\)-sparse graph with \(2|V| - 3\) edges, which is a Laman graph (theorem 9.13).
Jordán (p. 39) calls the row-independent edge sets of a framework the independent sets of its rigidity matroid. For a generic framework in the plane, Pollaczek-Geiringer and Laman characterized them: an edge set is row-independent if and only if it forms a \((2,3)\)-sparse graph (Jordán, Theorem 2.2.1, which he credits to Laman; Pollaczek-Geiringer proves the harder half in §8, p. 70). The first fact above is one half of this characterization, and Laman’s theorem needs only this half. We prove the converse in section 10, where the two halves identify the rigidity matroid in the plane with the \((2,3)\)-count matroid.
Row-independent edge sets
Let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\). The row of \(R(G, p)\) at an edge \(e = uv\) is the linear functional \(p' \mapsto R(G, p)(p')(e) = \langle p_u - p_v,\, p'_u - p'_v \rangle \) on \(({\mathbb {R}}^{d})^{V}\). In the standard bases it is the row of Jordán’s rigidity matrix indexed by \(e\).
Let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\), and let \(I \subseteq E(G)\). We say that \(I\) is row-independent at \(p\) if the linear functionals \(p' \mapsto R(G, p)(p')(e)\) on \(({\mathbb {R}}^{d})^{V}\), for \(e \in I\), are linearly independent.
The rows of the rigidity map
To find a large row-independent edge set, we use that the row rank of a matrix equals its column rank. For this we regard the rows of \(R(G, p)\) as elements of the dual space \((({\mathbb {R}}^{d})^{V})^{*}\) of linear functionals on \(({\mathbb {R}}^{d})^{V}\). The transpose of \(R(G, p)\) is the linear map \(R(G, p)^{\top }\) from the dual space of \({\mathbb {R}}^{E(G)}\) to \((({\mathbb {R}}^{d})^{V})^{*}\) that sends a functional \(\varphi \) to \(\varphi \circ R(G, p)\). In the standard bases its matrix is the transpose of the rigidity matrix. When \(V\) is finite, \(R(G, p)^{\top }\) has the same rank as \(R(G, p)\).
Let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\), and let \(e\) be an edge of \(G\). The rigidity row of \(G\) at \(p\) indexed by \(e\) is the linear functional \(r_e \in (({\mathbb {R}}^{d})^{V})^{*}\) given by \(r_e(p') = R(G, p)(p')(e)\).
Let \(G\) have finitely many edges, and let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\). Then the rigidity rows \(r_e\), for \(e \in E(G)\), span the image of \(R(G, p)^{\top }\).
For an edge \(e\), let \(e^{*}\) be the coordinate functional of \({\mathbb {R}}^{E(G)}\) at \(e\). Then \(r_e = e^{*} \circ R(G, p) = R(G, p)^{\top }(e^{*})\). Since \(E(G)\) is finite, the functionals \(e^{*}\) form a basis of the dual space of \({\mathbb {R}}^{E(G)}\). So their images under \(R(G, p)^{\top }\) span its image.
Let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\), and let \(I \subseteq E(G)\). Then \(I\) is row-independent at \(p\) if and only if the rigidity rows \(r_e\), for \(e \in I\), are linearly independent in \((({\mathbb {R}}^{d})^{V})^{*}\).
The rigidity row \(r_e\) is the functional of definition 9.3 at the edge \(e\). So both sides say that the same family of linear functionals is linearly independent.
The formal definition of row-independence regards the rows as elements of the space of all real functions on \(({\mathbb {R}}^{d})^{V}\). The rigidity rows are elements of its linear subspace \((({\mathbb {R}}^{d})^{V})^{*}\), in which the transpose of \(R(G, p)\) takes its values. The lemma passes between the two: a family of vectors of a subspace is linearly independent in the subspace exactly when it is linearly independent in the whole space.
A lower bound on the rank
The proof of the edge-count bound (theorem 6.18) first bounds the rank of the rigidity map from below, and then bounds the rank by the number of edges. We record the first step.
Let \(V\) be finite, and let \(G\) be generically rigid in dimension \(d\). Then there is a framework \(p\) on \(V\) in \({\mathbb {R}}^{d}\) with
Let \(p\) be a framework that is infinitesimally rigid for \(G\). By rank–nullity, \(\dim ({\mathbb {R}}^{d})^{V}\) is the rank of \(R(G, p)\) plus the dimension of its kernel. Here \(\dim ({\mathbb {R}}^{d})^{V} = d\, |V|\) (lemma 6.2). The kernel has dimension at most \(d(d+1)/2\), since \(p\) is infinitesimally rigid (definition 6.5).
Let \(V\) be finite, and let \(G\) be generically rigid in dimension \(2\). Then there are a framework \(p\) on \(V\) in \({\mathbb {R}}^{2}\) and an edge set \(I \subseteq E(G)\) with \(|I| = \max (2|V| - 3,\, 0)\) that is row-independent at \(p\).
Let \(p\) be a framework given by lemma 9.8 at \(d = 2\), so that \(R(G, p)\) has rank at least \(2|V| - 3\). The rigidity rows span the image of \(R(G, p)^{\top }\) (lemma 9.5). This image has the same dimension as the image of \(R(G, p)\), since the transpose has the same rank. So there is a set \(B\) of edges whose rigidity rows are linearly independent and span the image of \(R(G, p)^{\top }\), and \(|B| \ge 2|V| - 3\).
Let \(I\) be a subset of \(B\) with \(\max (2|V| - 3,\, 0)\) elements. The rigidity rows \(r_e\), for \(e \in I\), are linearly independent. So \(I\) is row-independent at \(p\) (lemma 9.6).
An upper bound on the rank
When the points \(p_v\) affinely span \({\mathbb {R}}^{d}\), the kernel of \(R(G, p)\) contains the space \(T(p)\) of trivial motions, of dimension at least \(d(d+1)/2\) (lemma 8.13). By rank–nullity this bounds the rank from above. Jordán proves the same bound for every framework on at least \(d + 2\) vertices, as his Lemma 1.2.1 [ Jor16 ] . In the plane the bound gives the sparsity of row-independent edge sets (lemma 9.12).
Let \(V\) be finite, and let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\) whose points affinely span \({\mathbb {R}}^{d}\). Then
By rank–nullity, the rank of \(R(G, p)\) plus the dimension of its kernel is \(\dim ({\mathbb {R}}^{d})^{V}\), which is \(d\, |V|\) (lemma 6.2). The kernel has dimension at least \(d(d+1)/2\) (lemma 8.13).
A perturbation lemma
The following lemma gives the framework that the beginning of this subsection asks for, one that is still infinitesimally rigid and has no three points collinear. We state it in any dimension \(d\) and for any property that holds at all frameworks near a given one, since section 10 applies it also to row-independence (lemma 10.6).
Let \(V\) be finite, let \(d \in {\mathbb {N}}\), and let \(P\) be a property of frameworks on \(V\) in \({\mathbb {R}}^{d}\) that holds at every framework in some neighbourhood of a framework \(p_0\). Then there is a framework \(p\) on \(V\) in \({\mathbb {R}}^{d}\) with property \(P\) such that, for every set \(S\) of at least \(d + 1\) vertices, the points \(p_v\), \(v \in S\), affinely span \({\mathbb {R}}^{d}\).
Choose an injective map \(\varphi : V \to {\mathbb {R}}\), for instance a numbering of the vertices by \(0, 1, \dots , |V| - 1\). Let \(w \in ({\mathbb {R}}^{d})^{V}\) place each vertex \(v\) on the moment curve, at \(w_v = (\varphi (v), \varphi (v)^{2}, \dots , \varphi (v)^{d})\). For \(t \in {\mathbb {R}}\), let \(p(t) = p_0 + t\, w\) be the framework that places \(v\) at \(p(t)_v = (p_0)_v + t\, w_v\). The map \(t \mapsto p(t)\) is continuous and \(p(0) = p_0\), so there is an \(\varepsilon {\gt} 0\) such that \(p(t)\) has property \(P\) whenever \(|t| {\lt} \varepsilon \).
Let \(v_0, \dots , v_d\) be distinct vertices. The points \(p(t)_{v_0}, \dots , p(t)_{v_d}\) are affinely independent if and only if the \(d \times d\) matrix with rows \(p(t)_{v_i} - p(t)_{v_0}\), for \(1 \le i \le d\), has nonzero determinant. This determinant is a polynomial \(f(t)\) in \(t\) of degree at most \(d\). Its coefficient of \(t^{d}\) is the determinant of the matrix with rows \(w_{v_i} - w_{v_0}\), whose entry in row \(i\) and column \(j\) is \(\varphi (v_i)^{j} - \varphi (v_0)^{j}\). Subtract the first row of the Vandermonde matrix of \(\varphi (v_0), \dots , \varphi (v_d)\) from the other rows, and expand along the first column. This shows that the coefficient of \(t^{d}\) is the Vandermonde determinant
which is nonzero because \(\varphi \) is injective. So \(f\) is a nonzero polynomial, and it has finitely many roots.
There are finitely many tuples \((v_0, \dots , v_d)\) of distinct vertices, so only finitely many \(t\) are roots of one of their polynomials. The interval \((0, \varepsilon )\) is infinite, so we can choose \(t\) in it that is a root of none of them. Let \(p = p(t)\). Then \(p\) has property \(P\). Let \(S\) be a set of at least \(d + 1\) vertices, and let \(v_0, \dots , v_d\) be distinct elements of \(S\). The points \(p_{v_0}, \dots , p_{v_d}\) are affinely independent, so they affinely span \({\mathbb {R}}^{d}\), and hence so do the points \(p_v\), \(v \in S\).
Sparsity from row-independence
We now prove the first of the two facts stated at the beginning of this subsection. Jordán derives his Lemma 1.3.1 from his rank bound, Lemma 1.2.1, and we argue in the same way: we apply the rank upper bound (lemma 9.10) to the subgraph induced on each set of vertices. That bound needs the points of the framework to affinely span the plane, which is why we assume that no three of them are collinear.
Let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{2}\) such that no three of the points \(p_v\) are collinear, that is, for every set \(S\) of at least three vertices the points \(p_v\), \(v \in S\), affinely span \({\mathbb {R}}^{2}\). Let \(I \subseteq E(G)\) be row-independent at \(p\). Then the spanning subgraph of \(G\) with edge set \(I\) is \((2, 3)\)-sparse.
Let \(H\) be the spanning subgraph of \(G\) with edge set \(I\). By definition 3.1, we must show that \(|E_{H}[S]| + 3 \le 2|S|\) for every set \(S\) of at least two vertices. If \(|S| = 2\), then \(S\) spans at most one edge, and \(1 + 3 \le 4\).
Let \(|S| \ge 3\). Let \(H[S]\) be the subgraph of \(H\) induced on \(S\), whose edges are the edges in \(E_{H}[S]\), and let \(p|_S\) be the framework on \(S\) that places each \(v \in S\) at \(p_v\). For an edge \(e\) of \(H[S]\), let \(r_e\) be the rigidity row of \(G\) at \(p\) indexed by \(e\), and let \(r'_e\) be the rigidity row of \(H[S]\) at \(p|_S\) indexed by \(e\) (definition 9.4). Let \(\rho : ({\mathbb {R}}^{2})^{V} \to ({\mathbb {R}}^{2})^{S}\) be the restriction \(x \mapsto x|_S\). If \(e = uv\), then \(u, v \in S\), and both \(r_e(x)\) and \(r'_e(\rho (x))\) equal \(\langle p_u - p_v,\, x_u - x_v \rangle \). So \(r_e = r'_e \circ \rho \).
The rows \(r_e\), for \(e \in E_{H}[S]\), are linearly independent, since \(E_{H}[S] \subseteq I\) and \(I\) is row-independent at \(p\) (lemma 9.6). Suppose that \(\sum _e c_e r'_e = 0\). Composing with \(\rho \) gives \(\sum _e c_e r_e = 0\), so every \(c_e\) is zero. Hence the rows \(r'_e\) are linearly independent. They span the image of \(R(H[S], p|_S)^{\top }\) (lemma 9.5), which has the same dimension as the image of \(R(H[S], p|_S)\). So their number is the rank of \(R(H[S], p|_S)\):
By hypothesis the points \(p_v\), \(v \in S\), affinely span \({\mathbb {R}}^{2}\). So this rank is at most \(2|S| - 3\) (lemma 9.10 at \(d = 2\)), and \(|E_{H}[S]| + 3 \le 2|S|\).
The Laman subgraph
We now combine the two facts with the perturbation lemma.
Let \(V\) be finite with \(|V| \ge 2\), and let \(G\) be generically rigid in dimension \(2\). Then \(G\) has a spanning subgraph that is Laman.
Since \(G\) is generically rigid, some framework \(p_0\) on \(V\) in \({\mathbb {R}}^{2}\) is infinitesimally rigid for \(G\) (definition 6.7). Every framework in some neighbourhood of \(p_0\) is infinitesimally rigid for \(G\) too (lemma 6.17). So there is a framework \(p\) that is infinitesimally rigid for \(G\) and has no three of its points collinear (lemma 9.11 at \(d = 2\)).
By rank–nullity, as in the proof of lemma 9.8, the rank of \(R(G, p)\) is at least \(2|V| - 3\). As in the proof of lemma 9.9, it follows that some set \(I\) of \(2|V| - 3\) edges of \(G\) is row-independent at \(p\); this number is positive, since \(|V| \ge 2\). Let \(H\) be the spanning subgraph of \(G\) with edge set \(I\). Then \(H\) is \((2, 3)\)-sparse (lemma 9.12), and \(|E(H)| + 3 = 2|V|\). So \(H\) is Laman (definition 4.1).
9.4 Laman’s theorem
The two directions combine into Laman’s theorem.
Let \(V\) be finite with \(|V| \ge 2\), and let \(G\) be a graph on \(V\). Then \(G\) is generically rigid in dimension \(2\) if and only if it has a spanning subgraph that is Laman.
If \(G\) is generically rigid in dimension \(2\), then it has a spanning subgraph that is Laman (theorem 9.13). Conversely, let \(H\) be a spanning subgraph of \(G\) that is Laman. Then \(H\) is generically rigid in dimension \(2\) (theorem 9.2). Since \(E(H) \subseteq E(G)\), so is \(G\) (lemma 6.12).