Dependencies

Let \((G,p)\) be a body-hinge framework, let \(u \neq v\) be bodies, and let \(V_1, V_2\) be sets of bodies with \(V_1 \cap V_2 = \{ u, v\} \) such that every edge of \(G\) lies inside \(V_1\) or inside \(V_2\). Let \(\rho _i = \rho _{uv}(G[V_i], p)\). Then the row spaces of \(R(G[V_1],p)\) and \(R(G[V_2],p)\) meet in the span of the joint rows at \(u, v\) confining the relative screw to \(\rho _1 + \rho _2\), and

Let \(G\) be a finite multigraph, and let \(q\) be an endpoint assignment of \(G\) that is generic for row independence. Then the endpoint realization of \(q\) is independent if and only if \(G\) is \((D, D)\)-sparse. It is isostatic, that is, independent and infinitesimally rigid, if and only if \(G\) is \((D, D)\)-tight.

Let \(d \ge 2\), let \(K\) be an infinite field, and let \(G = (V, E)\) be a multigraph, with parallel edges and loops allowed, with \(V\) finite and nonempty. Then \((G, q)\) is infinitesimally rigid at every hinge-point assignment \(q\) of \(G\) that is generic in the sense of definition 19.16 if and only if \(\operatorname {def}(\tilde G) = 0\). The same holds with the assignments that are generic for row independence (definition 28.27) in place of these.

Let \(d \ge 2\), let \(K\) be an infinite field, and let \(G = (V, E)\) be a multigraph, with parallel edges and loops allowed, with \(V\) finite and nonempty. Then \((G, q)\) is infinitesimally rigid at every hinge-point assignment \(q\) of \(G\) that is generic in the sense of definition 19.16 if and only if \(\tilde G = (D-1) \cdot G\) contains \(D\) edge-disjoint spanning trees. The same holds with the assignments that are generic for row independence (definition 28.27) in place of these.

Let \(d \ge 2\), let \(K\) be an infinite field, and let \(G = (V, E)\) be a multigraph, with parallel edges and loops allowed, with \(V\) finite and nonempty. Let \(q\) be a hinge-point assignment of \(G\) that is generic in the sense of definition 19.16. Then \(\operatorname {rank} R(G,q) = D(|V|-1) - \operatorname {def}(\tilde G)\). So \((G,q)\) has \(\operatorname {def}(\tilde G)\) degrees of freedom.

Let \(D \ge 2\), and let \(G\) be a multigraph with a vertex \(v\) of degree two, whose edges join \(v\) to distinct vertices \(a, b \neq v\). Then

Let \(H\) be a graph on \(V\) with \(E(H)\) independent in \(\mathcal{R}_3(V)\). Then \(H\) is Laman.

Let \(V\) be finite, and let \(G\) be a Laman graph on \(V\). Then there is a framework \(p\) on \(V\) in \({\mathbb {R}}^{2}\) at which \(E(G)\) is row-independent.

Let \(G\) be a connected \((k, k)\)-tight multigraph. Then \(E(G)\) is the union of \(k\) pairwise disjoint spanning trees of \(G\).

Let \(G\) be a simple graph of minimum degree at least two on a finite, nonempty vertex set \(V\), and suppose that \(\operatorname {def}(\tilde G) = 0\), where \(\tilde G = 5 \cdot G\). Then every placement \(p\) of \(V\) in \({\mathbb {R}}^3\) that is generic for row independence is infinitesimally rigid for \(G^2\).

Let \(G\) be a simple graph on a finite, nonempty vertex set \(V\), and suppose that \(5 \cdot G\) contains six edge-disjoint spanning trees. Then every placement of \(V\) in \({\mathbb {R}}^3\) that is generic for row independence is infinitesimally rigid for \(G^2\).

Let \(G\) be a simple graph of minimum degree at least two on a finite, nonempty vertex set \(V\). Then

where \(r\) is the rank function of the generic rigidity matroid \(\mathcal{R}_3(V)\) (definition 24.7), and \(\operatorname {def}(\tilde G)\) is the deficiency of definition 20.3 at \(D = 6\), with \(\tilde G = 5 \cdot G\).

Let \(d \ge 2\), let \(K\) be an infinite field, and let \(G = (V, E)\) be a simple graph with \(V\) finite and nonempty. Then \((G, q)\) is infinitesimally rigid at every normal assignment \(q\) of \(G\) that is generic for row independence if and only if \(\operatorname {def}(\tilde G) = 0\).

Let \(V\) be a finite set, let \(k\) and \(\ell \) be non-negative integers with \(\ell {\lt} 2k\), and let \(G\) be a simple graph on \(V\). Then \(E(G)\) is independent in the \((k, \ell )\)-count matroid on \(V\) (definition 11.7) if and only if the verdict that the formal pebble game on \(G\) returns accepts \(G\).

Let \(G\) be connected and let \(q\) be admissible. The flat configuration \((q, 0)\) has rank \(6(|V(G)| - 1) - \operatorname {def}_3(G)\) if and only if \(\dim L(q) = 3 + \operatorname {def}_3(G)\), and this holds if and only if equality holds in lemma 30.34 at \(q\) and \(\operatorname {def}_2(G) = \operatorname {def}_3(G)\). If \(\dim L(q) \le 3 + \operatorname {def}_3(G)\), then the general configuration of \(G\) attains.

Let \(G\) be connected, and suppose that \(\dim L(q) = 3\) at some admissible picture \(q\), so that \(\ell _0 = 3\) (lemma 30.3). Then \(\operatorname {def}_2(G) = \operatorname {def}_3(G) = 0\), and the general configuration of \(G\) attains.

Let \(K\) be infinite and let \(G\) be connected and simple, with at least three members in every closed neighbourhood. If \(\operatorname {def}_2(G) = \operatorname {def}_3(G)\), then the general configuration of \(G\) attains (definition 30.8).

Let \(K\) be infinite and let \(G\) satisfy the standing hypotheses and be \(2\)-edge-connected. Let \(W \subsetneq V(G)\) with \(|W| \ge 2\) and \(\operatorname {def}_2(G[W]) = 0\), such that no body outside \(W\) is adjacent to two bodies of \(W\), and let \(G/H\) be the contraction of \(H = G[W]\) to a body of \(W\). If the general configuration of \(G/H\) attains, then the general configuration of \(G\) attains.

Let \(d = 3\), so that \(D = 6\), let \(K\) be an infinite field, and let \(G = (V, E)\) be a multigraph, possibly with loops, with \(V \neq \emptyset \). Then \(G\) has a hinge-coplanar panel realization at the target rank \(6(|V| - 1) - \operatorname {def}(\tilde G)\) (definition 23.21).

Let \(d = 3\), so that \(D = 6\), let \(K\) be an infinite field, and let \(G = (V, E)\) be a simple minimal \(0\)-dof-graph with \(|V| \ge 2\) that spans the set of bodies. Then \(G\) has a panel-hinge realization \((G,p)\) with nonparallel panels (definition 23.10), a nondegenerate hinge at every edge of \(G\), and

(definition 23.21).

Let \(H\) be a graph on \(V\) and let \(v\) be a vertex of \(H\) whose neighborhood \(N_H(v)\) is a clique of \(H\). Then

Let \(H\) be a graph on \(V\) and let \(v\) be a vertex of \(H\) with \(d_H(v) \le 3\). Then

and \(E(H)\) is independent in \(\mathcal{R}_3(V)\) if and only if \(E(H - E_H(v))\) is.

Let \(p_1, \dots , p_k \in K^d\). The extensor of \(p_1, \dots , p_k\) is

If \(p_1, \dots , p_k\) are affinely independent and span the affine subspace \(U\), we also write \(C(U)\) for \(C(p_1, \dots , p_k)\) and call it a \(k\)-extensor supporting \(U\).

Let \(D\) be a partial orientation on \(V\), and let \(u \ne v\) be vertices with \((v, u) \notin D\). Inserting the arc \((u, v)\) replaces \(D\) by the partial orientation \(D \cup \{ (u, v)\} \). Its underlying edge set is \(\underline{D} \cup \{ uv\} \).

Let \(G\) be a simple graph on \(V\), and let \(k\) and \(\ell \) be non-negative integers. A blocking witness for \(G\) is a finite set \(V' \subseteq V\) with \(\ell \le k|V'|\) that spans more than \(k|V'| - \ell \) edges of \(G\), that is, \(|E_{G}[V']| + \ell {\gt} k|V'|\).

Let \(d\) be a natural number and let \(D = \binom {d+1}{2}\). A body-bar framework in \({\mathbb {R}}^d\) on a multigraph \(G\) is a pair \((G, b)\), where \(b\) assigns a vector \(b_e \in {\mathbb {R}}^D\) to each bar \(e\) of \(G\).

Let \(D = \binom {d+1}{2}\), and let \(G\) be a multigraph. A body-hinge framework in \({\mathbb {R}}^d\) on \(G\) assigns to each edge \(e\) of \(G\) a \((d-2)\)-dimensional affine subspace of \({\mathbb {R}}^d\), the hinge of \(e\), and to the \(D - 1\) copies of \(e\) in \((D-1)\cdot G\) a basis of the space spanned by the Plücker vectors of the lines that meet the hinge. Its rigidity map is that of the body-bar framework on \((D-1)\cdot G\) with these vectors (definition 16.22). It is independent, or infinitesimally rigid, if this body-bar framework is.

Let \(G\) be a multigraph with normals \(q\), let \(e_c\) and \(e_r\) be edge labels, and let \(n_1, n', n_2 \in K^{d+1}\). For \(t \in K\), let \(F_t\) be the body-hinge framework on \(G\) (definition 19.3) whose supporting extensor is \(C(n_1 + t\, n', n_2)\) at \(e_r\), is \(C(n_1, n')\) at \(e_c\) if \(e_c \neq e_r\) (definition 23.1), and at every other edge label is its extensor in the panel-hinge framework \((G, q)\) (definition 23.5). For a vertex \(v\) of \(G\) whose edges \(va\) and \(vb\) join it to vertices \(a\) and \(b\), we write \((G, p_1)\) for \(F_0\) with \(e_c = va\), \(e_r = vb\), \(n_1 = q(a)\) and \(n_2 = q(b)\).

Let \(G\) be a multigraph, and let \(d \ge 1\). A chain of length \(d\) in \(G\), written \(v_0 v_1 \dots v_d\), consists of distinct vertices \(v_0, \dots , v_d\) of \(G\) and, for \(0 \le i \le d - 1\), an edge \(f_i\) of \(G\) joining \(v_i\) and \(v_{i+1}\), such that for \(1 \le i \le d - 1\) the only edges of \(G\) at the interior vertex \(v_i\) are \(f_{i-1}\) and \(f_i\).

Let \(G = (V, E)\) be a multigraph. A hinge-coplanar panel realization of \(G\) is a body-hinge framework \((G,p)\) (definition 19.3) together with a nonzero normal \(n_v \in K^{d+1}\) for each body \(v\), such that the hinge \(C(p(e))\) at each edge \(e\) with ends \(u\) and \(v\) is nonzero and lies in the panels with normals \(n_u\) and \(n_v\) (definition 23.24).

Let \(V\) be finite, and let \(k\) and \(\ell \) be non-negative integers with \(\ell {\lt} 2k\). The \((k, \ell )\)-count matroid on \(V\) is the matroid on \(E(K_V)\) whose independent sets are the sets \(I \subseteq E(K_V)\) for which the graph on \(V\) with edge set \(I\) is \((k, \ell )\)-sparse.

Let \(G\) be a multigraph, let \(P\) be a partition of \(V(G)\), and let \(Q \subseteq P\). We write \(e_G(Q)\) for the number of edges of \(G\) that join distinct members of \(Q\).

Let \(G\) be a multigraph. For a set \(V'\) of vertices of \(G\), let \(\delta _G(V')\) be the set of edges of \(G\) that join \(V'\) to \(V(G) \setminus V'\), and let \(d_G(V') = |\delta _G(V')|\). Then \(G\) is \(2\)-edge-connected if \(d_G(V') \ge 2\) for every set \(V'\) with \(\emptyset \neq V' \neq V(G)\).

Let \(G\) be a multigraph, and let \(m \ge 3\). Then \(G\) is a cycle on \(m\) vertices, or a cycle graph, if it has distinct vertices \(v_0, \dots , v_{m-1}\) and, for \(0 \le i \le m - 1\), an edge \(f_i\) joining \(v_i\) and \(v_{i+1}\), with indices modulo \(m\), such that every vertex and every edge of \(G\) is among them.

Let \(G\) be a multigraph. For a partition \(P\) of \(V(G)\) into nonempty parts, let \(d_G(P)\) be the number of edges of \(G\) that join different parts of \(P\). The \(D\)-deficiency of \(P\) is

and the deficiency \(\operatorname {def}(\tilde G)\) is the largest value of \(\operatorname {def}_{\tilde G}(P)\) over the partitions \(P\) of \(V(G)\).

Let \(G\) be a multigraph, and let \(u\) and \(v\) be vertices of \(G\). The merged deficiency of \(\tilde G\) at \(u\) and \(v\) is

the maximum over the partitions \(P\) of \(V(G)\) that have \(u\) and \(v\) in one part.

Let \(R\) be a relation on a set \(V\), whose elements we call vertices. A directed \(R\)-walk from \(u\) to \(w\) is a sequence \(u = v_0, v_1, \ldots , v_m = w\) of vertices, with \(m \ge 0\), such that \((v_{i-1}, v_i) \in R\) for \(1 \le i \le m\). Its length is \(m\). The walk is simple if \(v_0, \ldots , v_m\) are distinct.

Let \((G,p)\) be a body-hinge framework. The degree of freedom of \((G,p)\) is \(D(|V|-1) - \operatorname {rank} R(G,p)\). The framework \((G,p)\) is generic if \(R(G,p)\) and each of its edge-induced submatrices (the rows of the edges of a subset of \(E\)) have the largest rank over all realizations of \(G\).

Let \(G\) be a multigraph and let \(m\) be a natural number. The multigraph \(m \cdot G\) has the vertices of \(G\), and for each edge \(e\) of \(G\) it has \(m\) edges \((e, 1), \dots , (e, m)\), each with the ends of \(e\).

Let \(V\) be a set with a linear order, and let \(G\) be a simple graph on \(V\) with finitely many edges. The sorted edge list of \(G\) is the list of the pairs \((\min e, \max e)\), for the edges \(e\) of \(G\), in lexicographic order. Here \(\min e\) and \(\max e\) are the smaller and the larger end of \(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.

For \(S \subseteq V\), let

be the set of edges of \(G\) with both endpoints in \(S\), that is, the edge set of the subgraph of \(G\) induced on \(S\). We say that \(S\) spans these edges.

Let \(1 \le i, j \le d\). The elementary skew-symmetric map \(E_{ij} - E_{ji}\) is the linear map of \({\mathbb {R}}^{d}\) that sends \(y\) to \(y_j e_i - y_i e_j\).

Let \(v_1, \dots , v_j \in K^{d+1}\). The extensor of the family \((v_1, \dots , v_j)\) is the product \(v_1 \wedge \cdots \wedge v_j\) in \(\bigwedge K^{d+1}\). A \(j\)-extensor is an element of \(\bigwedge K^{d+1}\) of this form.

A screw element \(C \in \bigwedge ^{k} K^{k+2}\) passes through the homogeneous point \(q \in K^{k+2}\) when \(C\) is the extensor of \(k\) points \(p_1, \dots , p_k \in K^{k+2}\) whose span contains \(q\).

A framework on \(V\) in \({\mathbb {R}}^{d}\) is a map \(p : V \to {\mathbb {R}}^{d}\), which places each vertex \(v\) at the point \(p_v\). The frameworks on \(V\) in \({\mathbb {R}}^{d}\) form the real vector space \(({\mathbb {R}}^{d})^{V}\).

Let \((G,p)\) be a body-hinge framework, and let \(G'\) be a multigraph on the same set of bodies. The framework \((G',p)\) has the multigraph \(G'\) and the hinge \(p(e)\) at each edge \(e\) of \(G'\). If \(G'\) is a subgraph of \(G\), then \((G',p)\) is the restriction of \((G,p)\) to \(G'\). The same operation on a panel-hinge framework, for a subgraph \(G'\) of \(G\), replaces its multigraph by \(G'\) and keeps its normals and the hinge at each edge of \(G'\).

Let \((G, n)\) be a panel-hinge framework, let \(v\) be a body, and let \(m \in K^{d+1}\). Replacing the normal of \(v\) by \(m\) gives the panel-hinge framework \((G, n')\) with \(n'_v = m\) and \(n'_w = n_w\) for every body \(w \neq v\).

Let \(P\) be a partition of \(V\), and let \(A\) be a part of \(P\). We write \(d_G(A)\) for the number of edges \(xy\) of \(G\) with \(x \in A\) and \(y \notin A\), that is, with exactly one endpoint in \(A\). The ordered pairs \((x, y)\) with \(x \in A\), \(y \notin A\) and \(xy \in E(G)\) are the pairs leaving \(A\).

A placement \(p \colon V \to {\mathbb {R}}^3\) (definition 6.1) is in general position up to order four if, for every set \(S \subseteq V\) of at most four vertices, the points \(p(v)\) with \(v \in S\) are affinely independent.

Let \(G\) be a multigraph, and fix an orientation of its bars (definition 16.22). An endpoint assignment \(q\) of \(G\) gives each bar \(e\) an ordered pair \((p_e, p'_e)\) of points of \({\mathbb {R}}^d\). Its endpoint realization is the body-bar framework \((G, b)\) in \({\mathbb {R}}^d\) with \(b_e = T(p_e, p'_e)\) for every bar \(e\). The assignment \(q\) is generic for row independence if every set of bars whose rows are linearly independent at the endpoint realization of some endpoint assignment has linearly independent rows at the endpoint realization of \(q\).

Let \(G = (V, E)\) be a multigraph. A hinge-point assignment \(q\) of \(G\) gives each edge \(e\) a family \(q_e\) of \(d - 1\) points \(q_{e,1}, \dots , q_{e,d-1}\) of \(K^d\). Its framework \((G, q)\) is the body-hinge framework whose hinge at \(e\) has the supporting extensor \(C(q_e) = C(q_{e,1}, \dots , q_{e,d-1})\) (definition 18.8). The annihilator-row family of \(q\) is the family of linear forms

on screw assignments \(S\), indexed by an edge \(e\) of \(G\), with ends \(u\) and \(v\) taken in a fixed order, and a pair \((t, t')\) of indices of the standard basis of \(\bigwedge ^{d-1}K^{d+1}\). Here \(y_t\) is the coordinate of \(y\) at the \(t\)-th basis vector. The assignment \(q\) is generic for row independence if every subfamily of the annihilator-row family that is linearly independent at some hinge-point assignment is linearly independent at \(q\).

Let \(G = (V, E)\) be a multigraph. A normal assignment \(q\) of \(G\) gives each body \(v\) a vector \(q_v \in K^{d+1}\), and \((G, q)\) is the panel-hinge framework with these normals. The annihilator-row family of \(q\) is the family of linear forms

on screw assignments \(S\), indexed by an edge \(e\) of \(G\), with ends \(u\) and \(v\), and a pair \((t, t')\) of indices of the standard basis of \(\bigwedge ^{d-1}K^{d+1}\). Here \(y_t\) is the coordinate of \(y\) at the \(t\)-th basis vector. The assignment \(q\) is generic for row independence, and \((G, q)\) has generic normals, if every subfamily of the annihilator-row family that is linearly independent at some normal assignment is linearly independent at \(q\).

Let \(p\) be a placement of \(V\) in \({\mathbb {R}}^{d}\). We say that \(p\) is generic for row independence if every set \(I \subseteq E(K_V)\) that is row-independent at some placement of \(V\) in \({\mathbb {R}}^{d}\) is row-independent at \(p\) (definition 9.3, at \(G = K_V\)).

Let \(H\) be a graph on \(V\). The generic rank \(r_d(H)\) of \(H\) in dimension \(d\) is the rank of \(E(H)\) in \(\mathcal{R}_d(V)\).

Fix a placement \(p\) of \(V\) in \({\mathbb {R}}^{d}\) that is generic for row independence (lemma 24.2). The generic rigidity matroid \(\mathcal{R}_d(V)\) is the linear rigidity matroid \(\mathcal{L}_p(V)\) at \(p\) (definition 10.16), a matroid on \(E(K_V)\).

Let \(G = (V, E)\) be a multigraph with \(V \neq \emptyset \). An extensor lies in the panel with normal \(n \in K^{d+1}\) if it is \(x_1 \vee \cdots \vee x_{d-1}\) for some \(x_1, \dots , x_{d-1} \in n^\perp \). A nondegenerate-hinge panel realization of \(G\) is a body-hinge framework \((G,p)\) at the target rank \(D(|V| - 1) - \operatorname {def}(\tilde G)\) (definition 23.21), together with a nonzero normal \(n_v \in K^{d+1}\) for each body \(v\), such that the hinge \(C(p(e))\) at each edge \(e\) with ends \(u\) and \(v\) is nonzero and lies in the panels with normals \(n_u\) and \(n_v\).

Let \(G\) be a multigraph, and let \(v\) be a vertex of \(G\) of degree two, whose two edges join \(v\) to vertices \(a\) and \(b\).

• The removal of \(v\) gives \(G_v = G - v\), obtained from \(G\) by deleting \(v\) and its two edges.

• The splitting off at \(v\) gives \(G_v^{ab}\), obtained from \(G\) by deleting \(v\) and its two edges and adding a new edge \(ab\).

Let \(H\) be a multigraph with an edge \(ab\). The edge-splitting along \(ab\) gives \(H_{ab}^v\), obtained from \(H\) by deleting \(ab\) and adding a new vertex \(v\) and two new edges \(va\) and \(vb\).

Let \(k\) and \(\ell \) be natural numbers. A multigraph \(G\) is \((k, \ell )\)-sparse if every non-empty set \(E'\) of bars of \(G\) satisfies \(|E'| \le k\, |V(E')| - \ell \). It is \((k, \ell )\)-tight if moreover \(|E(G)| = k\, |V(G)| - \ell \).

Let \(G = (V, E)\) be a multigraph, and let \(c \colon V \to {\mathbb {R}}^3\) assign a centre \(c(v)\) to each body \(v\). The molecular framework on \((G, c)\) is the body-hinge framework on \(G\) (definition 19.3) whose supporting extensor at an edge \(e\) with ends \(u\) and \(v\) is

(definition 18.8), where \(\bar c(v) = (c(v), 1)\).

A body-hinge framework \((G,p)\) in \(K^d\) is a multigraph \(G = (V,E)\) together with a map \(p\) that assigns to each edge \(e\) a \((d-2)\)-dimensional affine subspace \(p(e)\) of \(K^d\), the hinge of \(e\). Let \(C(p(e)) \in \bigwedge ^{d-1}K^{d+1}\) be a \((d-1)\)-extensor supporting \(p(e)\) (definition 18.8). A screw assignment is a map \(S\) from \(V\) to the screw space \(\bigwedge ^{d-1}K^{d+1}\). It satisfies the hinge constraint at an edge \(e\) with ends \(u\) and \(v\) if

A body-hinge framework is hinge-coplanar if some panel-hinge framework on its multigraph has, at every edge, the hinge of the framework.

Let \((G,p)\) be a body-hinge framework and let \(e\) be an edge of \(G\). Let \(r_1(p(e)), \dots , r_{D-1}(p(e))\) be a basis of the orthogonal complement of \(\operatorname {span} C(p(e))\) in \(K^D\), and let \(r(p(e))\) be the \((D-1) \times D\) matrix with these rows. Then a screw assignment \(S\) satisfies the hinge constraint at \(e\), with ends \(u\) and \(v\), if and only if

Let \(p \in K^d\). The homogeneous coordinate vector of \(p\) is the vector \(\bar p = (p, 1) \in K^{d+1}\), obtained by appending the coordinate \(1\).

A body-bar framework \((G, b)\) is independent if its rigidity map has rank \(|E(G)|\), that is, if the rows of its bars are linearly independent.

Let \(K\) be a field, let \(d \ge 1\), and let \(g\) be an invertible linear map of \(K^{d+1}\). The screw map of \(g\) is the linear automorphism \(\Lambda _g\) of the screw space \(\bigwedge ^{d-1} K^{d+1}\) (definition 19.1) with

Let \(G\) be a multigraph, let \(X\) be a set of edges of \(\tilde G\), and let \(V(X)\) be the set of vertices incident with an edge of \(X\). Then \(G[V(X)]\) is the subgraph of \(G\) induced by \(V(X)\). Its vertices are those of \(V(X)\), and its edges are the edges of \(G\) with both ends in \(V(X)\).

Let \(D = \binom {d+1}{2}\). A body-bar framework \((G, b)\) in \({\mathbb {R}}^d\) is infinitesimally rigid if its rigidity map has rank \(D|V(G)| - D\).

Let \(A\) be a linear map of \({\mathbb {R}}^{d}\), and let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\). We write \(A \circ p\) for the element of \(({\mathbb {R}}^{d})^{V}\) with \((A \circ p)_v = A p_v\) for every vertex \(v\). When \(A\) is skew-symmetric, \(A \circ p\) is an infinitesimal rotation at \(p\).

Let \(V\) be finite. The graph \(G\) is generically rigid in dimension \(d\) if some framework on \(V\) in \({\mathbb {R}}^{d}\) is infinitesimally rigid for \(G\).

Let \(V\) be finite. The graph \(G\) is injectively generically rigid in dimension \(d\) if some injective framework on \(V\) in \({\mathbb {R}}^{d}\) is infinitesimally rigid for \(G\).

Let \(V\) be finite, and let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\). We say that \(p\) is infinitesimally rigid for \(G\) if

Let \(V\) be finite. A graph \(G\) on \(V\) is Laman if it is \((2,3)\)-tight, that is, if it is \((2,3)\)-sparse and

Let \(V\) be a finite set with a linear order, and let \(G\) be a simple graph on \(V\). The decision procedure for the Laman property of \(G\) is the decision procedure for the \((2, 3)\)-tightness of \(G\) (definition 14.11), since \(3 {\lt} 2 \cdot 2\) and a graph is Laman if and only if it is \((2, 3)\)-tight (definition 4.1).

A graph \(H\) on \(V\) is Laman (in the three-dimensional counting sense of [ JJ08a , § 5 ] ) if for every \(X \subseteq V\) with \(|X| \ge 3\),

\(G\) is \((k,\ell )\)-sparse if every finite set \(s \subseteq V\) with \(\ell \le k\, |s|\) spans at most \(k\, |s| - \ell \) edges, that is,

Let \(V\) be a finite set with a linear order, let \(G\) be a simple graph on \(V\), and let \(k\) and \(\ell \) be non-negative integers with \(\ell {\lt} 2k\). The decision procedure for the \((k, \ell )\)-sparsity of \(G\) runs the computable pebble game on \(G\) (definition 14.5). If the verdict accepts \(G\), it returns a proof that \(G\) is \((k, \ell )\)-sparse, and otherwise a proof that \(G\) is not, both by theorem 14.7.

Let \(V\) be finite, let \(G\) be a graph on \(V\), and let \(X \subseteq V\). We write \(C_G(X)\) for the union of all sets that contain \(X\) and are \((k, \ell )\)-tight in \(G\). If there is no such set, then \(C_G(X)\) is empty.

Let \(V\) be finite. The graph \(G\) is \((k,\ell )\)-tight if it is \((k,\ell )\)-sparse and

Let \(V\), \(G\), \(k\) and \(\ell \) be as in definition 14.8. The decision procedure for the \((k, \ell )\)-tightness of \(G\) decides whether \(G\) is \((k, \ell )\)-sparse by definition 14.8, and whether \(|E(G)| + \ell = k|V|\) by computing both sides. It returns a proof that \(G\) is \((k, \ell )\)-tight if both hold, and otherwise a proof that \(G\) is not (definition 3.3).

A finite set \(s \subseteq V\) is \((k,\ell )\)-tight in \(G\) if it attains the sparsity bound:

Let \(A, B \in \bigwedge K^{d+1}\). The join of \(A\) and \(B\) is their product \(A \vee B = A \wedge B\) in \(\bigwedge K^{d+1}\).

Let \(G\) be a multigraph and let \(k\) be an integer. Then \(G\) is a \(k\)-dof-graph if \(\operatorname {def}(\tilde G) = k\). It is a minimal \(k\)-dof-graph if moreover, for every edge \(e\) of \(G\), every base of \(M(\tilde G)\) meets the set \(\tilde e\) of the \(D - 1\) copies of \(e\) in \(\tilde G\).

Let \(G\) be a multigraph and let \(k \ge 1\). Let \(R = {\mathbb {Q}}[X_{e,j}]\) be the polynomial ring over \({\mathbb {Q}}\) in one indeterminate \(X_{e,j}\) for each bar \(e\) and each \(j \in \{ 1, \dots , k\} \), and let \(K\) be its field of fractions. The \(k\)-frame row of a bar \(e\) is

where \(a_e\) is the signed incidence vector of \(e\). The \(k\)-frame matroid \(F(G, X)\) is the matroid on \(E(G)\) in which a set of bars is independent if and only if their \(k\)-frame rows are linearly independent over \(K\).

Let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\). The linear rigidity matroid \(\mathcal{L}_p(V)\) at \(p\) is the matroid on \(E(K_V)\) represented by the extended rigidity rows at \(p\): a set \(I \subseteq E(K_V)\) is independent if the functionals \(\tilde r_e\), for \(e \in I\), are linearly independent.

Let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\), and let \(r_e\), for \(e \in E(K_V)\), be the rigidity rows of \(K_V\) at \(p\) (definition 9.4). The extended rigidity rows at \(p\) are the functionals \(\tilde r_e \in (({\mathbb {R}}^{d})^{V})^{*}\), for unordered pairs \(e\) of elements of \(V\), given by \(\tilde r_e = r_e\) if \(e \in E(K_V)\) and \(\tilde r_e = 0\) if \(e = \{ v, v\} \) for some \(v \in V\).

Let \(G\) be a multigraph. The matroid \(M(\tilde G)\) is the union of \(D\) copies of the cycle matroid of \(\tilde G\) (definition 15.6). A set \(F\) of edges of \(\tilde G\) is independent in \(M(\tilde G)\) if and only if \(\tilde G \restriction F\) is \((D, D)\)-sparse.

Let \(M_1, \dots , M_k\) be matroids on a finite set \(E\), and let \(\Delta \) be the bipartite graph that joins each \(e \in E\) to its copies \((1, e), \dots , (k, e)\) in the ground set of the direct sum \(M_1 \oplus \dots \oplus M_k\). The union \(\bigcup _j M_j\) is the matroid on \(E\) induced from \(M_1 \oplus \dots \oplus M_k\) by \(\Delta \): a set \(I \subseteq E\) is independent in \(\bigcup _j M_j\) if and only if \(\Delta \) matches \(I\) onto an independent set of \(M_1 \oplus \dots \oplus M_k\). For two matroids we write \(M_1 \cup M_2\).

Let \(a, b \ge 0\) with \(a + b \le d+1\), and let \(A \in \bigwedge ^{d+1-a} V\) and \(B \in \bigwedge ^{d+1-b} V\). The meet of \(A\) and \(B\) is

where \({*A} \in \bigwedge ^{a} V\) and \({*B} \in \bigwedge ^{b} V\), so that their join lies in \(\bigwedge ^{a+b} V\).

Let \(0 \le j \le d+1\). The wedge pairing \(\bigwedge ^{j} V \times \bigwedge ^{d+1-j} V \to K\) is nondegenerate, so \(X \mapsto \operatorname {vol}(X \vee \cdot )\) is an isomorphism \(\bigwedge ^{j} V \to (\bigwedge ^{d+1-j} V)^*\). The complement isomorphism \(* \colon \bigwedge ^{j} V \to \bigwedge ^{d+1-j} V\) is this isomorphism followed by the inverse of the coordinate identification of \(\bigwedge ^{d+1-j} V\) with its dual.

Let \(j \ge 0\). The linear map \(\bigwedge ^{j} V^{*} \to (\bigwedge ^{j} V)^{*}\) that sends \(\varphi _1 \vee \cdots \vee \varphi _j\) to the linear form

is an isomorphism.

The volume form \(\operatorname {vol} \colon \bigwedge ^{d+1} V \to K\) is the linear isomorphism with \(\operatorname {vol}(e_1 \vee \cdots \vee e_{d+1}) = 1\).

Let \(f\) be a polymatroid rank function on a finite set \(E\). The matroid \(M_f\) is the matroid on \(E\) induced by \(f\) (definition 15.3). Its independent sets are the sets \(I \subseteq E\) with \(|I'| \le f(I')\) for every non-empty \(I' \subseteq I\).

Let \(f\) be a non-decreasing submodular function on the subsets of a finite set \(E\). The matroid induced by \(f\) is the matroid \(M_f\) on \(E\) whose circuits are the minimal non-empty sets \(C \subseteq E\) with \(f(C) {\lt} |C|\). Equivalently, a set \(I \subseteq E\) is independent in \(M_f\) if and only if \(|I'| \le f(I')\) for every non-empty \(I' \subseteq I\).

Let \(V_1 \subseteq V(G)\). An open ear of \(G\) on \(V_1\) is a path \(a - x_1 - \cdots - x_k - b\) (\(k \ge 0\)) with distinct ends \(a, b \in V_1\) and distinct interior bodies \(x_1, \dots , x_k\) outside \(V_1\), such that \(V(G) = V_1 \cup \{ x_1, \dots , x_k\} \) and every edge of \(G\) off the path lies inside \(V_1\).

Let \(V\) be a set with a linear order, and let \(D\) be a partial orientation on \(V\) (definition 13.1). For \(v \in V\), the sorted out-neighbour list of \(v\) in \(D\) is the list of the out-neighbours of \(v\) in \(D\), the vertices \(u\) with \((v, u) \in D\), in increasing order.

The normals of a panel-hinge framework \((G, n)\) are in general position if \(n_u\) and \(n_v\) are linearly independent for any two distinct bodies \(u\) and \(v\).

A panel-hinge framework \((G, n)\) is a multigraph \(G = (V, E)\) together with a vector \(n_v \in K^{d+1}\) for each body \(v\), the normal of its panel \(\Pi (v)\). Its body-hinge interpretation is the body-hinge framework \((G, p)\) (definition 19.3) whose hinge at an edge \(e\) with ends \(u\) and \(v\) has the supporting extensor

(definition 23.1).

The panels of a panel-hinge framework \((G, n)\) are nonparallel if \(\hat n_u\) and \(\hat n_v\) are linearly independent for any two distinct bodies \(u\) and \(v\), where \(\hat n_v \in K^d\) consists of the first \(d\) coordinates of \(n_v\).

Let \(n_1, n_2 \in K^{d+1}\). The panel support extensor of \(n_1\) and \(n_2\) is

the image of the join \(n_1 \vee n_2\) (definition 18.4) under the complement isomorphism \(*\) (definition 22.5).

Let \(V\) be a set. A partial orientation on \(V\) is a finite set \(D \subseteq V \times V\) such that:

1. (no loops) \((v, v) \notin D\) for every \(v \in V\);

2. (no antiparallel pairs) if \((u, v) \in D\), then \((v, u) \notin D\).

The elements of \(D\) are its arcs, and an arc \((u, v)\) has tail \(u\) and head \(v\). An edge \(uv\) of the complete graph \(K_V\) is oriented in \(D\) if \((u, v) \in D\) or \((v, u) \in D\). The underlying edge set \(\underline{D} \subseteq E(K_V)\) is the set of edges oriented in \(D\). The empty orientation has no arcs.

Let \(D\) be a partial orientation on \(V\). A directed path in \(D\) from \(u_0\) to \(u_m\) is a simple directed walk \(u_0, u_1, \ldots , u_m\) along the arcs of \(D\) (definition 12.1): the vertices \(u_i\) are distinct, and \((u_{i-1}, u_i) \in D\) for \(1 \le i \le m\). Reversing the path replaces \(D\) by the partial orientation

The underlying edge sets of \(D'\) and \(D\) are equal.

Let \(D\) be a partial orientation on \(V\), and let \(k\) be a non-negative integer. For a vertex \(v\), the out-degree \(\mathrm{out}_D(v)\) is the number of arcs of \(D\) with tail \(v\), and the number of free pebbles at \(v\) is

For a finite set \(V' \subseteq V\), let

• \(\mathrm{peb}_{D,k}(V') = \sum _{v \in V'} \mathrm{peb}_{D,k}(v)\);

• \(\mathrm{span}_D(V')\) be the number of arcs of \(D\) with both ends in \(V'\);

• \(\mathrm{out}_D(V')\) be the number of arcs of \(D\) with tail in \(V'\) and head outside \(V'\).

Let \(G\) be a simple graph on \(V\) with finitely many edges, and let \(k\) and \(\ell \) be non-negative integers. A verdict on \(G\) is one of the following:

1. an acceptance, given by a \((k, \ell )\)-reachable partial orientation \(D\) on \(V\) with \(\underline{D} = E(G)\) (definition 13.6);

2. a rejection, given by a blocking witness \(V'\) for \(G\) (definition 13.13).

A verdict accepts \(G\) if it is an acceptance.

A planar picture of \(G\) is a map \(q \colon V(G) \to K^2\), written \(q_v = (x_v, y_v)\); its homogeneous picture points are the vectors \((x_v, y_v, 1) \in K^3\). The picture is admissible if \(q_u \neq q_v\) for every edge \(uv\) and, for every body \(v\), three members of the closed neighbourhood of \(v\) (definition 29.23) have linearly independent homogeneous picture points, that is, the points \(q_w\) of the closed neighbourhood do not lie on one line.

A multigraph \(G\) satisfies the conditioned pair at \(d\) when it has a pencil realization at the deficiency rank (definition 29.13); when, if it is simple, it has an adjacent-distinct one (definition 29.26); and when, if it is both simple and nondegeneracy-feasible (definition 29.23), it has a generic one (definition 29.25).

A planar picture \(q\) and a height \(z\) give the configuration \(p = (q, z)\) of homogeneous points \(p_v = (x_v, y_v, z_v, 1) \in K^4\). Given a choice of three bodies \(a_v, b_v, c_v\) at every body \(v\), the plane normal of \(p\) at \(v\) is the vector \(n_v \in K^4\) with \(n_v \cdot w = \det [p_{a_v}, p_{b_v}, p_{c_v}, w]\) for every \(w \in K^4\).

Let \(W \subseteq V(G)\), \(r \in W\), and let \(q\) be a planar picture. For \(t \in K\) the contraction curve \(q(t)\) keeps each body outside \(W\) at \(q\) and puts each \(c \in W\) at \((1 - t)\, q_r + t\, q_c\). The rescaled lifting system \(M(t)\) is the lifting system with weights (definition 30.21) whose weight \(\omega (v, w)\) is \((x_w - (1 - t)\, x_r,\ y_w - (1 - t)\, y_r,\ t)\) when \(w \notin W\) and the closed neighbourhood of \(v\) meets \(W\), and \((x_w, y_w, 1)\) otherwise. The heights \(z(t)\) of a solution \((z, h)\) of \(M(t)\) are \(t\, z_w\) at \(w \in W\) and \(z_w\) elsewhere.

A multigraph \(G\) has an adjacent-distinct pencil realization when it has a pencil realization at the deficiency rank (definition 29.13) in which the two concurrency points of every link are projectively distinct.

Let \(a - x_1 - \cdots - x_k - b\) be an open ear of \(G\) on \(V_1\) with \(k \ge 2\). Fix base data: a picture \(q_1\), heights \(z_1 \in L_{G[V_1]}(q_1)\), and \(h_a, h_b \in K^3\) with \(z_1(w) = h_a \cdot (q_1(w), 1)\) on the closed neighbourhood of \(a\) in \(G[V_1]\), and likewise \(h_b\) at \(b\). The ear data are a point \(s\) giving every body a point of \(K^2\) and a value in \(K\). They give the picture \(q(s)\), equal to \(q_1\) on \(V_1\) and to the points of \(s\) elsewhere, and the height \(z(s)\), equal to \(z_1\) on \(V_1\), to \(h_a \cdot (q(s)_{x_1}, 1)\) at \(x_1\), to \(h_b \cdot (q(s)_{x_k}, 1)\) at \(x_k\), to the value of \(s\) at the other interior bodies, and to \(0\) elsewhere. The configuration of \(s\) is \((q(s), z(s))\).

Let \(\iota \) be an injective map from the set of edge labels of \(G\) into a larger set of labels. The graph \(G\) with its edges relabelled by \(\iota \) has the bodies of \(G\), and an edge \(\iota (e)\) joining \(u\) and \(v\) for every edge \(e\) of \(G\) joining \(u\) and \(v\).

A multigraph \(G\) has a generic pencil realization when it has a nondegenerate pencil realization (definition 29.23) whose rigidity rows attain the deficiency-rank target of definition 29.13.

Let \(q\) be a planar picture of \(G\), and identify a vector \(h \in K^3\) with the affine function \((x, y) \mapsto h \cdot (x, y, 1)\) on \(K^2\). The space \(F(q)\) of lifting planes is the set of families \((h_v)_{v \in V(G)}\) of affine functions with \((h_u - h_v)(q_u) = (h_u - h_v)(q_v) = 0\) for every edge \(uv\).

Let \(q\) be a planar picture of \(G\). A height is a map \(z \colon V(G) \to K\). The lifting space \(L(q)\) is the set of heights \(z\) such that, for every body \(v\), the restriction of \(z\) to the closed neighbourhood of \(v\) agrees with an affine function of the picture there: there are \(a, b, c \in K\) with \(z_w = a x_w + b y_w + c\) for every \(w\) in that neighbourhood. The space \(\mathrm{Aff}(q)\) of globally affine heights is the subspace of heights \(z_w = \alpha x_w + \beta y_w + \gamma \) for a single triple \((\alpha , \beta , \gamma ) \in K^3\), the same at every body.

Let \(q\) be a planar picture of \(G\). The lifting system \(M(q)\) of \(G\) at \(q\) is the homogeneous linear system in the heights \(z\) and one coefficient vector \(h_v \in K^3\) per body \(v\) that requires \(z_w = h_v \cdot (x_w, y_w, 1)\) for every body \(v\) and every \(w\) in the closed neighbourhood of \(v\). Its coefficients are polynomials in \(q\), and the heights of its solutions form \(L(q)\). If \(q\) is admissible, its solutions form a space of dimension \(\dim L(q)\).

The pairing of \(c, c' \in \bigwedge ^2 K^4\) is

Let \(K\) be a field. The distinct main-component statement asserts that every simple two-edge-connected multigraph on at least three bodies has an adjacent-distinct pencil realization at the deficiency rank at \(d = 3\) (definition 29.26). The generic main-component statement asserts that every such multigraph that is nondegeneracy-feasible (definition 29.23) has a generic pencil realization at \(d = 3\) (definition 29.25).

Let \(\ell _0\) be the least value of \(\dim L(q)\) over admissible pictures \(q\) of \(G\). A main picture of \(G\) is an admissible picture \(q\) with \(\dim L(q) = \ell _0\), and \(U\) denotes the set of main pictures.

A vertex of a multigraph is a pencil hub when it has degree at least three. The closed hub-neighbourhood of a vertex \(v\) is the set of pencil hubs among \(v\) itself and its neighbours, and the closed neighbourhood of \(v\) is \(v\) together with all of its neighbours, hub or not. A pencil realization of \(G\) (definition 29.2) is nondegenerate when the two concurrency points of every link are projectively distinct; at every vertex, the panel normals of its closed hub-neighbourhood are linearly independent; and at every non-hub vertex, the concurrency points of its closed neighbourhood are linearly independent. A multigraph is nondegeneracy-feasible when it has a nondegenerate pencil realization.

A hinge-coplanar panel realization of a multigraph \(G\) (definition 23.63), with normal assignment \(v \mapsto n_v\), has a pencil realization when it is given in addition a per-body nonzero homogeneous point \(v \mapsto q_v \in K^{k+2}\), incident to its own panel (\(q_v \cdot n_v = 0\)). Every link’s supporting extensor must then pass through the points of both its endpoints (definition 29.1). We call this requirement the pencil condition.

A pencil realization at the deficiency rank of a multigraph \(G\) is a pencil realization \((F, n, q)\) of \(G\) (definition 29.2) whose rigidity rows span dimension

the target of theorem 23.66 restricted to the pencil condition.

For distinct bodies \(u, w\) of \(G\), the graph \(G_{uw}\) is \(G\) together with one new body \(x\) and two new edges, joining \(x\) to \(u\) and to \(w\).

Let \(\omega \) assign a vector \(\omega (v, w) \in K^3\) to every ordered pair of bodies. The lifting system with weights \(\omega \) of \(G\) is the homogeneous linear system in the heights \(z\) and one coefficient vector \(h_v \in K^3\) per body \(v\) of \(G\) requiring \(z_w = h_v \cdot \omega (v, w)\) for every body \(v\) and every \(w\) in the closed neighbourhood of \(v\).

The rank of a configuration \(p = (q, z)\) of \(G\) is the rank of the rigidity matrix (definition 19.7) of the panel-hinge framework on \(G\) whose panel normal at each body \(v\) is \(p_v\) (definition 23.5). The general configuration of \(G\) attains if there is a nonzero polynomial \(P\) in the picture coordinates such that every picture \(q\) with \(P(q) \neq 0\) is admissible and the heights \(z \in L(q)\) at which \((q, z)\) has rank \(6(|V(G)| - 1) - \operatorname {def}(\tilde G)\) (definition 20.3, at \(d = 3\)) contain a nonempty Zariski-open subset of \(L(q)\).

A chain of \(G\) is an open ear \(a - x_1 - \cdots - x_k - b\) on \(V_1\) with \(k \ge 1\) whose interior bodies all have degree two in \(G\) and whose ends have degree at least three.

Let \(\mathcal P\) be a property of graphs, and let open ears be as in definition 30.63. The graph \(G\) reduces to \(\mathcal P\) if one of the following holds.

1. \(\operatorname {def}_2(G) = \operatorname {def}_3(G)\).

2. \(G\) has a cut vertex with sides \(V_1\) and \(V_2\) as in theorem 30.49, and \(G[V_1]\) and \(G[V_2]\) satisfy \(\mathcal P\).

3. \(G\) has a chain of bridges between \(V_1\) and \(V_2\) as in theorem 30.52, and \(G[V_1]\) and \(G[V_2]\) satisfy \(\mathcal P\).

4. \(G\) is a cycle, given as an edge \(ab\) and a path from \(a\) to \(b\) through its other bodies, as in theorem 30.71.

5. \(G\) has an open ear \(a - x_1 - \cdots - x_k - b\) on \(V_1\), \(G[V_1]\) satisfies \(\mathcal P\), and one of the following holds: \(k \ge 5\); \(k \in \{ 3, 4\} \) and \(G\) with \(x_2\) suppressed satisfies \(\mathcal P\); \(k = 2\) and \(\operatorname {def}_3(G[V_1]) \le \operatorname {def}_3(G)\); \(k = 2\), \(a\) and \(b\) are not adjacent, \(\operatorname {def}_2(G[V_1]; a, b) + 2 \le \operatorname {def}_2(G[V_1])\) and \(G\) with \(x_2\) suppressed satisfies \(\mathcal P\); or \(k = 1\), \(a\) and \(b\) are not adjacent, \(\operatorname {def}_3(G[V_1]) \le \operatorname {def}_3(G)\) and \(\operatorname {def}_2(G[V_1]; a, b) + 2 \le \operatorname {def}_2(G[V_1])\).

6. \(G\) has an open ear \(a - x - b\) on \(V_1\) whose ends are not adjacent, \(\operatorname {def}_3(G[V_1]; a, b) + 5 \le \operatorname {def}_3(G[V_1])\), and \(G\) with \(x\) suppressed satisfies \(\mathcal P\).

7. \(G\) is 2-edge-connected, and there are \(W \subsetneq V(G)\) with \(|W| \ge 2\), no body outside \(W\) adjacent to two bodies of \(W\), and \(r \in W\), such that \(G/G[W]\) (collapsing \(W\) to \(r\)) satisfies \(\mathcal P\) and either \(\operatorname {def}_2(G[W]) = 0\), or \(\operatorname {def}_3(G[W]) = 0\), \(\operatorname {def}_2(G[W]) + \operatorname {def}_2(G/G[W]) \le \operatorname {def}_2(G)\) and \(G[W]\) satisfies \(\mathcal P\).

Here suppressing an interior body \(x_i\) is the splitting-off \(G_{x_i}^{x_{i-1} x_{i+1}}\) (definition 21.10, with \(x_0 = a\) and \(x_{k+1} = b\)) whose new edge carries the label of the edge \(x_{i-1} x_i\).

A graph \(G\) satisfies the standing hypotheses if it is finite, simple and connected, with minimum degree at least two. Then every closed neighbourhood of \(G\) has at least three members: in a simple graph a body has as many distinct neighbours as its degree.

A chain \(a - x_1 - \cdots - x_k - b\) on \(V_1\) is usable if \(k \ge 3\); or \(k = 2\) and either \(\operatorname {def}_3(G[V_1]; a, b) = \operatorname {def}_3(G[V_1])\), or \(a\) and \(b\) are not adjacent and \(\operatorname {def}_2(G[V_1]; a, b) + 2 \le \operatorname {def}_2(G[V_1])\); or \(k = 1\) and either \(\operatorname {def}_3(G[V_1]; a, b) = \operatorname {def}_3(G[V_1])\) or \(\operatorname {def}_3(G[V_1]; a, b) + 5 \le \operatorname {def}_3(G[V_1])\).

Let \((G,p)\) be a body-hinge framework, and let \(s\) be a set of bodies. The block pin of \(s\) is the subspace

of the infinitesimal motions that vanish on \(s\).

Let \(v_1, \dots , v_j \in K^{d+1}\), and let \(A(v)\) be the \(j \times (d+1)\) matrix whose \(i\)-th row is \(v_i\). For \(1 \le i_1 {\lt} \cdots {\lt} i_j \le d+1\), the Plücker coordinate \(P_{i_1, \dots , i_j}\) of \((v_1, \dots , v_j)\) is \((-1)^{1 + i_1 + \cdots + i_j}\) times the determinant of the \(j \times j\) submatrix of \(A(v)\) on the columns \(i_1, \dots , i_j\). The Plücker coordinate vector of \((v_1, \dots , v_j)\) is the vector of its \(\binom {d+1}{j}\) Plücker coordinates.

A polymatroid rank function on a finite set \(E\) is a non-decreasing submodular function \(f\) on the subsets of \(E\) with \(f(\emptyset ) = 0\).

Let \(G = (V, E)\) be a multigraph with \(V \neq \emptyset \). A panel-hinge realization \((G,p)\) of \(G\) (definition 23.5) is at the target rank if

A generic full-rank realization of \(G\) is a panel-hinge realization at the target rank whose normals are in general position (definition 23.9). A nonparallel full-rank realization of \(G\) is a panel-hinge realization at the target rank whose panels are nonparallel (definition 23.10). For a minimal \(k\)-dof-graph, \(\operatorname {def}(\tilde G) = k\) (definition 20.8), and the target rank is the rank \(D(|V| - 1) - k\) of KT eq. (6.1).

Let \(V\) be a finite set, and let each vertex \(a \in V\) have a list \(N^+(a)\) of vertices, its out-neighbours. Let \(R\) be the relation with \((a, b) \in R\) when \(b\) appears in \(N^+(a)\), and let \(P\) be a predicate on \(V\). For a set \(S \subseteq V\) of marked vertices and a vertex \(x\), the search for \(P\) from \(x\) with \(S\) marked returns a set \(S' \supseteq S\) of marked vertices, together with either a vertex \(w\) and a walk from \(x\) to \(w\), or a failure. It runs as follows.

1. If \(x \in S\), the search fails, with \(S' = S\).

2. Otherwise, if \(P(x)\) holds, it returns \(x\) and the walk of length \(0\) at \(x\), with \(S' = S\).

3. Otherwise, let \(y_1, \ldots , y_k\) be the out-neighbours of \(x\) in the order of \(N^+(x)\), and let \(S_0 = S \cup \{ x\} \). For \(i = 1, \ldots , k\) in turn, it runs the search for \(P\) from \(y_i\) with \(S_{i-1}\) marked. If this search returns a vertex \(w\) and a walk \(p\) from \(y_i\) to \(w\), it stops, and returns \(w\), the walk from \(x\) that steps to \(y_i\) and follows \(p\), and the set that this search returned. If it fails, with the set \(S_i\), the search goes on to \(y_{i+1}\). If all \(k\) of these searches fail, the search fails, with \(S' = S_k\).

The search for \(P\) from \(v\) is the case \(S = \varnothing \) and \(x = v\), without its set \(S'\).

Let \(k\) and \(\ell \) be non-negative integers. The \((k, \ell )\)-reachable partial orientations on \(V\) form the smallest set of partial orientations that contains the empty orientation and is closed under the following two moves, applied to a member \(D\):

1. reversing a directed path in \(D\) from \(u_0\) to \(u_m\) with \(\mathrm{out}_D(u_m) {\lt} k\) (definition 13.4);

2. inserting an arc \((u, v)\) with \(u \ne v\), \((u, v) \notin D\), \((v, u) \notin D\), \(\mathrm{out}_D(u) {\lt} k\) and \(\mathrm{peb}_{D, k}(u) + \mathrm{peb}_{D, k}(v) \ge \ell + 1\) (definition 13.5).

Let \(V\) and \(R\) be as in definition 12.2, and let \(v \in V\). For \(w \in V\), let \(P_w\) be the predicate that holds at \(w\) and nowhere else. The reachability region \(\mathrm{Reach}_R(v)\) is the set of vertices \(w \in V\) for which the search for \(P_w\) from \(v\) does not fail.

Let \((G,p)\) be a body-hinge framework and \(u, v\) two bodies. The relative screws of \(u, v\) in \((G,p)\) form the subspace

For a subspace \(U \subseteq K^{D}\), the joint rows at \(u, v\) confining the relative screw to \(U\) are the linear forms \(S \mapsto r\bigl(S(u) - S(v)\bigr)\) on screw assignments, one for each linear form \(r\) on \(K^D\) that vanishes on \(U\).

Let \(H\) be a subgraph of a multigraph \(G\), and let \(r\) be a vertex of \(H\). The contraction \(G/E(H)\) of \(H\) to \(r\) is obtained from \(G\) by deleting the edges of \(H\) and identifying every vertex of \(H\) with \(r\). Its vertices are \(r\) and the vertices of \(G\) not in \(H\). Its edges are the edges of \(G\) not in \(H\), and each end of such an edge that lies in \(V(H)\) is replaced by \(r\).

Let \(H\) be a subgraph of a multigraph \(G\). Then \(H\) is a rigid subgraph of \(G\) if \(H\) is a \(0\)-dof-graph. It is a proper rigid subgraph if moreover \(1 {\lt} |V(H)| {\lt} |V(G)|\).

Let \((G, b)\) be a body-bar framework in \({\mathbb {R}}^d\), and let \(D = \binom {d+1}{2}\). Orient each bar \(e\) of \(G\) from a body \(u_e\), its tail, to a body \(v_e\), its head. A motion of \((G, b)\) assigns a vector \(m(v) \in {\mathbb {R}}^D\) to each body \(v\). The rigidity map of \((G, b)\) is the linear map from motions to \({\mathbb {R}}^{E(G)}\) given by

Let \((G,p)\) be a body-hinge framework. Its rigidity matrix \(R(G,p)\) is the \((D-1)|E| \times D|V|\) matrix with a block of \(D - 1\) rows for each edge and a block of \(D\) columns for each body. Orient each edge \(e\) from one end \(u\) to the other end \(v\). The rows of \(e\) have \(r(p(e))\) in the columns of \(u\), \(-r(p(e))\) in the columns of \(v\), and zeros elsewhere (definition 19.5). An infinitesimal motion of \((G,p)\) is a screw assignment that satisfies the hinge constraint at every edge, that is, a vector of \(\ker R(G,p) \subseteq K^{D|V|}\). We write \(Z(G,p)\) for the space of infinitesimal motions.

Let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\). The rigidity map of \(G\) at \(p\) is the linear map \(R(G, p) : ({\mathbb {R}}^{d})^{V} \to {\mathbb {R}}^{E(G)}\) given by

for \(p' \in ({\mathbb {R}}^{d})^{V}\) and each edge \(uv\) of \(G\).

Let \(V\) be finite. The planar rigidity matroid \(\mathcal{R}(V)\) is the \((2, 3)\)-count matroid on \(V\) (definition 11.7): the matroid on \(E(K_V)\) whose independent sets are the sets \(I \subseteq E(K_V)\) for which the graph on \(V\) with edge set \(I\) is \((2, 3)\)-sparse.

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\) and \(P\) be as above, and let \(A\) be a part of \(P\). A normal or special cross edge is rooted at \(A\) if its common neighbor lies in \(A\).

Let \(V\), \(k\), \(\ell \) and the lists \(N^+_D(a)\) be as in definition 13.12. Let \(D_0\) be a \((k, \ell )\)-reachable partial orientation on \(V\), and let \((u_1, v_1), \ldots , (u_m, v_m)\) be a list of pairs of vertices. The pebble game on this list from \(D_0\) starts with \(D = D_0\), and for \(i = 1, \ldots , m\) in turn runs as follows.

1. If \(u_i = v_i\), or \((u_i, v_i) \in D\), or \((v_i, u_i) \in D\), it skips the pair.

2. Otherwise it processes \(u_i v_i\) at \(D\). If this rejects \(u_i v_i\), the game stops and returns the failure witness. If it accepts \(u_i v_i\) and returns \(D'\), the game sets \(D = D'\).

If no pair is rejected, the game returns the final orientation \(D\).

Now let \(G\) be a simple graph on \(V\), and let \(\ell {\lt} 2k\). The pebble game on \(G\) is the pebble game from the empty orientation on a list of the edges of \(G\) in which each edge \(uv\) appears once, as \((u, v)\) or as \((v, u)\). It accepts \(G\) if this game returns a partial orientation \(D\). It rejects \(G\), with the set \(V'\), if the game returns a failure witness whose set is \(V'\).

Let \(V\) be a finite set, let \(G\) be a simple graph on \(V\), and let \(k\) and \(\ell \) be non-negative integers with \(\ell {\lt} 2k\). The formal pebble game on \(G\) runs the pebble game from the empty orientation on mathlib’s list of the edges of \(G\), with mathlib’s lists of out-neighbours as the lists \(N^+_D(a)\) (formalization note 13.15). It returns the verdict on \(G\) (definition 13.25) that is an acceptance, given by \(D\), if the game returns a partial orientation \(D\), and a rejection, given by \(V'\), if the game returns a failure witness whose set is \(V'\).

Let \(V\) be a finite set with a linear order, let \(G\) be a simple graph on \(V\), and let \(k\) and \(\ell \) be non-negative integers with \(\ell {\lt} 2k\). The computable pebble game on \(G\) runs the pebble game on the sorted edge list of \(G\) (definition 14.3) from the empty orientation, with the sorted out-neighbour lists (definition 14.1) as the lists \(N^+_D(a)\). It returns the verdict on \(G\) (definition 13.25) that is an acceptance, given by \(D\), if the game returns a partial orientation \(D\), and a rejection, given by \(V'\), if the game returns a failure witness whose set is \(V'\).

The screw space is \(\bigwedge ^{d-1}K^{d+1}\). It has dimension \(\binom {d+1}{d-1} = D\), where \(D = \binom {d+1}{2}\).

For \(v \in {\mathbb {R}}^4\), let \(v' \in {\mathbb {R}}^3\) be its first three coordinates and \(v_4\) its last. The rotation part \(\omega _S \in {\mathbb {R}}^3\) and the translation part \(t_S \in {\mathbb {R}}^3\) of a screw \(S \in \bigwedge ^2 {\mathbb {R}}^4\) are the linear functions of \(S\) with

The velocity field of \(S\) is

The square of a graph \(G = (V,E)\) is the graph \(G^2 = (V, E^2)\) with

that is, \(G\) together with an edge joining every two vertices at distance two in \(G\).

Let \(E\) be a finite set. A function \(f\) from the subsets of \(E\) to the integers is submodular if \(f(X \cap Y) + f(X \cup Y) \le f(X) + f(Y)\) for all \(X, Y \subseteq E\).

Let \(G\) be a multigraph. Following Jackson and Jordán  [ JJ08a , § 2 ] , a partition \(P\) of \(V(G)\) is tight if it attains the deficiency, that is, if \(\operatorname {def}_{\tilde G}(P) = \operatorname {def}(\tilde G)\).

Let \(b \in {\mathbb {R}}^{d}\). The translation by \(b\) is the element \(\tau _b\) of \(({\mathbb {R}}^{d})^{V}\) with \((\tau _b)_v = b\) for every vertex \(v\).

Let \((G,p)\) be a body-hinge framework. A screw assignment \(S\) is trivial if \(S(u) = S(v)\) for all bodies \(u\) and \(v\), and the trivial screw assignments form the space of trivial motions. The framework \((G,p)\) is infinitesimally rigid if all its infinitesimal motions are trivial.

Let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\). The elementary trivial motions at \(p\) are the translations \(\tau _{e_i}\), for \(1 \le i \le d\), and the motions \((E_{ij} - E_{ji}) \circ p\), for \(1 \le j {\lt} i \le d\).

Let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\). The space \(T(p)\) of trivial infinitesimal motions at \(p\) is the linear span in \(({\mathbb {R}}^{d})^{V}\) of the translations \(\tau _b\), for \(b \in {\mathbb {R}}^{d}\), and the infinitesimal rotations \(A \circ p\), for skew-symmetric linear maps \(A\) of \({\mathbb {R}}^{d}\).

Let \(V\) be a finite set, and let \(k\) and \(\ell \) be non-negative integers. Let each partial orientation on \(V\) come with lists \(N^+_D(a)\) as in definition 13.9. Let \(D\) be a \((k, \ell )\)-reachable partial orientation on \(V\), and let \(u \ne v\) be vertices such that the edge \(uv\) is not oriented in \(D\). Let \(P_D\) be the predicate that holds at a vertex \(w\) when \(w \ne u\), \(w \ne v\) and \(\mathrm{peb}_{D, k}(w) {\gt} 0\). Processing \(uv\) at \(D\) runs as follows.

1. If \(\mathrm{peb}_{D, k}(u) + \mathrm{peb}_{D, k}(v) \ge \ell + 1\), it accepts \(uv\). It inserts the arc \((u, v)\) if \(\mathrm{peb}_{D, k}(u) {\gt} 0\), and the arc \((v, u)\) otherwise (definition 13.5), and returns the result.

2. Otherwise, it runs the pebble search for \(P_D\) from \(u\) in \(D\). If this search does not fail, it processes \(uv\) at the partial orientation \(D'\) that the search returns.

3. Otherwise, it runs the pebble search for \(P_D\) from \(v\) in \(D\). If this search does not fail, it processes \(uv\) at the partial orientation \(D'\) that the search returns.

4. Otherwise it rejects \(uv\). It returns the failure witness made of \(D\), the set \(\mathrm{Reach}_D(u) \cup \mathrm{Reach}_D(v)\) and the pair \((u, v)\). Here \(\mathrm{Reach}_D(x)\) is the reachability region of \(x\) in \(D\), the set of vertices reachable from \(x\) along the arcs of \(D\) (definition 12.5).

Let \(D\) be a partial orientation on a finite set \(V\), and let each vertex \(a\) have a list \(N^+_D(a)\) whose entries are the out-neighbours of \(a\) in \(D\). Let \(P\) be a predicate on \(V\), and let \(v \in V\). The pebble search for \(P\) from \(v\) in \(D\) runs the search for \(P\) from \(v\) (definition 12.2) with these lists, so that the search follows the arcs of \(D\).

1. If the search returns a vertex \(w\) and a walk \(p\), then \(p\) is a directed path in \(D\) from \(v\) to \(w\), and \(P(w)\) holds (theorem 12.4). The pebble search returns \(w\), \(p\), and the partial orientation obtained from \(D\) by reversing \(p\) (definition 13.4).

2. If the search fails, the pebble search fails.

Let \(G\) be a graph on \(V\). The core \(G^{\mathrm{core}}\) of \(G\) is the graph on \(V\) whose edges are those of all subgraphs \(H\) of \(G\) in which every vertex of the support of \(H\) has degree at least two in \(H\).

For \(p \in {\mathbb {R}}^d\) let \(h(p) = (1, p) \in {\mathbb {R}}^{d+1}\), with coordinates indexed by \(0, 1, \dots , d\). Index the \(D\) coordinates of \({\mathbb {R}}^D\) by the pairs \((i, j)\) with \(0 \le i {\lt} j \le d\), through a fixed bijection. The two-extensor of an ordered pair of points \(p, p' \in {\mathbb {R}}^d\) is the vector \(T(p, p') \in {\mathbb {R}}^D\) with

Let \(a, b \in V\). The Type I move at \(a\) and \(b\) adds to \(G\) a new vertex \(v\) and the edges \(va\) and \(vb\).

Let \(a, b, c \in V\). The Type II move on \(ab\) and \(c\) deletes the edge \(ab\) from \(G\) if it is present, and adds a new vertex \(v\) and the edges \(va\), \(vb\) and \(vc\).

Let \(V\) be a set, and let \(k\) and \(\ell \) be non-negative integers. A failure witness consists of a partial orientation \(D\) on \(V\), a finite set \(V' \subseteq V\), and a pair \((u, v)\) of distinct vertices in \(V'\), such that:

1. \(D\) is \((k, \ell )\)-reachable (definition 13.6);

2. the edge \(uv\) is not oriented in \(D\);

3. no arc of \(D\) has its tail in \(V'\) and its head outside \(V'\), that is, \(\mathrm{out}_D(V') = 0\);

4. \(\mathrm{peb}_{D, k}(V') \le \ell \).

Let \(G\) be a multigraph with a vertex \(v\) of degree two. Let \(F\) be a forest of \(\tilde G\) none of whose edges is incident with \(v\), and let \(x\) be an edge of \(\tilde G\) that joins \(v\) to a vertex \(w \neq v\). Then \(F \cup \{ x\} \) is a forest of \(\tilde G\).

Let \(D \ge 6\), that is, \(d \ge 3\), and let \(G\) be a minimal \(0\)-dof-graph with at least three vertices and no proper rigid subgraph. Then \(G\) has two adjacent vertices of degree two.

Let \(p_1, \dots , p_k \in K^d\). Then \(p_1, \dots , p_k\) are affinely independent if and only if \(\bar p_1, \dots , \bar p_k\) are linearly independent. In particular, \(d+1\) points \(p_1, \dots , p_{d+1}\) of \(K^d\) are affinely independent if and only if the \((d+1) \times (d+1)\) matrix with rows \(\bar p_1, \dots , \bar p_{d+1}\) has nonzero determinant.

Let \(D \ge 2\), and let \(G\) be a multigraph with a vertex \(v\) of degree two, whose edges join \(v\) to vertices \(a, b \neq v\). Then every base \(B\) of \(M(\tilde G)\) is the union of \(D\) pairwise disjoint forests of \(\tilde G\), each of which has an edge incident with \(v\).

Let \(D \ge 2\), and let \(G\) be a multigraph with a vertex \(v\) of degree two, whose edges \(e_a\) and \(e_b\) join \(v\) to vertices \(a, b \neq v\). Then every base \(B\) of \(M(\tilde G)\) contains at least \(D\) of the \(2(D - 1)\) edges of \(\tilde G\) incident with \(v\):

where \(\tilde e\) is the set of the \(D - 1\) copies of \(e\) in \(\tilde G\).

Let \((G,p)\) be a panel-hinge framework, let \(W\) be a set of bodies, and let \(H = G[W]\). Let \(R_W(G \setminus E(H), p)\) be the matrix of the rows of the edges of \(G\) not in \(H\), with the columns of \(W\) deleted. Then

Let \((G,p)\) be a body-hinge framework with \(C(p(e)) \neq 0\) at every edge \(e\). Let \(V_1\) be a nonempty proper subset of \(V(G)\), let \(V_2 = V(G) \setminus V_1\), and let \(C\) be a set of at most one edge of \(G\), each with one end in \(V_1\) and the other in \(V_2\). Then

In particular, if an edge of \(G\) joins \(V_1\) to a body \(w \in V_2\), then

Let \((G,p)\) be a body-hinge framework, let \(v\) be a body, and let \(V_1, V_2\) be sets of bodies with \(V_1 \cap V_2 \subseteq \{ v\} \) such that every edge of \(G\) lies inside \(V_1\) or inside \(V_2\). Then

Let \((G,p)\) be a body-hinge framework and \(V_1\) a set of bodies. Let \(a - x_1 - \cdots - x_k - b\) (\(k \geq 0\)) be a path in \(G\) with ends \(a \neq b\) in \(V_1\) and distinct bodies \(x_1, \dots , x_k\) outside \(V_1\), such that every edge of \(G\) off the path lies inside \(V_1\). Write \(x_0 = a\) and \(x_{k+1} = b\), suppose that \(C_i = C(p(x_i x_{i+1})) \neq 0\) for \(0 \le i \le k\), and let \(\Lambda = \operatorname {span}(C_0, \dots , C_k)\) and \(\rho = \rho _{ab}(G[V_1], p)\). Then

Let \((P,p)\) be a body-hinge framework whose edges are those of a path \(a = x_0 - x_1 - \cdots - x_k - x_{k+1} = b\) (\(k \geq 0\)) on distinct bodies, and let \(C_i = C(p(x_i x_{i+1})) \neq 0\) for \(0 \le i \le k\). Then \(\operatorname {rank} R(P,p) = (D-1)(k+1)\).

Let \((G,p)\) be a body-hinge framework and let \(u \neq v\) be bodies. Let \(V_1, V_2\) be sets of bodies with \(V_1 \cap V_2 \subseteq \{ u, v\} \), and let \(G_1, G_2\) be subgraphs of \(G\) such that every edge of \(G\) is an edge of \(G_1\) or of \(G_2\), and every edge of \(G_i\) lies inside \(V_i\). Let \(\rho _i = \rho _{uv}(G_i, p)\) (definition 19.27). Then the row spaces of \(R(G_1,p)\) and \(R(G_2,p)\) meet in the span of the joint rows at \(u, v\) confining the relative screw to \(\rho _1 + \rho _2\), and

Let \(D \ge 2\), and let \(G\) be a minimal \(k\)-dof-graph that is not \(2\)-edge-connected. Suppose that for every \(k'\), every minimal \(k'\)-dof-graph with at least one and fewer than \(|V(G)|\) vertices has a nondegenerate-hinge panel realization. Then \(G\) has a nondegenerate-hinge panel realization.

Let \(D \ge 2\), and let \(G\) be a simple minimal \(k\)-dof-graph that is not \(2\)-edge-connected. Suppose that for every \(k'\), every simple minimal \(k'\)-dof-graph with at least one and fewer than \(|V(G)|\) vertices has a generic full-rank realization. Then \(G\) has a generic full-rank realization.

Let \(G\) be a minimal \(k\)-dof-graph, let \(H\) be a proper rigid subgraph of \(G\), and let \(G/E(H)\) be its contraction to a vertex \(r\) of \(H\). Let \((G,p)\) be a body-hinge framework, and let \((G/E(H), p_2)\) be a realization of \(G/E(H)\) at the target rank (definition 23.21). Then \((G,p)\) is at the target rank if and only if

Let \(d \ge 2\), let \(K\) be an infinite field, and let \(G\) be a minimal \(k\)-dof-graph that has a proper rigid subgraph. Suppose that for every \(k'\), every minimal \(k'\)-dof-graph with at least one and fewer than \(|V(G)|\) vertices has a nondegenerate-hinge panel realization, and a generic full-rank realization if it is simple. Then \(G\) has a nondegenerate-hinge panel realization (definition 23.24), and if \(G\) is simple, a generic full-rank realization (definition 23.21).

Let \(d \ge 2\), let \(K\) be an infinite field, and let \(G\) be a minimal \(0\)-dof-graph that has a proper rigid subgraph. Suppose that for every \(k'\), every minimal \(k'\)-dof-graph with at least one and fewer than \(|V(G)|\) vertices has a nondegenerate-hinge panel realization, and a generic full-rank realization if it is simple. Then \(G\) has a nondegenerate-hinge panel realization (definition 23.24), and if \(G\) is simple, a generic full-rank realization (definition 23.21).

Let \(d \ge 2\), let \(K\) be an infinite field, and let \(G\) be a simple minimal \(k\)-dof-graph with \(|V(G)| \ge 3\). Let \(H\) be a proper rigid subgraph of \(G\) whose contraction \(G/E(H)\) to a vertex \(r\) of \(H\) is simple, and suppose that \(H\) and \(G/E(H)\) have generic full-rank realizations (definition 23.21). Then \(G\) has a generic full-rank realization, of rank \(D(|V(G)| - 1) - k\).

Let \(d \ge 2\), let \(K\) be an infinite field, and let \(G\) be a simple minimal \(0\)-dof-graph that has a proper rigid subgraph, and in which no proper rigid subgraph \(H\) has a simple contraction \(G/E(H)\). Suppose that every minimal \(0\)-dof-graph with at least one and fewer than \(|V(G)|\) vertices has a nondegenerate-hinge panel realization, and a generic full-rank realization if it is simple. Then \(G\) has a generic full-rank realization (definition 23.21).

Let \(d \ge 2\), and let \(G\) be a minimal \(k\)-dof-graph with \(|V(G)| \ge 3\) that is not simple. Suppose that for every \(k'\), every minimal \(k'\)-dof-graph with at least one and fewer than \(|V(G)|\) vertices has a nondegenerate-hinge panel realization, and a generic full-rank realization if it is simple. Then \(G\) has a nondegenerate-hinge panel realization (definition 23.24), of rank \(D(|V(G)| - 1) - k\).

Let \((G,p)\) be a body-hinge framework, let \(H\) be a proper rigid subgraph of \(G\), and let \(G/E(H)\) be its contraction to a vertex \(r\) of \(H\), with vertex set \(s_c = (V(G) \setminus V(H)) \cup \{ r\} \). Suppose that every infinitesimal motion of the restriction \((H,p)\) is constant on \(V(H)\), and that every infinitesimal motion of \((G/E(H), p)\) is constant on \(s_c\). Then every infinitesimal motion of \((G,p)\) is constant on \(V(G)\).

Let \(G\) be a minimal \(k\)-dof-graph with \(k {\gt} 0\), let \(v\) be a vertex of \(G\) of degree two, and let \(t = V(G) \setminus \{ v\} \). Then every infinitesimal motion of a body-hinge framework \((G,p)\) is constant on \(V(G)\) if and only if every infinitesimal motion \(S\) is constant on \(t\) and satisfies \(S(v) = S(w)\) for every \(w \in t\).

Let \(v\) be a body, and let \(\rho _1, \dots , \rho _m\) and \(\sigma _1, \dots , \sigma _l\) be linear forms on the screw assignments, the maps from the bodies to the screw space (definition 19.1). Suppose that the restrictions of \(\rho _1, \dots , \rho _m\) to the screw assignments that vanish off \(v\) are linearly independent, and that \(\sigma _1, \dots , \sigma _l\) are linearly independent and vanish on these screw assignments. Then \(\rho _1, \dots , \rho _m, \sigma _1, \dots , \sigma _l\) are linearly independent.

Let \((G,q)\) be a panel-hinge framework, and let \(e\) be an edge of \(G\) with distinct ends whose hinge is nondegenerate. Then some \(D - 1\) of the rows of \(R(G,q)\) at \(e\) are linearly independent.

Let \((G_1, q_1)\) and \((G_2, q_2)\) be panel-hinge frameworks. Index the rows of each rigidity matrix by an edge and a pair of coordinates, as in lemma 23.91. Let \(s_1\) be a set of indices at which the rows of \(R(G_1, q_1)\) are linearly independent, and let \(f \colon s_2 \to s_1\) be injective, such that the row of \(R(G_2, q_2)\) at each \(i \in s_2\) is the row of \(R(G_1, q_1)\) at \(f(i)\). Then the rows of \(R(G_2, q_2)\) at the indices in \(s_2\) are linearly independent.

Let \((G,p)\) be a body-hinge framework whose screw assignments are defined on a finite set \(W\) of bodies with \(\emptyset \neq V(G) \subseteq W\), and suppose that every infinitesimal motion of \((G,p)\) is constant on \(V(G)\). Then

If moreover \(C(p(e)) \neq 0\) at every edge \(e\) of \(G\), that is, every hinge is nondegenerate, then some \(D(|V(G)| - 1)\) rows of \(R(G,p)\) are linearly independent.

Let \((G,p)\) be a body-hinge framework, let \(v\) be a body, and let \(k'\) be an integer. Then \(\dim Z(G,p) = D + k'\) if and only if the space \(\operatorname {pinned}(v)\) of the infinitesimal motions \(S\) with \(S(v) = 0\) has dimension \(k'\) (lemma 19.20). Let \((G,n)\) be a panel-hinge framework in which \(v\) lies on no edge, and let \((G,n')\) be obtained by replacing the normal of \(v\) (definition 23.15). Then \(\dim Z(G,n') = D + k'\) if and only if \(\operatorname {pinned}(v)\) has dimension \(k'\) in \((G,n)\).

Let \(d \ge 2\), let \(K\) be an infinite field, and let \(G\) be a \(2\)-edge-connected minimal \(k\)-dof-graph with \(k {\gt} 0\), \(|V(G)| \ge 3\) and no proper rigid subgraph. Suppose that for every \(k'\), every minimal \(k'\)-dof-graph with at least one and fewer than \(|V(G)|\) vertices has a nondegenerate-hinge panel realization, and a generic full-rank realization if it is simple. Then \(G\) has a generic full-rank realization (definition 23.21), of rank \(D(|V(G)| - 1) - k\).

Let \(G\) be a multigraph, let \(v\) be a vertex of \(G\) of degree two whose edges join it to vertices \(a\) and \(b\), and let \(G_v^{ab}\) be obtained by splitting off \(v\) (definition 21.10). Let \((G_v^{ab}, q)\) be a panel-hinge framework with nondegenerate hinges, every infinitesimal motion of which is constant on \(V(G_v^{ab})\). Let \(t \neq 0\), and let \(q_0\) be the normals with \(q_0(v) = q(a) + t\, q(b)\) and \(q_0(w) = q(w)\) for every body \(w \neq v\). Then some \(D(|V(G)| - 1) - 1\) rows of \(R(G, q_0)\) are linearly independent.

Let \(d \ge 2\), let \(K\) be an infinite field, and let \(G\) be a simple minimal \(0\)-dof-graph with \(|V(G)| \ge 3\) and no proper rigid subgraph. Suppose that for every \(k'\), every minimal \(k'\)-dof-graph with at least one and fewer than \(|V(G)|\) vertices has a nondegenerate-hinge panel realization, and a generic full-rank realization if it is simple. Then \(G\) has a generic full-rank realization (definition 23.21), of rank \(D(|V(G)| - 1)\).

Let the rows \(R(G_v^{ab}, q; e_j)\) and the scalars \(\lambda _j\) and \(\lambda _{ej}\) be as in lemma 23.152, and let \(\lambda _{(ab)j} = \lambda _j\). For a body \(u\), write \(R(G_v^{ab}, q; e_j, u)\) for the restriction of the row \(e_j\) to the screw assignments that vanish off \(u\). Then for every body \(u\),

For \(u = a\) this is KT eq. (6.43).

Let \(d = 3\), so that \(D = 6\), and let \(K\) be an infinite field. Let \(G\) be a simple \(0\)-dof-graph, and let \(v\), \(a\), \(b\) and \(c\) be distinct vertices of \(G\) such that the edges of \(G\) at \(v\) are \(va\) and \(vb\), and those at \(a\) are \(va\) and \(ac\). Suppose that \(G_v^{ab}\) is a \(0\)-dof-graph with a generic full-rank realization (definition 23.21), and that there is a nonzero polynomial \(P\) in the normals with

wherever \(P(q) \neq 0\), as in lemma 23.140. Then \(G\) has a generic full-rank realization, of rank \(D(|V(G)| - 1)\).

Under the hypotheses of lemma 23.145, let the forms \(r_j\), the index \(i^*\) and the scalars \(\lambda _j\) be as in lemma 23.152, and let \(r = \sum _j \lambda _j r_j\). Let \(L\) be a \((d-2)\)-dimensional affine subspace of the panel \(\Pi (a)\) of \((G_v^{ab}, q)\), and let \((G, p_1)\) be the body-hinge framework with the hinge \(L\) at \(va\), the hinge \(q(ab)\) of \(ab\) at \(vb\), and at each edge \(e\) of \(G_v\) the hinge \(q(e)\) of \(e\) in \((G_v^{ab}, q)\) (KT eq. (6.12)): the framework of definition 23.147 for a normal \(n'\) of a hyperplane that meets \(\Pi (a)\) in \(L\). If \(r\) does not vanish on \(C(L)\), that is, if the top-left \(D \times D\) block of KT eq. (6.29) is nonsingular, then \(\operatorname {rank} R(G, p_1) \ge D(|V(G)| - 1)\).

Let \(r = \sum _j \lambda _j r_j\), where the forms \(r_j\) and the scalars \(\lambda _j\) are those of lemma 23.152, under the hypotheses of lemma 23.145. Let \(t \in K\), and let \(q_0\) be normals with \(q_0(v) = q(a) + t\, q(b)\) and \(q_0(b) = q(b)\). Then the combination of the rows at \(ab\) with the coefficients \(\lambda _j\) is the form \(S \mapsto r(S(a) - S(b))\), the form \(S \mapsto r(S(v) - S(b))\) is a row of \(R(G, q_0)\) at \(vb\), and

Let \(d \ge 2\), let \(K\) be an infinite field, and let \(G\) be a simple minimal \(0\)-dof-graph with \(|V(G)| \ge 3\). Let \(v_0 v_1 \cdots v_d\) be a chain of length \(d\) in \(G\) (definition 21.62), let \(G_1 = G_{v_1}^{v_0 v_2}\), and let \(u_0 = v_0\) and \(u_i = v_{i+1}\) for \(1 \le i \le d - 1\). Suppose that \(G_1\) is a \(0\)-dof-graph with a generic full-rank realization, and that for every \(k'\), every minimal \(k'\)-dof-graph with at least one and fewer than \(|V(G)|\) vertices has a nondegenerate-hinge panel realization, and a generic full-rank realization if it is simple. Then there are normals \(q\) in general position (definition 23.9), a nonzero linear form \(r\) on \(\bigwedge ^{d-1} K^{d+1}\), an index \(0 \le i \le d - 1\) and a vector \(n' \in K^{d+1}\) with the following properties.

1. The matrix \(R(G_1, q)\) has \(D(|V(G)| - 2)\) linearly independent rows (definition 19.7; KT eq. (6.46)).

2. \(r(C(q(v_0), q(v_2))) = 0\), and the form \(S \mapsto r(S(v_0) - S(v_2))\) lies in the row space of \(R(G - v_1, q)\) (KT eq. (6.52)).

3. The vector \(n'\) is linearly independent of \(q(u_i)\), and \(r(C(q(u_i), n')) \neq 0\).

Under the hypotheses of lemma 23.200, \(G\) has a generic full-rank realization (definition 23.21), of rank \(D(|V(G)| - 1)\).

Let \(d \ge 3\), let \(G\) be a multigraph with a chain \(v_0 v_1 \cdots v_d\) of length \(d\) (definition 21.62), and let \(q\) be normals. Let \(r\) be a linear form on \(\bigwedge ^{d-1} K^{d+1}\) that vanishes on \(C(q(v_0), q(v_2))\), such that the form \(S \mapsto r(S(v_0) - S(v_2))\) lies in the row space of \(R(G - v_1, q)\). Let \(2 \le i \le d - 1\), and let \(\sigma _i\) and \(q_i\) be as above. Then \(r\) vanishes on \(C(q_i(v_{i-1}), q_i(v_{i+1}))\), the hinge of the new edge \(v_{i-1} v_{i+1}\) of \((G_i, q_i)\), and the form \(S \mapsto r(S(v_{i-1}) - S(v_{i+1}))\) lies in the row space of \(R(G - v_i, q_i)\).

Let \(G\) be a multigraph with a chain \(v_0 v_1 \cdots v_d\) of length \(d\) (definition 21.62), let \(2 \le i \le d - 1\), and let \(q\) be normals. Let \(\sigma _i\) and \(q_i\) be as above. Let \(f\) be a row of \(R(G - v_1, q)\), or a form \(S \mapsto x(S(v_0) - S(v_2))\) for a linear form \(x\) on \(K^D\) that vanishes on \(C(q(v_0), q(v_2))\). Then the form \(S \mapsto f(S \circ \sigma _i^{-1})\) is a row of \(R(G - v_i, q_i)\), or a form \(S \mapsto x'(S(v_{i-1}) - S(v_{i+1}))\) for a linear form \(x'\) on \(K^D\) that vanishes on \(C(q_i(v_{i-1}), q_i(v_{i+1}))\).

Let \(d \ge 2\), let \(G\) be a multigraph with a vertex \(v\) of degree two, whose edges join \(v\) to distinct vertices \(a, b \neq v\), and let \(G_v = G - v\). Let \(q\) be normals at which the hinge of the new edge \(ab\) of \((G_v^{ab}, q)\) is nondegenerate. Suppose that, for some \(k' \le D - 2\),

as in KT eqs. (6.18) and (6.22). Then one of the \(D - 1\) rows of \(R(G_v^{ab}, q)\) at \(ab\) lies in the span of the rows of \(R(G_v, q)\) and the other rows at \(ab\).

Let \((G, p)\) be a body-hinge framework, let \(e\) be an edge of \(G\) with distinct ends whose hinge is nondegenerate, and let \(R_e\) be the span of the rows of \(R(G, p)\) at \(e\). Let \(W\) be a space of linear forms on the screw assignments such that

Then \(R_e\) has a basis \(r_1, \dots , r_{D-1}\) with \(r_i \in W + \operatorname {span}\{ r_j : j \neq i\} \) for some \(i\).

Let \(d = 3\). Under the hypotheses of lemma 23.145, let \(r\) be the linear form of lemma 23.163, and let \(\bar p_1, \dots , \bar p_4 \in K^4\) be linearly independent. Then \(r(\bar p_i \vee \bar p_j) \neq 0\) for some \(1 \le i {\lt} j \le 4\).

Under the hypotheses of lemma 23.145, let \(r\) be the linear form of lemma 23.163. Let \(L\) be a \((d-2)\)-dimensional affine subspace of the panel of a vertex of \((G_v^{ab}, q)\), and let \(r'_1, \dots , r'_{D-1}\) be linearly independent linear forms on \(K^D\) that vanish on \(C(L)\). Then \(r'_1, \dots , r'_{D-1}, r\) are linearly independent if and only if \(r(C(L)) \neq 0\).

Let \(\sigma \) be a set of variables, and let \(P_{ij} \in K[\sigma ]\) for \(1 \le i \le 4\) and \(1 \le j \le 3\). For \(t \in K^\sigma \), let \(p_i(t) = \bigl(P_{i1}(t), P_{i2}(t), P_{i3}(t)\bigr) \in K^3\). Then some \(P \in K[\sigma ]\) satisfies \(P(t) = \det \bigl(\bar p_1(t), \dots , \bar p_4(t)\bigr)\) for every \(t \in K^\sigma \).

Under the hypotheses of lemma 23.145, suppose that the edges of \(G\) at \(a\) are \(va\) and \(ac\), where \(v\), \(a\), \(b\) and \(c\) are distinct. Let the forms \(r_j\) and the scalars \(\lambda _j\) and \(\lambda _{ej}\) be as in lemma 23.152, and let \(r = \sum _j \lambda _j r_j\). Write the rows \(R(G_v^{ab}, q; (ac)j)\) at \(ac\) as the forms \(S \mapsto s_j(S(a) - S(c))\). Then

Let \(\bar p_1, \dots , \bar p_{d+1} \in K^{d+1}\) be linearly independent. For \(1 \le i {\lt} j \le d + 1\), let \(E_{ij}\) be the join of the \(d - 1\) vectors \(\bar p_l\) with \(l \neq i, j\), in increasing order of \(l\). Then the \(D\) extensors \(E_{ij}\) span \(\bigwedge ^{d-1} K^{d+1}\). In particular, for \(d = 3\) the six joins \(\bar p_i \vee \bar p_j\) (\(1 \le i {\lt} j \le 4\)) span \(\bigwedge ^2 K^4\).

Let \(n_1, n_2 \in K^4\) be linearly independent, and let \(x, y \in K^4\) satisfy \(x \cdot n_i = y \cdot n_i = 0\) for \(i = 1, 2\). Then \(x \vee y\) is a scalar multiple of \(*(n_1 \vee n_2)\). In particular, every linear form \(r\) on \(\bigwedge ^2 K^4\) with \(r(*(n_1 \vee n_2)) = 0\) satisfies \(r(x \vee y) = 0\).

Let \(S\) be a subset of \(\bigwedge ^{d-1} K^{d+1}\) that spans it, and let \(r\) be a linear form on \(\bigwedge ^{d-1} K^{d+1}\) that vanishes on \(S\). Then \(r = 0\).

Under the hypotheses of lemma 23.145, let \(r\) be the linear form of lemma 23.163. Let \(L'\) be a \((d-2)\)-dimensional affine subspace of the panel \(\Pi (b)\) of \((G_v^{ab}, q)\), and let \((G, p_2)\) be the body-hinge framework with the hinge \(q(ab)\) at \(va\), the hinge \(L'\) at \(vb\), and the hinge \(q(e)\) at each edge \(e\) of \(G_v\) (KT eq. (6.19)): the framework \((G, p_1)\) of definition 23.147 with the roles of \(a\) and \(b\) exchanged, for a normal of a hyperplane that meets \(\Pi (b)\) in \(L'\). If \(r\) does not vanish on \(C(L')\), that is, if the top-left \(D \times D\) block \(M_2\) of KT eq. (6.30) is nonsingular, then \(\operatorname {rank} R(G, p_2) \ge D(|V(G)| - 1)\).

Under the hypotheses of lemma 23.145, suppose that the edges of \(G\) at \(a\) are \(va\) and \(ac\), where \(v\), \(a\), \(b\) and \(c\) are distinct. Let \(r\) be the linear form of lemma 23.163. Let \(L''\) be a \((d-2)\)-dimensional affine subspace of the panel \(\Pi (c)\) of \((G_v^{ab}, q)\), and let \((G, p_3)\) be the body-hinge framework with the hinge \(q(ac)\) at \(va\), the hinge \(q(ab)\) at \(vb\), the hinge \(L''\) at \(ac\), and the hinge \(q(e)\) at every other edge \(e\) (KT eq. (6.33)): the framework \((G, p_1)\) of definition 23.147 for the normals \(q_\rho \) of lemma 23.185, with \(a\), \(c\) and \(v\) in the roles of \(v\), \(a\) and \(b\), and a normal of a hyperplane that meets \(\Pi (c)\) in \(L''\). If \(r\) does not vanish on \(C(L'')\), that is, if the top-left \(D \times D\) block \(M_3\) of KT eq. (6.41) is nonsingular, then \(\operatorname {rank} R(G, p_3) \ge D(|V(G)| - 1)\).

Let \(m {\lt} d + 1\), and let \(n_1, \dots , n_m \in K^{d+1}\). Then there is a nonzero \(x \in K^{d+1}\) with \(x \cdot n_i = 0\) for \(1 \le i \le m\).

There are linearly independent \(n_a, n_b, n_c \in K^4\) and affinely independent points \(p_1, \dots , p_4 \in K^3\) such that

where \(\Pi (u)\) is the plane \(\{ x \in K^3 : \bar x \cdot n_u = 0\} \).

Let \(K\) be infinite, and let \(\sigma \) be a set of variables. For each \(t \in K^\sigma \), let \(p_1(t), \dots , p_4(t)\) be points of \(K^3\). Suppose that a nonzero polynomial \(P \in K[\sigma ]\) satisfies \(P(t) = \det \bigl(\bar p_1(t), \dots , \bar p_4(t)\bigr)\), the determinant of the matrix with these rows, for every \(t\). Then \(p_1(t), \dots , p_4(t)\) are affinely independent for some \(t\).

Let \(n_a, n_b, n_c \in K^4\) be linearly independent. Then there are linearly independent \(\bar p_1, \dots , \bar p_4 \in K^4\) with \(\bar p_1 \cdot n_a = \bar p_1 \cdot n_b = \bar p_1 \cdot n_c = 0\) and

Under the hypotheses of lemma 23.145, let the forms \(r_j\) and the scalars \(\lambda _j\) be as in lemma 23.152. Then the linear form \(r = \sum _j \lambda _j r_j\) on \(K^D\) is not zero.

Let \(v \neq a\) be bodies, and let \(\Phi \) be the map on screw assignments with \(\Phi (S)(v) = S(v) + S(a)\) and \(\Phi (S)(u) = S(u)\) for every body \(u \neq v\). Then \(\Phi \) is a linear automorphism. For every linear form \(x\) on \(K^D\), the form \(S \mapsto x(S(v) - S(a))\) composed with \(\Phi \) is the form \(S \mapsto x(S(v))\), which vanishes at every \(S\) with \(S(v) = 0\).

Let \(v\) be a body, and let \(\varphi _1, \dots , \varphi _{D-1}\), \(\omega \) and \(\psi _1, \dots , \psi _l\) be linear forms on the screw assignments. Suppose that the restrictions of \(\varphi _1, \dots , \varphi _{D-1}\) and \(\omega \) to the screw assignments that vanish off \(v\) are linearly independent, and that \(\psi _1, \dots , \psi _l\) are linearly independent and vanish on these screw assignments. Then the forms \(\varphi _1, \dots , \varphi _{D-1}, \omega , \psi _1, \dots , \psi _l\) are linearly independent.

Let \(D \ge 2\), and let \(G\) be a minimal \(0\)-dof-graph with a vertex \(v\) of degree two, whose edges \(e_a\) and \(e_b\) join \(v\) to distinct vertices \(a, b \neq v\). Let \(G_v = G - v\) and \(k' = \operatorname {def}(\tilde G_v)\). Then \(G_v\) is a minimal \(k'\)-dof-graph, and

Let \(d \ge 2\), let \(G\) be a simple minimal \(0\)-dof-graph with a vertex \(v\) of degree two, whose edges join \(v\) to distinct vertices \(a, b \neq v\), and let \(G_v = G - v\). Then there is a nonzero polynomial \(P\) in the normals such that

for all normals \(q\) with \(P(q) \neq 0\).

Let \(G\) be a multigraph with a vertex \(v\) of degree two, whose edges \(va\) and \(vb\) join \(v\) to distinct vertices \(a, b \neq v\), and let \(G_v = G - v\). Let \(q\) be normals, let \(n' \in K^{d+1}\) be linearly independent of \(q(a)\), and let \((G, p_1)\) be the framework of definition 23.147 for \(n'\). Let \(r\) be a linear form on \(\bigwedge ^{d-1} K^{d+1}\) that vanishes on \(C(q(a), q(b))\), such that the form \(S \mapsto r(S(a) - S(b))\) lies in the row space of \(R(G_v, q)\). Suppose that some \(D(|V(G_v)| - 1)\) linearly independent forms are each a row of \(R(G_v, q)\) or a form \(S \mapsto r'(S(a) - S(b))\), for a linear form \(r'\) that vanishes on \(C(q(a), q(b))\). If \(r(C(q(a), n')) \neq 0\), then

Let \(d \ge 2\), let \(G\) be a multigraph with a vertex \(v\) of degree two, whose edges join \(v\) to distinct vertices \(a, b \neq v\), and let \(G_v = G - v\). Let \(q\) be normals at which the hinge of the new edge \(ab\) of \((G_v^{ab}, q)\) is nondegenerate, and every infinitesimal motion of \((G_v^{ab}, q)\) is constant on \(V(G_v^{ab})\). Suppose that

Then there are linearly independent forms \(r_1, \dots , r_{D-1}\) that span the same space as the rows of \(R(G_v^{ab}, q)\) at \(ab\), an index \(i^*\) and scalars \(\lambda _1, \dots , \lambda _{D-1}\) with \(\lambda _{i^*} = 1\), such that the form \(\sum _j \lambda _j r_j\) is not zero and lies in the row space of \(R(G_v, q)\).

Under the hypotheses of lemma 23.145, let \(W\) be the row space of \(R(G_v, q)\). Then there are linearly independent linear forms \(r_1, \dots , r_{D-1}\) on \(K^D\) that vanish on \(C(q(a), q(b))\), an index \(i^*\) and scalars \(\lambda _1, \dots , \lambda _{D-1}\) with \(\lambda _{i^*} = 1\), such that the form \(S \mapsto \sum _j \lambda _j r_j(S(a) - S(b))\) lies in \(W\). That is, writing \(R(G_v^{ab}, q; (ab)j)\) for the row \(S \mapsto r_j(S(a) - S(b))\) at \(ab\) and \(R(G_v^{ab}, q; e_j)\) for the rows of an edge \(e\) of \(G_v\), there are scalars \(\lambda _{ej}\) with

Let \((G, q_0)\) and \((G', q)\) be panel-hinge frameworks, and let \(e\) be an edge of \(G\) and of \(G'\) with the same ends \(u\) and \(w\) in both. If \(q_0(u) = q(u)\) and \(q_0(w) = q(w)\), then \(e\) has the same rows in \(R(G, q_0)\) as in \(R(G', q)\), indexed as in lemma 23.91.

Let \(G\) be a multigraph with a vertex \(v\) of degree two, whose edges join \(v\) to distinct vertices \(a, b \neq v\), and orient \(vb\) from \(v\) to \(b\) and \(ab\) from \(a\) to \(b\). Let \(q\) be normals, \(t \in K\), and \(q_0\) normals with \(q_0(v) = q(a) + t\, q(b)\) and \(q_0(b) = q(b)\). Then each row of \(R(G, q_0)\) at \(vb\), minus the row of \(R(G_v^{ab}, q)\) at \(ab\) with the same index (lemma 23.91), is a form \(S \mapsto x(S(v) - S(a))\) for a linear form \(x\) on \(K^D\) that vanishes on \(C(q(a), q(b))\). Moreover, for every linear form \(x\) on \(K^D\), the form \(S \mapsto x(S(v) - S(a))\) composed with the map \(\Phi \) of lemma 23.149 depends only on \(S(v)\).

Let \(v\) be a body, and let \(f\) be a linear form on the screw assignments such that \(f(S) = 0\) for every screw assignment \(S\) with \(S(v) = 0\). For a screw \(y\), let \(S_y\) be the screw assignment with the value \(y\) at \(v\) and \(0\) elsewhere. Then \(f(S) = f(S_{S(v)})\) for every screw assignment \(S\).

Let \(D \ge 3\), and let \(G\) be a minimal \(0\)-dof-graph with at least three vertices and no proper rigid subgraph. Then \(G\) is a cycle on at most \(d\) vertices (definition 21.64), or \(G\) has a chain of length \(d\) (definition 21.62).

Let \(D \ge 3\), and let \(G\) be a minimal \(0\)-dof-graph with at least four vertices and no proper rigid subgraph. Then \(G\) is a cycle on at most \(d\) vertices, or \(G\) has a chain \(v_0 v_1 \dots v_d\) of length \(d\) such that \(G_{v_1}^{v_0 v_2}\) is a simple minimal \(0\)-dof-graph with at least two and fewer than \(|V(G)|\) vertices.

Let \(D \ge 6\), and let \(G\) be a minimal \(0\)-dof-graph with at least four vertices and no proper rigid subgraph. Then \(G\) has distinct vertices \(v\), \(a\), \(b\), \(c\) and edges \(e_a = va\), \(e_b = vb\) and \(e_c = ac\), such that \(e_a\) and \(e_b\) are the only edges at \(v\), and \(e_a\) and \(e_c\) are the only edges at \(a\).

Let \(D \ge 1\), let \(G\) be a multigraph, let \(X\) be a circuit of \(M(\tilde G)\), and let \(e \in X\). Then \(|X - e| = D(|V(X)| - 1)\), and \(X - e\) is the union of \(D\) edge-disjoint spanning trees on \(V(X)\). Moreover, \(G[V(X)]\) is a rigid subgraph of \(G\).

Let \(G\) be a multigraph, let \(X\) be a circuit of \(M(\tilde G)\), and let \(e \in X\). Then \(\tilde G \restriction (X - e)\) is \((D, D)\)-sparse, and \(X - e\) is a basis of \(X\), that is, a maximal subset of \(X\) that is independent in \(M(\tilde G)\).

Let \(G\) be a multigraph, let \(H\) be a proper rigid subgraph of \(G\), and let \(G/E(H)\) be its contraction to a vertex \(r\) of \(H\), with vertex set \(s_c = (V(G) \setminus V(H)) \cup \{ r\} \). Suppose that \(G/E(H)\) is a simple \(0\)-dof-graph (definition 20.8) with a generic full-rank realization (definition 23.21). Then there are normals \(q_0\) at which some \(D(|s_c| - 1)\) rows of \(R(G \setminus E(H), q_0)\) are linearly independent after the columns of \(V(H)\) are deleted.

Let \(D \ge 2\), and let \(G\) be a simple minimal \(k\)-dof-graph that has a proper rigid subgraph, and in which no proper rigid subgraph \(H\) has a simple contraction \(G/E(H)\) (definition 21.3). Then \(k = 0\), and \(G\) has a vertex \(v\) of degree two, joined to two distinct vertices, such that \(G_v\) (definition 21.10) is a simple minimal \(0\)-dof-graph.

Let \(H\) be a graph on \(V\), and let \(X \subseteq V\) be a clique of \(H\), that is, a set of pairwise adjacent vertices. Then \(\bigl|E_{H}[X]\bigr| = \binom {|X|}{2}\).

1. Let \(d \ge 1\) and \(0 \le j \le d+1\), and let \(X \in \bigwedge ^{j} K^{d+1}\) and \(Y \in \bigwedge ^{d+1-j} K^{d+1}\) with \(X \vee Y = 0\). Then \(\langle *X, Y \rangle = 0\).

2. Let \(n_1, n_2, c \in K^4\), and let \(Y = n_1 \vee c\). Then \((n_1 \vee n_2) \vee Y = 0\) and \(\langle *(n_1 \vee n_2), Y \rangle = 0\).

Let \(W\) be a subspace of \(K^4\). The linear map \(\bigwedge ^{2} W \to \bigwedge ^{2} K^4\) induced by the inclusion of \(W\) in \(K^4\) is injective.

Let \(W\) be a \(2\)-dimensional vector space over \(K\). Then \(\dim \bigwedge ^{2} W = \binom {2}{2} = 1\). Consequently, every element of \(\bigwedge ^{2} W\) is a scalar multiple of any nonzero one.

Let \(0 \le j \le d+1\), \(X \in \bigwedge ^{j} V\) and \(Y \in \bigwedge ^{d+1-j} V\). Then

Let \(D \ge 1\), and let \(H\) be a rigid subgraph of a multigraph \(G\), with at least one vertex. Then

Let \(G\) be a minimal \(k\)-dof-graph, and let \(H\) be a subgraph of \(G\). Then every base of \(M(\tilde G)/E(\tilde H)\) meets \(\tilde e\) for every edge \(e\) of \(G\) that is not an edge of \(H\).

Let \(H\) be a subgraph of a multigraph \(G\). Then

Let \(D \ge 1\), let \(G\) be a minimal \(k\)-dof-graph, and let \(H\) be a proper rigid subgraph of \(G\). Then

and every base of \(M(\tilde G)/E(\tilde H)\) meets \(\tilde e\) for every edge \(e\) of \(G\) that is not an edge of \(H\).

Let \(c_0 = 0 \in {\mathbb {R}}^d\), and for \(1 \le i \le d\) let \(c_i\) be the \(i\)-th standard basis vector of \({\mathbb {R}}^d\). Then the \(D\) two-extensors \(T(c_i, c_j)\), \(0 \le i {\lt} j \le d\), are linearly independent, and so form a basis of \({\mathbb {R}}^D\).

Let \(n \in K^4\) be nonzero and let \(C_1, C_2 \in \bigwedge ^{2} K^{4}\) be nonzero screw elements each lying in the panel with normal \(n\) (definition 23.24). Then there is a nonzero point \(q \in n^{\perp }\) through which both pass (definition 29.1).

Let \(G\) be a multigraph.

1. Let \(V'\) be a set of vertices of \(G\) with \(V' \neq V(G)\) and \(d_G(V') \le 1\), and let \(V'' = V(G) \setminus V'\). Then

   \[ \operatorname {def}(\tilde G) \; =\; \operatorname {def}(\tilde G[V']) + \operatorname {def}(\tilde G[V'']) + D - (D-1)\, d_G(V'). \]

   So the cut adds \(1\) to the sum if \(d_G(V') = 1\), and \(D\) if \(d_G(V') = 0\).

2. If \(G\) is a minimal \(k\)-dof-graph that is not \(2\)-edge-connected, then for some nonempty set \(V'\) as in (1), \(G[V']\) and \(G[V'']\) are minimal \(k'\)- and \(k''\)-dof-graphs, where \(k' = \operatorname {def}(\tilde G[V'])\), \(k'' = \operatorname {def}(\tilde G[V''])\), and \(k = k' + k'' + D - (D-1)\, d_G(V')\).

3. If \(G\) has no loops, \(V'\) is as in (1), and an edge of \(G\) joins \(V'\) to a vertex \(w \notin V'\), then \(\operatorname {def}(\tilde G[V' \cup \{ w\} ]) = \operatorname {def}(\tilde G[V']) + 1\).

Let \(G\) be presented as a cycle of \(m\) bodies (definition 21.64) with \(3 \le m \le 4\). Then \(G\) has a hinge-coplanar panel realization (definition 23.63) that is infinitesimally rigid on all of its bodies \(V(G)\) (definition 19.15).

Let \(3 \le m \le d + 1\). Then there are \(n_0, \dots , n_{m-1} \in K^{d+1}\) such that the \(m\) extensors \(C(n_i, n_{i+1})\), with indices mod \(m\), are linearly independent. In particular, each \(n_i \vee n_{i+1}\) is nonzero.

Let \(G\) be presented as a cycle of \(m\) bodies (definition 21.64) with \(3 \le m \le 4\). Then \(G\) has a pencil realization (definition 29.2) that is infinitesimally rigid on all of its bodies \(V(G)\) (definition 19.15).

Let \(K\) be an infinite field, let \(3 \le m \le d + 1\), and let \(G\) be a cycle on \(m\) vertices (definition 21.64) that is a minimal \(0\)-dof-graph. Then \(G\) has a generic full-rank realization (definition 23.21), of rank \(D(m - 1)\).

Let \((G,p)\) be a panel-hinge framework, and let \(e_1\) and \(e_2\) be edges of \(G\) that both join the bodies \(u\) and \(v\), with \(C(p(e_1))\) and \(C(p(e_2))\) linearly independent. Then every infinitesimal motion \(S\) of \((G,p)\) has \(S(u) = S(v)\). In particular, if \(u\) and \(v\) are distinct and are the only bodies, then \((G,p)\) is infinitesimally rigid, of rank \(D\).

Let \((G,p)\) be a panel-hinge framework, and let \(e_1, \dots , e_m\) be edges of \(G\) with \(C(p(e_1)), \dots , C(p(e_m))\) linearly independent. Then \(m \le D\).

Let \((G,p)\) be a body-hinge framework, let \(m \ge 1\), and let \(v_0, \dots , v_{m-1}\) be bodies, not necessarily distinct. Let \(f_0, \dots , f_{m-1}\) be edges of \(G\) such that \(f_i\) joins \(v_i\) and \(v_{i+1}\), with indices modulo \(m\), and suppose that \(C(p(f_0)), \dots , C(p(f_{m-1}))\) are linearly independent. Then every infinitesimal motion \(S\) of \((G,p)\) has \(S(v_0) = S(v_1) = \cdots = S(v_{m-1})\). In particular, if \(v_0, \dots , v_{m-1}\) are all the bodies, then \((G,p)\) is infinitesimally rigid.

Let \(3 \le m \le D\), and let \(C\) be a multigraph whose vertices are \(m\) distinct vertices \(v_0, \dots , v_{m-1}\) and whose edges are \(m\) edges \(f_0, \dots , f_{m-1}\), where \(f_i\) joins \(v_i\) and \(v_{i+1}\), with indices modulo \(m\). Then \(C\) is a \(0\)-dof-graph.

Let \(p_0, p_1, p_0', p_1' \in K^{d+1}\) with \(p_0 \vee p_1 = p_0' \vee p_1' \neq 0\). Then \(\operatorname {span}\{ p_0, p_1\} = \operatorname {span}\{ p_0', p_1'\} \).

Let \(X \subseteq V(G)\) and \(u \notin X\), and let \(P\) be a partition of \(X \cup \{ u\} \). Let \(t\) be the number of edges of \(G\) from \(u\) to a body of \(X\) in a part of \(P\) other than the part of \(u\), and let \(\epsilon = 1\) if \(u\) is alone in its part and \(\epsilon = 0\) otherwise. Then

Consequently, if \(D \ge 3\), \(\operatorname {def}(\tilde G[W]) = 0\) and a body \(u \notin W\) is adjacent to two distinct bodies of \(W\), then \(\operatorname {def}(\tilde G[W \cup \{ u\} ]) = 0\).

1. For a map \(c\) of the bodies, the value of a partition of the image graph \(c(G)\) equals the value of its pull-back along \(c\) to a partition of \(V(G)\).

2. Let \(G\) be sparse, let \(r \in W \subseteq V(G)\), and suppose \(s(W) \le s(X)\) for every \(X\) with \(W \subseteq X \subseteq V(G)\). Let \(G/G[W]\) collapse \(W\) to \(r\) (definition 21.3). Then

   \[ \operatorname {def}_2(G[W]) + \operatorname {def}_2(G/G[W]) \; \le \; \operatorname {def}_2(G). \]

Let \(G\) be a connected multigraph, and let \(d \le d'\) be natural numbers. Then \(\operatorname {def}_{d'}(G) \le \operatorname {def}_d(G)\). In particular \(\operatorname {def}_3(G) \le \operatorname {def}_2(G)\).

Let \(G\) be sparse.

1. Let \(W \subseteq Y \subseteq V(G)\) with \(W\) nonempty and \(\operatorname {def}_3(G[W]) = 0\). If \(s(Y) \le s(W)\), and \(s(W) \le s(Q)\) for every \(Q\) with \(W \subseteq Q \subsetneq Y\), then \(\operatorname {def}_3(G[Y]) = 0\).

2. Let \(W \subseteq V(G)\) be nonempty with \(\operatorname {def}_3(G[W]) = 0\), and let \(X_0\) be empty or a single body outside \(W\) that sends at most two edges into every set avoiding it and at most one into \(W\). Suppose \(W\) is maximal among the sets \(W' \supseteq W\) in \(V(G) \setminus X_0\) with \(\operatorname {def}_3(G[W']) = 0\). Then \(s(W) \le s(X)\) for every \(X\) with \(W \subseteq X \subseteq V(G)\).

Let \(G\) be a multigraph without loops, and let \(V_1\) and \(V_2\) be sets of vertices of \(G\) with \(V_1 \cup V_2 = V(G)\) and \(V_1 \cap V_2 = \{ v\} \), such that every edge of \(G\) lies inside \(V_1\) or inside \(V_2\). Then

Let \(D \ge 1\), let \(G\) be a multigraph, and let \(V_1\) be a set of vertices of \(G\). Let \(a - x_1 - \cdots - x_k - b\) (\(k \ge 1\)) be a path of \(G\) with \(a, b \in V_1\), possibly \(a = b\), and distinct vertices \(x_1, \dots , x_k\) outside \(V_1\), such that \(V(G) = V_1 \cup \{ x_1, \dots , x_k\} \) and every edge of \(G\) off the path lies inside \(V_1\). Then

Let \(G\) be a multigraph, and let \(V_1\) be a set of vertices of \(G\). Let \(a - x_1 - \cdots - x_k - b\) (\(k \ge 0\)) be a walk of \(G\) with \(a, b \in V_1\), possibly \(a = b\), and vertices \(x_1, \dots , x_k\) outside \(V_1\), not necessarily distinct, such that \(V(G) = V_1 \cup \{ x_1, \dots , x_k\} \) and every edge of \(G\) off the walk lies inside \(V_1\). Suppose that some partition of \(V_1\) of value \(\operatorname {def}(\tilde G[V_1])\) has \(a\) and \(b\) in one part. Then

Let \(D \ge 1\) and let \(W \subseteq V(G)\) be nonempty with \(\operatorname {def}(\tilde G[W]) = 0\).

1. For every partition \(P\) of \(V(G)\), some partition \(P'\) coarser than \(P\), with \(W\) inside one of its parts, has \(\operatorname {def}_{\tilde G}(P) \le \operatorname {def}_{\tilde G}(P')\).

2. For all bodies \(a\) and \(b\), \(\operatorname {def}(\tilde G; a, b) \le \operatorname {def}(\tilde G)\), with equality if \(a, b \in W\).

Let \(V_1 \subseteq V(G)\) and \(x \in V(G) \setminus V_1\), and let \(a \neq b\) in \(V_1\) be joined to \(x\) by edges.

1. If \(G\) is sparse, then \(a\) and \(b\) are not adjacent, and \(\operatorname {def}_2(G[V_1]; a, b) + 2 \le \operatorname {def}_2(G[V_1])\).

2. If no set of at least two bodies containing \(x\) is rigid, then \(\operatorname {def}_3(G[V_1]; a, b) + 5 \le \operatorname {def}_3(G[V_1])\).

Let \((G,p)\) be a body-hinge framework with \(V\) nonempty, and suppose that \(C(p(e)) \neq 0\) at every edge \(e\) of \(G\) whose two ends differ. Then

that is, \(\operatorname {rank} R(G,p) \le D(|V|-1) - \operatorname {def}(\tilde G)\).

Let \(P\) be a partition of \(V(G)\) with a part \(Z\), and suppose \(s_D(Y) \ge 0\) for every nonempty \(Y \subseteq V(G) \setminus Z\). Then

In particular, if \(s_D(Y) \ge 0\) for every nonempty \(Y \subseteq V(G)\), then \(\operatorname {def}_{\tilde G}(P) \le s_D(V(G))\) for every partition \(P\) of \(V(G)\).

Let \(X \subseteq V(G)\) with \(|X| \ge 2\) and \(s_D(X) \le 0\). Then some \(Y \subseteq X\) with \(|Y| \ge 2\) has \(\operatorname {def}(\tilde G[Y]) = 0\). Hence, if no set of at least two bodies has deficiency zero, then \(s_D(X) \ge 1\) for every \(X\) with \(|X| \ge 2\); at \(d = 2\), a graph with no planar-rigid set is sparse.

Let \(X \subseteq V(G)\) with \(|X| \ge 3\), and suppose \(s(Z) \ge 1\) for every \(Z \subseteq X\) with \(|Z| \ge 2\). If \(s(X) \le 1\), then \(\operatorname {def}_3(G[X]) = 0\).

Let \(G\) be sparse, and let \(a \neq b\) be bodies of \(G\) that are not adjacent, with \(\operatorname {def}_3(G; a, b) \neq \operatorname {def}_3(G)\). Then \(\operatorname {def}_2(G; a, b) + 2 \le \operatorname {def}_2(G)\).

Let \(D \ge 1\), and let \(G\) be a \(0\)-dof-graph with at least one vertex. Then \(G\) is connected. If \(G\) has at least two vertices, then every vertex of \(G\) has degree at least \(2\).

Let \(D \ge 2\), and let \(G\) be a multigraph with at least one vertex. Then \(\operatorname {def}(\tilde G) = 0\) if and only if \(\tilde G\) contains \(D\) edge-disjoint spanning trees.

Let \(D \ge 2\), and let \(G\) be a \(k\)-dof-graph with a vertex \(v\) of degree two, whose edges \(e_a\) and \(e_b\) join \(v\) to vertices \(a, b \neq v\). Then

Let \(D = \binom {d+1}{2}\), and let \(G\) be a multigraph. Then there is an independent body-hinge framework in \({\mathbb {R}}^d\) on \(G\) if and only if \((D-1)\cdot G\) is \((D, D)\)-sparse. There is a body-hinge framework in \({\mathbb {R}}^d\) on \(G\) that is independent and infinitesimally rigid if and only if \((D-1)\cdot G\) is \((D, D)\)-tight.

Let \((G,p)\) be a body-hinge framework, let \(u \neq v\) be bodies, and let \(r_1, \dots , r_n \in K^D\) be linearly independent. Then the linear forms \(S \mapsto r_i \cdot (S(u) - S(v))\) on screw assignments are linearly independent. In particular, if \(e\) is an edge with ends \(u\) and \(v\) and \(C(p(e)) \neq 0\), then the \(D - 1\) rows of \(e\) are linearly independent.

Let \(D \ge 2\), and let \(G\) be a minimal \(k\)-dof-graph with \(k {\gt} 0\) and no proper rigid subgraph. Then \(E(\tilde G)\) is independent in \(M(\tilde G)\). In particular, \(E(\tilde G)\) is the only base of \(M(\tilde G)\).

Let \(D \ge 2\), and let \(G\) be a multigraph with a vertex \(v\) of degree two, whose edges \(e_a\) and \(e_b\) join \(v\) to distinct vertices \(a, b \neq v\). Let \(I'\) be an independent set of \(M(\widetilde{G_v^{ab}})\), and let \(h' = |\widetilde{ab} \cap I'|\). Then \(M(\tilde G)\) has an independent set \(I\) with

such that (i) if \(h' {\lt} D - 1\), then \(|I| = |I'| + D\) and \(|\tilde e_b \cap I| = h' + 1\), and (ii) if \(h' = D - 1\), then \(|I| = |I'| + D - 1\).

Let \(G\) be a graph on a finite set \(V\), let \(I \subseteq E(G)\), and let \(p_0\) be a framework on \(V\) in \({\mathbb {R}}^{d}\) at which \(I\) is row-independent. Then \(I\) is row-independent at every framework in some neighbourhood of \(p_0\) in \(({\mathbb {R}}^{d})^{V}\).

Let \(G\) and \(H\) be graphs on sets \(V\) and \(W\), let \(\varphi \) be an isomorphism from \(G\) to \(H\), and let \(q\) be a framework on \(W\) in \({\mathbb {R}}^{d}\). If \(E(H)\) is row-independent at \(q\), then \(E(G)\) is row-independent at \(q \circ \varphi \).

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})^{*}\).

Let \(v \in V\) and \(S \subseteq V\). Then \(E_{G}[V] = E(G)\), \(E_{G}[\emptyset ] = \emptyset \) and \(E_{G}[\{ v\} ] = \emptyset \). If \(G\) has no edges, then \(E_{G}[S] = \emptyset \).

Let \(S, T \subseteq V\). Then \(E_{G}[S \cap T] = E_{G}[S] \cap E_{G}[T]\).

Let \(S \subseteq T \subseteq V\). Then \(E_{G}[S] \subseteq E_{G}[T]\).

Let \(V\) be finite and let \(S, T \subseteq V\). Then

Let \(G'\) be \(G\) with its edges relabelled by an injective map \(\iota \) (definition 23.41), let \((G', p')\) be a body-hinge framework, and let \((G, p)\) be the body-hinge framework with \(p(e) = p'(\iota (e))\) for every edge label \(e\) of \(G\). Then the rigidity matrices of \((G, p)\) and \((G', p')\) have the same rows, and the two frameworks have the same infinitesimal motions. If \((G', p')\) is a panel-hinge framework with normals \(n_v\), then \((G, p)\) is the panel-hinge framework on \(G\) with the normals \(n_v\).

Let \(G\) be a minimal \(k\)-dof-graph and \(G'\) be \(G\) with its edges relabelled injectively (definition 23.41). Then \(G'\) is a minimal \(k\)-dof-graph. Moreover, for \(D \ge 1\), every minimal \(k'\)-dof-graph on the bodies of \(G\) with labels in \(L \sqcup \{ 1, \dots , D(|W| - 1) + 1\} \) has a label outside its edge set, for every \(k'\).

Let \(G'\) be \(G\) with its edges relabelled by an injective map \(\iota \) (definition 23.41). Then \(G'\) is simple if \(G\) is, and \(\operatorname {def}_d(G') = \operatorname {def}_d(G)\) for every \(d\).

Let \(G\) be a finite multigraph, and let \(E' \subseteq E(G)\) be a set of bars such that \(G \restriction E'\) is \((D, D)\)-sparse. Then there is an endpoint assignment of \(G\) at whose endpoint realization the rows of the bars in \(E'\) are linearly independent.

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}\).

Let \(G\) be a finite multigraph. Then some endpoint assignment of \(G\) is generic for row independence.

Let \(V\) be finite. Then there is a placement \(p \colon V \to {\mathbb {R}}^3\) that is generic for row independence (definition 24.1) and in general position up to order four.

Let \(K\) be infinite, and let \(G = (V, E)\) be a multigraph with \(V\) and \(E\) finite. Then some hinge-point assignment of \(G\) is generic for row independence and gives each edge \(d - 1\) affinely independent points.

Let \(K\) be infinite, and let \(G = (V, E)\) be a multigraph with \(V\) and \(E\) finite. Then some normal assignment of \(G\) is generic for row independence.

Let \(V\) be finite and \(d \in {\mathbb {N}}\). Then there is a placement of \(V\) in \({\mathbb {R}}^{d}\) that is generic for row independence.

Let \(m \le D\). Then there are \(a_i, b_i \in K^{d+1}\) for \(1 \le i \le m\) such that the extensors \(C(a_i, b_i)\) are linearly independent, and so are the joins \(a_i \vee b_i\).

Let \(G\) be a \((k, \ell )\)-sparse graph on a set \(V\), which need not be finite, and let \(u\) and \(v\) be distinct vertices that are not adjacent in \(G\). Let \(G + uv\) be obtained from \(G\) by adding the edge \(uv\). If \(G + uv\) is not \((k, \ell )\)-sparse, then some set containing \(u\) and \(v\) is \((k, \ell )\)-tight in \(G\).

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 \(G\) be a multigraph whose vertex set is finite and nonempty. Then some partition \(P\) of \(V(G)\) is tight, that is, \(\operatorname {def}_{\tilde G}(P) = \operatorname {def}(\tilde G)\).

Let \(V\) be finite. Then there is a framework \(p\) on \(V\) in \({\mathbb {R}}^{2}\) such that every \(I \subseteq E(K_V)\) is row-independent at \(p\) whenever the graph on \(V\) with edge set \(I\) is \((2, 3)\)-sparse.

Let \(u_1, \dots , u_{d-1} \in K^{d+1}\), and suppose that some \(u_i\) has nonzero last coordinate. Then there are points \(p_1, \dots , p_{d-1}\) of \(K^d\) and a nonzero scalar \(c\) with

Let \(d \ge 2\) and let \(C \neq 0\) be an extensor that lies in the panel with normal \(n\) (definition 23.24). Then \(C = x_1 \vee \cdots \vee x_{d-1}\) for some vectors \(x_1, \dots , x_{d-1}\) of \(K^{d+1}\), with \(x_1 \neq 0\).

Let \(p_1, \dots , p_{d+1} \in K^{d}\) be affinely independent. Then the \(D = \binom {d+1}{2}\) extensors

are linearly independent in \(\bigwedge ^{d-1} K^{d+1}\), where a hat marks an omitted vector.

Let \((G, b)\) be a body-bar framework in \({\mathbb {R}}^d\), and let \(M\) be an invertible linear map of \({\mathbb {R}}^D\). Let \((G, Mb)\) be the framework with the vector \(M b_e\) on each bar \(e\). If the rows of a set of bars are linearly independent in \((G, b)\), then they are linearly independent in \((G, Mb)\).

Let \(n \in K^4\). Then there are vectors \(p_0, p_1, q_0, q_1\) in \(n^{\perp } = \{ x \in K^4 : x \cdot n = 0\} \) such that the extensors \(p_0 \vee p_1\) and \(q_0 \vee q_1\) are linearly independent in \(\bigwedge ^2 K^4\).

For any normal \(n \in K^4\) and any nonzero point \(q \in n^{\perp }\), there are two screw elements \(C, C' \in \bigwedge ^{2} K^{4}\), each lying in the panel with normal \(n\) (definition 23.24) and passing through \(q\) (definition 29.1), whose \(2\)-extensors are linearly independent.

For any normal \(n \in K^4\) there is a nonzero point \(q \in n^{\perp }\) and two screw elements \(C, C' \in \bigwedge ^{2} K^{4}\), each lying in the panel with normal \(n\) (definition 23.24) and passing through \(q\) (definition 29.1), whose \(2\)-extensors are linearly independent.

Let \((G,p)\) be a body-hinge framework, and let \(t\) be a set of bodies with \(V(G) \cap t = \{ r\} \). Then every screw assignment is the sum of an infinitesimal motion of \((G,p)\) and a screw assignment that vanishes on \(t\). Hence \(\pi _t\) is injective on the row space of \(R(G,p)\), and deleting the columns of \(t\) from \(R(G,p)\) does not change its rank.

Let \(G\) be a multigraph. A set \(I\) of edges of \(\tilde G\) is independent in \(M(\tilde G)\) if and only if \(I = F_1 \cup \dots \cup F_D\) for some forests \(F_1, \dots , F_D\) of \(\tilde G\).

Let \((G,p)\) be a body-hinge framework, and let \(T\) be a forest with finitely many edges that is a subgraph of \(G\), with \(C(p(e)) \neq 0\) at each edge \(e\) of \(T\). Then \(R(G,p)\) has \((D-1)|E(T)|\) linearly independent rows.

Let \(D \ge 2\), and let \(G\) be a multigraph with a vertex \(v\) of degree two, whose edges \(e_a\) and \(e_b\) join \(v\) to distinct vertices \(a, b \neq v\). Let \(F_1, \dots , F_D\) be pairwise disjoint forests of \(\tilde G\), each of which has an edge incident with \(v\), and let \(I\) be their union. Then there are pairwise disjoint forests \(F'_1, \dots , F'_D\) of \(\widetilde{G_v^{ab}}\) whose union \(I'\) is independent in \(M(\widetilde{G_v^{ab}})\) and satisfies

Let \(D \ge 2\), and let \(G\) be a multigraph with a vertex \(v\) of degree two, whose edges join \(v\) to distinct vertices \(a, b \neq v\). Then

Let \(D \ge 2\), and let \(G\) be a multigraph with a vertex \(v\) of degree two, whose edges \(e_a\) and \(e_b\) join \(v\) to distinct vertices \(a, b \neq v\). Let \(I'\) be an independent set of \(M(\widetilde{G_v^{ab}})\) that contains no copy of \(ab\). Then \(M(\tilde G)\) has an independent set \(I\) with \(I \setminus (\tilde e_a \cup \tilde e_b) = I'\), \(|I| = |I'| + D\) and \(|\tilde e_b \cap I| = 1\).

Let \(V\) be finite. Then \(\dim _{{\mathbb {R}}} ({\mathbb {R}}^{d})^{V} = d\, |V|\).

Let the normals of a panel-hinge framework \((G, n)\) be in general position. Then every edge of \(G\) with two distinct ends has a nondegenerate hinge.

Let \(G\) be a finite multigraph. Then there is a nonzero polynomial \(P\) in the \(2d\, |E(G)|\) endpoint coordinates such that every endpoint assignment \(q\) of \(G\) with \(P(q) \neq 0\) is generic for row independence. In particular, the endpoint assignments that are not generic lie in the zero set of a nonzero polynomial.

Let \(G = (V, E)\) be a multigraph with \(V\) and \(E\) finite. Then there is a nonzero polynomial \(P\) in the \(d(d-1)|E|\) coordinates of a hinge-point assignment such that every hinge-point assignment \(q\) with \(P(q) \neq 0\) is generic for row independence and gives each edge \(d - 1\) affinely independent points. In particular, the hinge-point assignments that are not generic, or that give some edge affinely dependent points, lie in the zero set of a nonzero polynomial.

Let \(d \ge 2\), let \(G\) be a multigraph with \(V\) and \(E\) finite, loops allowed, and let \(q\) be a hinge-point assignment of \(G\) that is generic for row independence. Then \((G, q)\) is generic in the sense of definition 19.16. If \(K\) is infinite, some hinge-point assignment of \(G\) is generic in this sense.

Let \(d \ge 2\), and let \(G = (V, E)\) be a multigraph, with parallel edges and loops allowed. Let \(q\) be a hinge-point assignment of \(G\) that is generic for row independence. Then the hinge of \((G, q)\) at every edge with two distinct ends is nondegenerate.

Let \(G = (V, E)\) be a multigraph with \(V\) and \(E\) finite. Then there is a nonzero polynomial \(P\) in the \((d+1)|V|\) coordinates of a normal assignment such that every normal assignment \(q\) with \(P(q) \neq 0\) is generic for row independence. In particular, the normal assignments that are not generic lie in the zero set of a nonzero polynomial.

Let \(d \ge 2\), and let \(G = (V, E)\) be a multigraph without loops. Let \(q\) be a normal assignment of \(G\) that is generic for row independence. Then every hinge of \((G, q)\) is nondegenerate.

Let \(V\) be finite and \(d \in {\mathbb {N}}\). Then there is a nonzero real polynomial \(P\) in the \(d\, |V|\) coordinates of a placement of \(V\) in \({\mathbb {R}}^{d}\) such that every placement \(p\) with \(P(p) \neq 0\) is generic for row independence. In particular, the placements that are not generic lie in the zero set of a nonzero polynomial.

Let \(K\) be an infinite field, and let \(G\) be a multigraph with \(V(G) \neq \emptyset \) and \(\operatorname {def}(\tilde G) = 0\). Suppose that some panel-hinge realization \((G, q_0)\) of \(G\) has a nondegenerate hinge at every edge and is infinitesimally rigid on \(V(G)\). Then \(G\) has a generic full-rank realization.

Let \(d \ge 2\), and let \(G = (V, E)\) be a multigraph with \(|V| \ge 2\). If \(G\) has a generic full-rank realization (definition 23.21), then \(G\) has a nondegenerate-hinge panel realization (definition 23.24).

Let \(K\) be an infinite field and let \(G\) be a multigraph. Regard the normals \(q\) of the panel-hinge frameworks \((G,q)\) on a finite set \(W\) of bodies as the points of \(K^N\), where \(N = (d+1)|W|\), and let \(U\) be the set of the \(q\) at which every hinge of \((G,q)\) is nondegenerate (definition 23.5). Then \(U\) is Zariski-open, and for each \(r\), the set of the \(q \in U\) with \(\operatorname {rank} R(G,q) \ge r\) is Zariski-open; that is, the rank is lower semicontinuous on \(U\). The rank is at least its value at a given \(q_0 \in U\) on a dense Zariski-open set contained in \(U\), and if \(U\) is not empty, the largest rank on \(U\) is attained on such a set. Equivalently, \(\dim Z(G,q) = D|W| - \operatorname {rank} R(G,q)\) is upper semicontinuous on \(U\), and its least value on \(U\) is attained on a dense Zariski-open set contained in \(U\).

Let \(d \in {\mathbb {N}}\), let \(S \subseteq V\), and let \(H\) be a graph on \(S\). Then \(E(H)\) is independent in \(\mathcal{R}_d(S)\) if and only if its image under the inclusion \(S \hookrightarrow V\) is independent in \(\mathcal{R}_d(V)\). The rank of \(E(H)\) in \(\mathcal{R}_d(S)\) equals the rank of its image in \(\mathcal{R}_d(V)\).

Let \(p\) be a placement of \(V\) in \({\mathbb {R}}^{d}\) that is generic for row independence, and let \(H\) be a graph on \(V\). Then

where \(r_e\) is the rigidity row of \(K_V\) at \(p\) indexed by \(e\) (definition 9.4).

Let \(I \subseteq E(K_V)\). Then \(I\) is independent in \(\mathcal{R}_d(V)\) if and only if \(I\) is row-independent at some placement of \(V\) in \({\mathbb {R}}^{d}\).

The generic rigidity matroid \(\mathcal{R}_2(V)\) is the planar rigidity matroid \(\mathcal{R}(V)\), the \((2,3)\)-count matroid on \(V\) (definition 10.12).

Let \(d \ge 2\), let \(K\) be an infinite field, and let \(G = (V, E)\) be a multigraph, with parallel edges and loops allowed, with \(V\) finite and nonempty. Then there is a hinge-point assignment \(q\) of \(G\) at which some \(D(|V|-1) - \operatorname {def}(\tilde G)\) members of the annihilator-row family of \(q\) are linearly independent.

Let \(G = (V, E)\) be a multigraph with \(E\) finite, let \(e\) be an edge of \(G\), and let \(t\) be an index of the standard basis of \(\bigwedge ^{d-1}K^{d+1}\). Then there is a polynomial in the \(d(d-1)|E|\) coordinates of a hinge-point assignment of \(G\) whose value at every hinge-point assignment \(q\) is the coordinate \(C(q_e)_t\) of \(C(q_e)\) at the \(t\)-th basis vector.

Let \((G,p)\) be a body-hinge framework whose hinges are nondegenerate. At each edge \(e\) of \(G\), with ends \(u\) and \(w\), take the linear forms \(S \mapsto C_t\, x_{t'} - C_{t'}\, x_t\), where \(C = C(p(e))\) and \(x = S(u) - S(w)\), for all pairs of indices \(t\) and \(t'\), as in lemma 23.91. If \(N \le \operatorname {rank} R(G,p)\), then some \(N\) of these forms are linearly independent.

Let \(A\) be a skew-symmetric linear map of \({\mathbb {R}}^{d}\), and let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\). Then \(A \circ p \in \ker R(G, p)\).

Let \(1 \le i, j \le d\). Then \(\langle y, (E_{ij} - E_{ji}) y \rangle = 0\) for every \(y \in {\mathbb {R}}^{d}\), that is, \(E_{ij} - E_{ji}\) is skew-symmetric.

Let \(V\) be finite, and let \(G\) be generically rigid in dimension \(2\). Then

Let \(V\) and \(W\) be finite, and let \(\varphi \) be an isomorphism from \(G\) to a graph \(H\) on \(W\). If \(G\) is generically rigid in dimension \(d\), then so is \(H\).

Let \(V\) be finite, and let \(G'\) be a graph on \(V\) with \(E(G) \subseteq E(G')\). If \(G\) is generically rigid in dimension \(d\), then so is \(G'\).

Let \(V\) and \(W\) be finite, and let \(\varphi \) be an isomorphism from \(G\) to a graph \(H\) on \(W\). If \(G\) is injectively generically rigid in dimension \(d\), then so is \(H\).

Let \(V\) be finite, and let \(G'\) be a graph on \(V\) with \(E(G) \subseteq E(G')\). If \(G\) is injectively generically rigid in dimension \(d\), then so is \(G'\).

Let \(V\) be finite, and let \(p_0\) be a framework on \(V\) in \({\mathbb {R}}^{d}\) that is infinitesimally rigid for \(G\). Then every framework in some neighbourhood of \(p_0\) in \(({\mathbb {R}}^{d})^{V}\) is infinitesimally rigid for \(G\).

Let \(V\) and \(W\) be finite, let \(\varphi \) be an isomorphism from \(G\) to a graph \(H\) on \(W\), and let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\). If \(p\) is infinitesimally rigid for \(G\), then \(p \circ \varphi ^{-1}\) is infinitesimally rigid for \(H\).

Let \(V\) be finite, let \(G'\) be a graph on \(V\) with \(E(G) \subseteq E(G')\), and let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\). If \(p\) is infinitesimally rigid for \(G\), then \(p\) is infinitesimally rigid for \(G'\).

Let \((G,p)\) be a body-hinge framework whose screw assignments are defined on a finite set \(W\) of bodies with \(\emptyset \neq V(G) \subseteq W\). If

then every infinitesimal motion of \((G,p)\) is constant on \(V(G)\).

Let \(G\) be a Laman graph on a set \(V\) of two vertices. Then \(G\) is the complete graph on \(V\).

Let \(V\) be finite with \(|V| \ge 3\), and let \(G\) be a Laman graph on \(V\). Then some vertex of \(G\) has degree \(2\) or \(3\).

Let \(\varphi \) be an isomorphism from \(G\) to a graph \(H\). If \(G\) is Laman, then so is \(H\).

Let \(V\) be finite with \(|V| \ge 3\), and let \(G\) be a Laman graph on \(V\). Then every vertex of \(G\) has degree at least \(2\).

Let \(G\) be a graph such that \(G^2\) is Laman. Then every vertex of \(G\) has degree at most three.

Let \(G\) be a Laman graph on \(V\), and let \(S \subseteq V\). Then the induced subgraph \(G[S]\) is Laman.

A subgraph of a Laman graph is Laman.

Let \(p\) be a placement of \(V\) in \({\mathbb {R}}^3\) such that, for every set \(S\) of at least four vertices, the points \(p(v)\), \(v \in S\), affinely span \({\mathbb {R}}^3\). Let \(H\) be a graph on \(V\) whose edge set is row-independent at \(p\). Then \(H\) is Laman.

Let \(\varphi \) be an isomorphism from \(G\) to a graph \(H\), and let \(s \subseteq V\). Then

where \(\varphi \) maps a pair \(\{ u, v\} \) of vertices to \(\{ \varphi (u), \varphi (v)\} \).

Let \(V\) be finite, let \(\ell {\lt} 2k\), and let \(I, J \subseteq E(K_V)\) be \((k, \ell )\)-sparse with \(|I| {\lt} |J|\). Then there is an edge \(e \in J \setminus I\) such that \(I \cup \{ e\} \) is \((k, \ell )\)-sparse.

Let \(V\) be finite, and let \(G\) be \((k,\ell )\)-sparse with \(\ell \le k\, |V|\). Then

Let \(V\) be finite with \(|V| \ge 2\), and let \(G\) be \((2,3)\)-sparse. Then some vertex of \(G\) has degree at most \(3\).

Let \(V\) be finite and let \(G\) be \((2,3)\)-sparse. Suppose that \(v \in V\) has three pairwise distinct neighbors \(a, b, c\). Then at least one of the pairs \(\{ a, b\} \), \(\{ a, c\} \), \(\{ b, c\} \) is non-adjacent in \(G\).

Let \(\varphi \) be an isomorphism from \(G\) to a graph \(H\). If \(G\) is \((k,\ell )\)-sparse, then so is \(H\).

Let \(G\) be \((k,\ell )\)-sparse, and let \(s \subseteq V\) be a finite set with \(\ell \le k\, |s|\) and

Then \(s\) is \((k,\ell )\)-tight in \(G\).

Let \(V\) be finite, let \(\ell {\lt} 2k\), and let \(G\) be a \((k, \ell )\)-sparse graph on \(V\). Let \(X, Y \subseteq V\) each have at least two elements. Suppose that some \((k, \ell )\)-tight set of \(G\) contains \(X\), and that \(Y \subseteq C_G(X)\). Then \(C_G(Y) = C_G(X)\). In particular, two distinct components of \(G\) share at most one vertex, and so no edge.

Let \(V\) be finite, let \(\ell {\lt} 2k\), and let \(G\) be a \((k, \ell )\)-sparse graph on \(V\). Let \(X \subseteq V\) have at least two elements, and suppose that some \((k, \ell )\)-tight set of \(G\) contains \(X\). Then \(C_G(X)\) is \((k, \ell )\)-tight in \(G\).

Let \(G'\) be a graph on \(V\) with \(E(G) \subseteq E(G')\). If \(G'\) is \((k,\ell )\)-sparse, then so is \(G\).

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 \(V\) be finite, let \(G\) be \((2,3)\)-sparse, and let \(v\), \(x\) and \(y\) be vertices of \(G\) with \(x, y \ne v\). Let \(G - v + xy\) be the graph on \(V \setminus \{ v\} \) obtained from \(G\) by deleting \(v\) and adding the edge \(xy\). If \(G - v + xy\) is not \((2,3)\)-sparse, then some set \(S \subseteq V \setminus \{ v\} \) that contains \(x\) and \(y\) is \((2,3)\)-tight in \(G\).

Let \(\varphi \) be an isomorphism from \(G\) to a graph \(H\). If \(G\) is \((k,\ell )\)-tight, then so is \(H\).

Let \(V\) be finite, let \(G\) be \((k,\ell )\)-tight, and let \(H\) be a graph on \(V\) with \(E(G) \subsetneq E(H)\). Then \(H\) is not \((k,\ell )\)-sparse.

Let \(V\) be finite, let \(\ell {\lt} 2k\), and let \(G\) be a \((k, \ell )\)-sparse graph on \(V\). Let \(s, t \subseteq V\) be \((k, \ell )\)-tight in \(G\), and suppose that two distinct vertices \(u\) and \(v\) lie in both \(s\) and \(t\). Then \(s \cup t\) and \(s \cap t\) are \((k, \ell )\)-tight in \(G\).

Let \(E' \subseteq E(G)\) be a set of bars such that \(G \restriction E'\) is \((k, k)\)-sparse. Then \(E' = F_1 \cup \dots \cup F_k\) for some pairwise disjoint forests \(F_1, \dots , F_k\) of \(G\).

Let \(M\) be a matroid of finite rank, represented over a field by vectors \(v_e\): a set \(I\) is independent in \(M\) if and only if the vectors \(v_e\), \(e \in I\), are linearly independent. Then for every set \(Y\) of elements of \(M\), the span of \(\{ v_e : e \in Y\} \) has dimension \(r_M(Y)\). In particular, for every set \(Y\) of bars of \(G\), the span over \(K\) of \(\{ a_e : e \in Y\} \) has dimension \(r(Y)\).

Let \(E' \subseteq E(G)\) be a set of bars. Then \(E'\) is independent in \(F(G, X)\) if and only if \(G \restriction E'\) is \((k, k)\)-sparse.

Let \(E' \subseteq E(G)\) be a set of bars. Then the \(k\)-frame rows of the bars in \(E'\) are linearly independent over \(K\) if and only if they are linearly independent over \(R\).

Let \(E' \subseteq E(G)\) be a set of bars whose \(k\)-frame rows are linearly independent over \(K\). Then \(|Y| \le k\, r(Y)\) for every \(Y \subseteq E'\).

Let \(W\) be a finite-dimensional subspace of a vector space \(U\) over \(K\). Then \(\dim W^k = k \dim W\).

Let \(A\) be the span over \(K\) of the signed incidence vectors of the bars of \(G\). Then the \(k\)-frame row of every bar lies in \(A^k\), and hence so does the span of all \(k\)-frame rows.

Let \(E' \subseteq E(G)\) be a set of bars such that \(G \restriction E'\) is \((k, k)\)-sparse. Then the \(k\)-frame rows of the bars in \(E'\) are linearly independent over \(K\).

Let \(F_1, \dots , F_k\) be pairwise disjoint forests of \(G\), and let \(\varphi \colon R \to {\mathbb {Q}}\) be the ring homomorphism with \(\varphi (X_{e,j}) = 1\) if \(e \in F_j\) and \(\varphi (X_{e,j}) = 0\) otherwise. Let \(e \in F_{j_0}\). Then applying \(\varphi \) to each entry of \(\rho _e\) gives \(a_e^{(j_0)}\).

Let \(F_1, \dots , F_k\) be forests of \(G\). Then the vectors \(a_e^{(j)}\), one for each pair \((j, e)\) with \(e \in F_j\), are linearly independent over \(K\).

Let \(p\) be a placement of \(V\) in \({\mathbb {R}}^{d}\) that is generic for row independence. Then \(\mathcal{L}_p(V) = \mathcal{R}_d(V)\).

Let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\), and let \(I \subseteq E(K_V)\). Then \(I\) is independent in \(\mathcal{L}_p(V)\) if and only if \(I\) is row-independent at \(p\).

Let \(D \ge 3\), and let \(G\) be a minimal \(k\)-dof-graph with at least one vertex and no proper rigid subgraph. Then \(G\) has a vertex of degree at most two.

Let \(H\) be a subgraph of a multigraph \(G\). Then \(M(\tilde H)\) is the restriction of \(M(\tilde G)\) to \(E(\tilde H)\):

Let \(d \ge 1\), let \(n_1, n_2 \in V\), and let \(W\) be a \((d-1)\)-dimensional subspace of \(V\) whose vectors are orthogonal to \(n_1\) and \(n_2\). Then \(*(n_1 \vee n_2)\) lies in the image of the map \(\bigwedge ^{d-1} W \to \bigwedge ^{d-1} V\) induced by the inclusion of \(W\) in \(V\). If moreover \(n_1\) and \(n_2\) are linearly independent, and \(p_1, \dots , p_{d-1} \in V\) are linearly independent and orthogonal to \(n_1\) and \(n_2\), then \(p_1 \vee \cdots \vee p_{d-1} = c\, {*(n_1 \vee n_2)}\) for some \(c \in K\).

Let \(V\) and \(G\) be as in definition 14.3, and let \(u, v \in V\). Then \((u, v)\) is an entry of the sorted edge list of \(G\) if and only if \(u \le v\) and \(uv \in E(G)\).

Let \(v \in V\). Then

that is, a pair \(e\) of vertices lies in \(E_{G}[\{ v\} ^c]\) if and only if \(e \in E(G)\) and \(v \notin e\).

Let \(V\) and \(D\) be as in definition 14.1, and let \(u, v \in V\). Then \(u\) is an entry of the sorted out-neighbour list of \(v\) in \(D\) if and only if \((v, u) \in D\).

Let \(V\) and \(R\) be as in definition 12.2, and let \(v, w \in V\). Then \(w \in \mathrm{Reach}_R(v)\) if and only if \(w\) is reachable from \(v\) along \(R\).

Let \(D \ge 1\), and let \(G\) be a multigraph with at least one vertex. Then \(G\) has a spanning subgraph that is a minimal \(\operatorname {def}(\tilde G)\)-dof-graph.

Let \(G\) be a simple graph on a finite set \(V\). Then there is a simple multigraph \(G'\) with vertex set \(V\), in which two distinct vertices are joined by an edge if and only if they are adjacent in \(G\).

Let \(G\) be a simple graph of minimum degree at least two on a finite, nonempty vertex set \(V\). Then \(3|V| - 6 - \operatorname {def}(\tilde G) \le r(G^2)\).

Let \(G\) be a simple graph of minimum degree at least two on a finite, nonempty vertex set \(V\). Then \(r(G^2) \le 3|V| - 6 - \operatorname {def}(\tilde G)\).

Let \((t_v)_{v \in V}\) be distinct elements of \(K\), and let \(n_v = (1, t_v, t_v^2, \dots , t_v^{d})\) be the point of the moment curve at \(t_v\). Then the normals \(n_v\) are in general position, and if \(d \ge 2\), their panels are nonparallel. In particular, if \(K\) is infinite and \(V\) is finite, then there are normals in general position, and for \(d \ge 2\) there are nonparallel panels.

Let \((G,p)\) be a body-hinge framework, and let \(G'\) be a subgraph of \(G\). Then \(Z(G,p) \subseteq Z(G',p)\). In particular, \(\dim Z(G,p) \le \dim Z(G',p)\), that is, \(\operatorname {rank} R(G',p) \le \operatorname {rank} R(G,p)\).

Let \(V\) be finite and let \(v \in V\). Then

Let \(D \ge 2\), and let \(G\) be a minimal \(k\)-dof-graph with at least one vertex and no proper rigid subgraph. Then

Let \(K\) be an infinite field, let \(d \ge 2\), and let \(G = (V, E)\) be a multigraph without loops, with \(V \neq \emptyset \). If \(G\) has a generic full-rank realization, then \(G\) has a nonparallel full-rank realization (definition 23.21).

Let \(G\) and \(P\) be as above, and let \(A\) be a part of \(P\) with \(|A| \ge 3\). Then the normal cross edges rooted at \(A\) (definition 27.17) number exactly \(2\, d_G(A)\).

Let \(G\) and \(P\) be as above, let \(A\) be a part of \(P\) with \(|A| \ge 3\), and let \(vw\) be an edge of \(G\) with \(v \in A\) and \(w \notin A\). Then the edges \(uw\) with \(u \in N_G(v) \cap A\), which are normal cross edges rooted at \(A\) (lemma 27.21), number exactly two.

Let \(G\) and \(P\) be as above, let \(A\) be a part of \(P\) with \(|A| \ge 3\), and let \(v \in A\) have a neighbor outside \(A\). Then \(v\) has exactly two neighbors in \(A\).

Let \(G\) and \(P\) be as above, and let \(A\) be a part of \(P\). Then \((v, w) \mapsto vw\) is a bijection from the pairs \((v, w)\) leaving \(A\) (definition 27.23) onto the \(d_G(A)\) edges of \(G\) with exactly one endpoint in \(A\). The normal cross edges rooted at \(A\) are the union, over these pairs \((v, w)\), of the sets \(\{ uw : u \in N_G(v) \cap A\} \), and the sets of two distinct pairs are disjoint.

Let \(G\) and \(P\) be as above, let \(v\) be a vertex of \(G\), and let \(u\) and \(w\) be neighbors of \(v\) with \(u\) in the part of \(v\) and \(w\) outside it. Then \(uw\) is a normal cross edge rooted at the part of \(v\), and \(v\) is the only common neighbor of \(u\) and \(w\).

Let \(G\) and \(P\) be as above. Then every normal cross edge is rooted at exactly one part, and this part has at least three vertices.

Let \((G,p)\) be a body-hinge framework. Let \(u_1, \dots , u_m\) be distinct bodies, and let \(w_1, \dots , w_m\) be bodies none of which is equal to any \(u_j\). For each \(j\), let \(r_{j,1}, \dots , r_{j,n_j} \in K^D\) be linearly independent. Then the linear forms \(S \mapsto r_{j,i} \cdot (S(u_j) - S(w_j))\) on screw assignments are linearly independent. In particular, if \(e_j\) is an edge with ends \(u_j\) and \(w_j\) and \(C(p(e_j)) \neq 0\) for each \(j\), then the \((D-1)m\) rows of \(e_1, \dots , e_m\) are linearly independent.

Let \(G\) be a multigraph with a vertex \(v\) of degree two, and let \(F_1, \dots , F_D\) be forests of \(\tilde G\) with union \(I\). Suppose that no edge of \(F_j\) is incident with \(v\), and let \(x \in I\) be an edge of \(\tilde G\) that joins \(v\) to a vertex \(w \neq v\). Then the sets \(F'_j = F_j \cup \{ x\} \) and \(F'_i = F_i \setminus \{ x\} \) for \(i \neq j\) are forests of \(\tilde G\) with union \(I\).

Let \(*\) be the polarity of \(\bigwedge ^2 {\mathbb {R}}^4\).

1. Let \(G\) be a multigraph on \(V\), and let \(c \colon V \to {\mathbb {R}}^3\). The panel-hinge framework on \(G\) with normals \(\bar c(v)\) (definition 23.5) is obtained from the molecular framework on \((G, c)\) (definition 25.3) by applying \(*\) to the supporting extensor at every edge. Hence the two frameworks have motion spaces of the same dimension and rigidity matrices of the same rank. One of them is infinitesimally rigid if and only if the other is, and the hinge at an edge is nondegenerate in one if and only if it is nondegenerate in the other.

2. The conclusions of (1) also hold for the panel-hinge framework on \(G\) with normals \(\lambda _v\, \bar c(v)\), for any nonzero scalars \(\lambda _v\). Its motion space is that of the panel-hinge framework with normals \(\bar c(v)\).

Let \(a_i, b_i \in K^{d+1}\) for \(1 \le i \le m\). Then the extensors \(C(a_i, b_i)\) with \(1 \le i \le m\) are linearly independent if and only if the joins \(a_i \vee b_i\) are linearly independent in \(\bigwedge ^2 K^{d+1}\).

Let \(d \ge 2\), and let \(n_1, n_2 \in K^{d+1}\) be linearly independent. Then there are \(x_1, \dots , x_{d-1} \in n_1^\perp \cap n_2^\perp \) with

Let \(G = (V, E)\) be a multigraph with \(V\) and \(E\) finite, and let \((G, q)\) be a panel-hinge framework whose hinges are all nondegenerate. Then for every \(N \le \operatorname {rank} R(G, q)\), some \(N\) members of the annihilator-row family of \(q\) are linearly independent.

Let \(G\) be a multigraph, let \(P\) be a partition of \(V(G)\), and let \(Q \subseteq P\) be nonempty. Let \(P'\) be the partition obtained from \(P\) by merging the members of \(Q\) into a single part. Then

where \(e_G(Q)\) is the number of edges of \(G\) that join distinct members of \(Q\) (definition 27.6).

Let \(V\) be a set, let \(k\) and \(\ell \) be non-negative integers, and let \(D\) be a \((k, \ell )\)-reachable partial orientation on \(V\). Let \(u \ne v\) be vertices, and let \(V' \subseteq V\) be a finite set that contains \(u\) and \(v\) and that no arc of \(D\) leaves, that is, \(\mathrm{out}_D(V') = 0\). Suppose that

Then \(\mathrm{peb}_{D, k}(w) \ge 1\) for some vertex \(w \in V'\) other than \(u\) and \(v\).

Let \(V\) be a finite set, let \(k\) and \(\ell \) be non-negative integers with \(\ell {\lt} 2k\), and let \(D\) be a \((k, \ell )\)-reachable partial orientation on \(V\). Let \(u \ne v\) be vertices such that the edge \(uv\) is not oriented in \(D\) and the graph on \(V\) with edge set \(\underline{D} \cup \{ uv\} \) is \((k, \ell )\)-sparse. If \(\mathrm{peb}_{D, k}(u) + \mathrm{peb}_{D, k}(v) \le \ell \), then \(\mathrm{peb}_{D, k}(w) \ge 1\) for some vertex \(w \ne u, v\) that is reachable from \(u\) or from \(v\) along the arcs of \(D\).

Let \(V\) be a set, let \(k\) and \(\ell \) be non-negative integers, and let \(D\) be a \((k, \ell )\)-reachable partial orientation on \(V\). Let \(v \in V\), and let \(V' \subseteq V\) be a finite set. Then:

1. \(\mathrm{peb}_{D, k}(v) + \mathrm{out}_D(v) = k\);

2. \(\mathrm{peb}_{D, k}(V') + \mathrm{span}_D(V') + \mathrm{out}_D(V') = k|V'|\);

3. if \(\ell \le k|V'|\), then \(\mathrm{peb}_{D, k}(V') + \mathrm{out}_D(V') \ge \ell \);

4. if \(\ell \le k|V'|\), then \(\mathrm{span}_D(V') \le k|V'| - \ell \).

Let \(V\), \(k\), \(\ell \) and the lists \(N^+_D(a)\) be as in definition 13.12. Let \(D\) be a \((k, \ell )\)-reachable partial orientation on \(V\), and let \(u \ne v\) be vertices such that the edge \(uv\) is not oriented in \(D\). If processing \(uv\) at \(D\) accepts \(uv\), then the graph on \(V\) with edge set \(\underline{D} \cup \{ uv\} \) is \((k, \ell )\)-sparse.

Every loopless multigraph with at most two vertices has a pencil realization at the deficiency rank (definition 29.13).

Let \(h, h' \in K^3\), and let \(c \in \bigwedge ^2 K^4\) have \(\langle c, u \vee v \rangle = 0\) for every \(u \in \hat\pi _h\) and every \(v \in \hat\pi _{h'}\). If \(h \neq h'\), then \(c = 0\); if \(h = h'\), then \(c \in \bigwedge ^2 \hat\pi _h\). Consequently, if every element of a subspace \(\rho \subseteq \bigwedge ^2 K^4\) has this property, and \(f_1, f_2, f_3 \in \bigwedge ^2 K^4\) lie in \(\bigwedge ^2 \hat\pi _h\) when \(h = h'\), then \(\dim \bigl(\rho + \operatorname {span}(f_1, f_2, f_3)\bigr) \le 3\).

Let \(G\) be \(G_1 \sqcup G_2\) plus a path \(a - x_1 - \cdots - x_k - b\) (\(k \ge 0\) new vertices), with \(a \in V(G_1)\), \(b \in V(G_2)\), and every other edge of \(G\) inside \(G_1\) or inside \(G_2\). At every picture \(q\), both restriction maps \(L_G(q) \to L_{G_i}(q)\) are onto.

Let \(Y_0, \dots , Y_5 \in K^4\) be the points \((1, 0, 0, 1)\), \((0, -1, 0, 1)\), \((0, 0, 1, 1)\), \((-1, 0, 1, 1)\), \((0, 0, 0, 1)\) and \((-1, -1, 0, 1)\). For \(n = 3, 4, 5, 6\), the \(n\) joins \(Y_0 \vee Y_1, \dots , Y_{n-2} \vee Y_{n-1}, Y_{n-1} \vee Y_0\) of the closed polygon \(Y_0 Y_1 \cdots Y_{n-1}\) are linearly independent, over every field.

Let \(q\) be admissible, \(z\) a height and \(p = (q, z)\). The points of every closed neighbourhood of \(p\) lie in a plane if and only if \(z \in L(q)\). In that case the plane through the points of the closed neighbourhood of each body \(v\) is unique and not vertical: if \(z_w = a x_w + b y_w + c\) on that neighbourhood, every nonzero vector orthogonal to its points is a multiple of \((a, b, -1, c)\).

Let \(q\) be an admissible picture of \(G\), \(z \in L(q)\) and \(p = (q, z)\). Choose at every body \(v\) three members of its closed neighbourhood with non-collinear picture points, and let \(n_v\) be the resulting plane normal (definition 30.6). Then the framework \(F_p\) of lemma 30.9, with panel normals \(n_v\) and concurrency points \(p_v\), is a pencil realization of \(G\) (definition 29.2) whose adjacent points are linearly independent. If moreover \(p\) has rank \(6(|V(G)| - 1) - \operatorname {def}(\tilde G)\), then \(G\) has an adjacent-distinct pencil realization (definition 29.26, at \(d = 3\)).

Let \(p = (q, z)\) be a configuration of \(G\), and let \(F_p\) be the body-hinge framework on \(G\) (definition 17.2) whose hinge at each edge \(uv\) is the line \(p_u \vee p_v\) (definition 18.3). Then the rigidity matrix of \(F_p\) has the rank of \(p\) (definition 30.8). If \(q\) is admissible, every hinge of \(F_p\) is nonzero.

Let \(r \in W \subseteq V(G)\) and \(H = G[W]\), and let \(n\) be panel normals at which every hinge of \(G/H\) is nonzero and \(\operatorname {rank} R(G/H, n) \ge N\). There is a polynomial \(Q\) in the panel normals of \(G\), nonzero at the collapsed placement (every body of \(W\) at the normal \(n_r\), every other body at its own), such that at every \(p\) with \(Q(p) \neq 0\) the rows of \(G \setminus E(H)\) at \(p\), with the columns of \(W\) deleted, have rank at least \(N\).

Let \(r \in W \subseteq V(G)\) and \(H = G[W]\), let \(q\) be a picture, and let \(\rho \) send a vector \((z, h)\) of unknowns of the rescaled lifting system to the height that agrees with \(z\) on \(W\) and vanishes elsewhere.

1. At every \(t\), \(\rho \) maps the solutions of \(M(t)\) into \(L_H(q)\).

2. If \(q\) is admissible for \(H\) and for \(G/H\), then \(\dim \ker M(0) + 3 \le \dim \rho (\ker M(0)) + \dim L_{G/H}(q)\).

At every \(t\), the heights of a solution of \(M(t)\) lie in \(L_G(q(t))\). At \(t \neq 0\) every height of \(L_G(q(t))\) is the heights of a solution of \(M(t)\), so \(\dim \ker M(t) \ge \dim L_G(q(t))\).

Let \(r \in W \subseteq V(G)\) and \(H = G[W]\), and let \(q\) be a picture. Suppose that no body outside \(W\) is adjacent to two bodies of \(W\). Then every \(z \in L_{G/H}(q)\) with \(z_r = 0\) agrees off \(W\) with the heights of a solution of \(M(0)\).

Let \(r \in W\) and \(H = G[W]\), let \(q\) be a picture and \(t \in K\) nonzero, and let \((z, h)\) be any vector of unknowns of the rescaled lifting system. Then the rank of \(H\) at the configuration \((q(t), z(t))\) equals its rank at \((q, z)\).

Let \(G\) satisfy the standing hypotheses and be \(2\)-edge-connected. Let \(W \subsetneq V(G)\) with \(|W| \ge 2\), such that no body outside \(W\) is adjacent to two bodies of \(W\), and let \(G/H\) be the contraction of \(H = G[W]\) to a body \(r \in W\). Then \(G/H\) is simple and satisfies the standing hypotheses.

Let \(G\) be simple and \(W \subseteq V(G)\) with \(|W| \ge 2\), and suppose \(G[W]\) has deficiency zero at some \(d \ge 1\) (definition 20.3). Then \(G[W]\) satisfies the standing hypotheses.

Let \(H\) be a proper rigid subgraph of \(G\). Contracting \(H\) to a single vertex leaves the deficiency unchanged, \(\operatorname {def}(\widetilde{G / E(H)}) = \operatorname {def}(\tilde G)\), without assuming \(G\) minimal.

Let \(G\) be a finite graph, and let \(t \mapsto n(t) = (n_v(t))\) be panel normals whose coordinates are polynomials in \(t \in K\), such that the hinge at every edge of \(G\) is nonzero at \(t = 0\). Then for all but finitely many \(t \in K\), the rank of the rigidity matrix of the panel-hinge framework on \(G\) with normals \(n(t)\) is at least its value at \(t = 0\).

Let \(G\) be a multigraph that is not two-edge-connected, so that at most one edge crosses some nonempty proper subset \(V_1 \subsetneq V(G)\), and let \(V_2 = V(G) \setminus V_1\). If \(G[V_1]\) and \(G[V_2]\) each have a pencil realization at the deficiency rank, then so does \(G\). The same holds for realizations at the deficiency rank in which the two points of every link are projectively distinct.

Let \(G = G_1 \cup G_2\) with \(V(G_1) \cap V(G_2) = \{ v\} \) and disjoint edge sets. At every picture \(q\), both restriction maps \(L_G(q) \to L_{G_i}(q)\) (lemma 30.46) are onto.

Fix the panel/point data of the two sides at a crossing edge \(uv\): normal \(n_1(u)\) and point \(pt_1(u) \ne 0\) on the \(V_1\) side, normal \(n_2(v)\) and point \(pt_2(v) \ne 0\) on the \(V_2\) side. Then there is a linear automorphism \(g\) of \(K^4\) with a contragredient \(h\) (\(\langle g x, h y\rangle = \langle x, y\rangle \) for the standard pairing) meeting the two cross-incidences of lemma 29.12 once the \(V_2\) side is transported by \((g, h)\): \(\langle pt_1(u), h\, n_2(v)\rangle = 0\) and \(\langle g\, pt_2(v), n_1(u)\rangle = 0\); moreover the transported point \(g\, pt_2(v)\) is projectively distinct from \(pt_1(u)\), which the construction supplies for free.

If \(q(s)\) is admissible for \(G\), then \(z(s) \in L_G(q(s))\). The points of the configuration \((q(s), z(s))\) are polynomial in \(s\), and on \(V_1\) they are those of \((q_1, z_1)\).

Let the points of a configuration be polynomial in a parameter \(s\). If, at one parameter, every hinge of a graph \(H\) is nonzero and the rank of \(H\) is at least \(r\), there is a polynomial in \(s\), nonzero there, such that the rank of \(H\) is at least \(r\) wherever it does not vanish. If, at one parameter, \(\dim (\rho + \operatorname {span} F) \ge n\) for a fixed subspace \(\rho \subseteq \bigwedge ^2 K^4\) and a family \(F\) of joins of points of the configuration, the same holds for this bound.

If \(P\) is a polynomial in the picture, \(s \mapsto P(q(s))\) is a polynomial in \(s\).

Let \(a - x_1 - \cdots - x_k - b\) be an open ear of \(G\) on \(V_1\) with \(k \ge 2\), and let \(q\) be admissible for \(G\).

1. A height lies in \(L_G(q)\) as soon as it agrees with an affine function of the picture on the closed neighbourhood in \(G\) of every body of \(V_1\).

2. Every \(z^1 \in L_{G[V_1]}(q)\) is the restriction to \(V_1\) (lemma 30.46) of a height \(z \in L_G(q)\) taking any prescribed values at \(x_2, \dots , x_{k-1}\).

Let \(p\) be the points of a configuration of \(G\), and let \(g_1, \dots , g_m\) be edges of \(G\), with ends \(u_i, w_i\), whose joins \(p_{u_i} \vee p_{w_i}\) are linearly independent. Then the hinges at \(g_1, \dots , g_m\) of the panel-hinge framework defining the rank of \(p\) (definition 30.8) span a space of dimension at least \(m\). In particular, if \(m = 6\), the hinges at any set of edges containing \(g_1, \dots , g_6\) span the whole screw space.

If a finite multigraph is nondegeneracy-feasible (definition 29.23), then every closed hub-neighbourhood has at most three members, and no triangle contains two pencil hubs.

Let \(G'\) and \(H\) be graphs on the same bodies, and \(a, b\) two bodies of \(G'\), such that every closed neighbourhood in \(H\) lies in the closed neighbourhood of the same body in \(G'\), except that the one of \(a\) may also contain \(b\) and the one of \(b\) may also contain \(a\). Let \(q\) be admissible for \(G'\), with \(\dim L_H(q) + 2 \le \dim L_{G'}(q)\). Then on the solutions \((z, h)\) of the lifting system of \(G'\) at \(q\) (definition 30.15), the two linear functionals

are linearly independent.

Let \(G\) be connected, let \(q\) be admissible, and let \(F_{(q,0)}\) be the body-hinge framework whose hinge at each edge \(uv\) is the line \(p_u \vee p_v\) of the flat configuration \(p = (q, 0)\) (lemma 30.9). Then its infinitesimal motions form a space of dimension \(3 + \dim F(q)\).

Let \(K\) be infinite and \(G\) simple and nondegeneracy-feasible, with a body \(x\) of degree two whose neighbours \(a\) and \(b\) are pencil hubs, and with \(\operatorname {def}_3(G - x) \le \operatorname {def}_3(G)\). If \(G - x\) has a generic pencil realization whenever it is nondegeneracy-feasible, then \(G\) has a generic pencil realization.

Let \(K\) be infinite and \(G\) simple and nondegeneracy-feasible, with two adjacent bodies \(x_1, x_2\) of degree two, both joined to a body \(c\) of degree at least four. If \(G - \{ x_1, x_2\} \) has a generic pencil realization whenever it is nondegeneracy-feasible, then \(G\) has a generic pencil realization.

Let \(K\) be infinite. (a) Let \(G\) be simple and nondegeneracy-feasible, and let \(H\) be a subgraph of \(G\). Suppose that whenever a pencil hub \(h\) of \(G\) is a body of \(H\) but not a hub of \(H\), the neighbours of \(h\) in \(G\) that are not its neighbours in \(H\) are not hubs of \(G\). Then \(G\) has a nondegenerate realization whose restriction to \(H\) is a nondegenerate realization of \(H\). In particular \(H\) is nondegeneracy-feasible, by a realization whose normals are independent on the closed hub-neighbourhood in \(G\) of every body of \(G\). (b) Let \(H\) have at least one body. Suppose that \(H\) has a generic pencil realization, and a nondegenerate realization with normals \(n'\) and points \(p'\). Let \(S_1, \dots , S_k \subseteq V(H)\) be sets on which \(n'\) is linearly independent, and let \((u_1, w_1), \dots , (u_m, w_m)\) be pairs of bodies of \(H\) with \(p'_{u_j} \cdot n'_{w_j} \neq 0\). Suppose that every member of every \(S_i\), and every \(w_j\), is a hub of \(H\) or has a closed neighbourhood in \(H\) of exactly three members. Then \(H\) has a generic pencil realization whose normals are independent on every \(S_i\), with \(p_{u_j} \cdot n_{w_j} \neq 0\) for every \(j\).

Let \(K\) be infinite, let \(\rho \subseteq \bigwedge ^2 K^4\) be a subspace and \(F\) a finite family in \(\bigwedge ^2 K^4\), let \(y, y', u \in K^4\), and let \(W = \rho + \operatorname {span} F + K\, (y \vee y')\). For \(t \in K\) write \(W_t = \rho + \operatorname {span} F + \operatorname {span}\bigl(y \vee (y + t u),\ (y + t u) \vee y'\bigr)\). If \(y \vee u \notin W\), then \(\dim W_t \ge \dim W + 1\) for some \(t \neq 0\).

Let \(K\) be infinite, and let \(\pi _a\) and \(\pi _b\) be the planes \(p_z = \ell _a \cdot \bar p\) and \(p_z = \ell _b \cdot \bar p\) of \(K^4\), for \(\ell _a, \ell _b \in K^3\) (with \(\bar p\) as in lemma 30.66). Let \(p_a \in \pi _a\), \(p_b \in \pi _b\) and \(y \in \pi _a \cap \pi _b\) be affine points, of last coordinate \(1\), with \(p_a \notin \pi _b\) and \(p_b \notin \pi _a\). Then for every subspace \(\rho \subseteq \bigwedge ^2 K^4\) there are affine points \(x_1 \in \pi _a\) and \(x_2 \in \pi _b\) with

Let \(K\) be infinite and let \(G\) be simple with at least two bodies. There is a nonzero polynomial \(P\) in the picture coordinates such that at every picture \(q\) with \(P(q) \ne 0\) the plane framework \(P_q\) of lemma 30.33, with panel normal \((x_v, y_v, 1)\) at each body, has \(\operatorname {rank} R(P_q) \ge 3(|V(G)| - 1) - \operatorname {def}_2(G)\).

Let \(G'\) be \(G\) with its edges relabelled injectively into a larger set of labels (definition 23.41). Then \(G'\) has the lifting spaces \(L(q)\) and the admissible and main pictures of \(G\).

Let \((n_v)\) be panel normals and \((c_v)\) nonzero scalars. Then at every edge \(e\) with ends \(u\) and \(v\), the panel-hinge framework on \(G\) with normals \(c_v n_v\) has the hinge \(c_u c_v\, C(e)\), where \(C(e)\) is its hinge at the normals \(n_v\). In particular the two frameworks have the same infinitesimal motions, and their rigidity matrices have the same rank.

For \(p = (p_x, p_y, p_z, p_w) \in K^4\) write \(\bar p = (p_x, p_y, p_w) \in K^3\). There is a linear isomorphism of the screw space \(\bigwedge ^2 K^4\) onto \(K^3 \times K^3\), adapted to the splitting of lemma 30.31, that sends the join \(p \vee p'\) of \(p, p' \in K^4\) to \(\bigl(p_z\, \bar p' - p'_z\, \bar p,\ \bar p \times \bar p'\bigr)\). In particular, a family of joins is linearly independent as soon as the family of these vectors is.

Let \((u_i, w_i)_{i \in I}\) be a finite family of pairs of bodies, and write \(p\) for the points of a configuration \((q, z)\). If the joins \(p_{u_i} \vee p_{w_i}\) are linearly independent at \((q_0, z)\), there is a polynomial \(P\) in the picture, nonzero at \(q_0\), such that they are linearly independent at \((q, z)\) whenever \(P(q) \neq 0\). Likewise, if they are independent at \((q, z_0)\), there is a polynomial \(R\) in the heights, nonzero at \(z_0\), such that they are independent at \((q, z)\) whenever \(R(z) \neq 0\).