Geiringer–Laman theorem

Let ${\displaystyle G=(V,E)}$ be a graph. First, we show that generic frameworks with respect to infinitesimal rigidity form an open and dense set in ${\displaystyle \mathbb {R} ^{2|V|}}$. One necessary and sufficient condition for a framework ${\displaystyle p}$ of ${\displaystyle G}$ to be infinitesimally rigid is for its rigidity matrix ${\displaystyle R(p)}$ to have max rank over all frameworks of ${\displaystyle G}$.

Proposition 1. For any framework ${\displaystyle p}$ of ${\displaystyle G}$ and any neighborhood ${\displaystyle N(p)}$, there exists a framework ${\displaystyle q}$ in ${\displaystyle N(p)}$ such that the rigidity matrix ${\displaystyle R(q)}$ has max rank.

Proof. If the rigidity matrix ${\displaystyle R(p)}$ does not have max rank, then it has a set of dependent rows corresponding to a subset of edges ${\displaystyle E'\subset E}$ such that for some other rigidity matrix ${\displaystyle R(q)}$, the rows corresponding to ${\displaystyle E'}$ are independent. Let ${\displaystyle {\mathcal {X}}_{E'}}$ be the set of frameworks such that the rows corresponding to ${\displaystyle E'}$ in their rigidity matrices are dependent. In other words, ${\displaystyle {\mathcal {X}}_{E'}}$ is the set of frameworks ${\displaystyle p}$ such that the minor of the rows corresponding to ${\displaystyle E'}$ in ${\displaystyle R(p)}$ is ${\displaystyle 0}$. Hence, ${\displaystyle {\mathcal {X}}_{E'}}$ is a curve in ${\displaystyle \mathbb {R} ^{2|V|}}$, because a minor is a polynomial in the entries of a matrix. Let ${\displaystyle {\mathcal {X}}}$ be the union of these curves over all subsets of edges of ${\displaystyle E}$. If a framework ${\displaystyle R(p)}$ does not have max rank for some framework ${\displaystyle p}$, then ${\displaystyle p}$ is contained in ${\displaystyle {\mathcal {X}}}$. Finally, since ${\displaystyle {\mathcal {X}}}$ is a finite set of curves, the proposition is proved.

Proposition 2. Infinitesimal rigidity is a generic property of graphs.

Proof. We show that if one generic framework with respect to infinitesimal rigidity is infinitesimally rigid, then all generic frameworks are infinitesimally rigid. If a framework ${\displaystyle p}$ of a graph ${\displaystyle G}$ is infinitesimally rigid, then ${\displaystyle R(p)}$ has max rank. Note that the kernel of the rigidity matrix is the space of infinitesimal motions of a framework, which has dimension ${\displaystyle {3 \choose 2}}$ for infinitesimally rigid frameworks. Hence, by the Rank–nullity theorem, if one generic framework is infinitesimally rigid then all generic frameworks are infinitesimal rigidity have rigid.

Proposition 3. If a framework ${\displaystyle p}$ of a graph ${\displaystyle G}$ is infinitesimally rigid, then it is rigid.

Proof. Assume that ${\displaystyle p}$ is not rigid, so there exists a framework ${\displaystyle q}$ in a neighborhood ${\displaystyle N(p)}$ such that ${\displaystyle \rho (p)=\rho (q)}$ and ${\displaystyle q}$ is cannot be obtained via a trivial motion of ${\displaystyle p}$. Since ${\displaystyle q}$ is in ${\displaystyle N(p)}$, there exists a ${\displaystyle \delta >0}$ and ${\displaystyle \|h\|<\delta }$ such that ${\displaystyle q=p+h}$. Applying some algebra yields:

${\displaystyle {\begin{aligned}\rho (p)_{ij}-\rho (q)_{ij}&=\|p_{i}-p_{j}\|^{2}-\|q_{i}-q_{j}\|^{2}\\&=\|h_{i}-h_{j}\|^{2}-2(p_{i}-p_{j})(h_{i}-h_{j})\\&=0.\end{aligned}}}$

Hence,

${\displaystyle {\frac {\|h_{i}-h_{j}\|^{2}}{\|h\|}}=2(p_{i}-p_{j}){\frac {(h_{i}-h_{j})}{\|h\|}}=0.}$

We can choose a sequence of ${\displaystyle \delta _{n}}$ such that ${\displaystyle \delta _{n+1}<\delta _{n}}$ and ${\displaystyle \lim _{n\rightarrow \infty }\delta _{n}=0}$. This causes ${\displaystyle \lim _{n\rightarrow \infty }\|h_{n}\|=0}$ and ${\displaystyle \lim _{n\rightarrow \infty }{\frac {\|h_{n,i}-h_{n,j}\|^{2}}{\|h_{n}\|}}=(h_{i}^{\star }-h_{j}^{\star })}$. Hence,

${\displaystyle {\begin{aligned}2(p_{i}-p_{j})(h_{i}^{\star }-h_{j}^{\star })&=\lim _{n\rightarrow \infty }2(p_{i}-p_{j}){\frac {\|h_{n,i}-h_{n,j}\|^{2}}{\|h_{n}\|}}\\&=\lim _{n\rightarrow \infty }{\frac {\|h_{n,i}-h_{n,j}\|^{2}}{\|h_{n}\|}}\\&=0.\end{aligned}}}$

The first and last expressions in the equations above state that ${\displaystyle h^{\star }}$ is an infinitesimal motion of the framework ${\displaystyle p}$. Since there is no trivial motion between ${\displaystyle p}$ and ${\displaystyle q}$, ${\displaystyle h^{\star }}$ is not a trivial infinitesimal motion. Thus, ${\displaystyle p}$ is not infinitesimally rigid.

Proposition 4. If a framework ${\displaystyle p}$ of a graph ${\displaystyle G}$ is rigid and generic with respect to infinitesimal rigidity, then ${\displaystyle p}$ is infinitesimally rigid.

Proof. This follows from the implicit function theorem. First, we will factor out all trivial motions of ${\displaystyle p}$. Since ${\displaystyle R(p)}$ has max rank, no ${\displaystyle 3}$ points of ${\displaystyle p}$ are colinear. Hence, we can pin ${\displaystyle 2}$ points of ${\displaystyle p}$ to factor out trivial motions: one point at the origin and another along the ${\displaystyle x}$-axis at a distance from the origin consistent with all constraints. This yields a pinned framework ${\displaystyle q}$ that lives in ${\displaystyle \mathbb {R} ^{2|V|-3}}$. This can be done for all frameworks in a neighborhood ${\displaystyle N(p)}$ of ${\displaystyle p}$ to obtain a neighborhood ${\displaystyle N(q)}$ of ${\displaystyle q}$ of pinned frameworks. The set of such frameworks is still a smooth manifold, so the rigidity map and rigidity matrix can be redefined on the new domain. Specifically, the rigidity matrix ${\displaystyle R(q)}$ of a pinned framework ${\displaystyle q}$ has ${\displaystyle 2|V|-3}$ columns and rank equal to ${\displaystyle R(p)}$, where ${\displaystyle p}$ is the unpinned framework corresponding to ${\displaystyle q}$. In this pinned setting, a framework is rigid if it is the only nearby solution to the rigidity map.

Now, assume an unpinned framework ${\displaystyle p}$ is not infinitesimally rigid, so that ${\displaystyle rank(R(p))=k<2|V|-3}$. Then the ${\displaystyle rank(R(q))=k}$, where ${\displaystyle q}$ is the pinned version of ${\displaystyle p}$. We now set up to apply the implicit function theorem. Our continuously differentiable function is the rigidity map ${\displaystyle \rho$ :\mathbb {R} ^{2|V|-3}\rightarrow \mathbb {R} ^{|E|}} . The Jacobian of ${\displaystyle \rho }$ is the rigidity matrix. Consider the subset of edges ${\displaystyle E'\subset E}$ corresponding to the ${\displaystyle k}$ independent rows of ${\displaystyle R(q)}$, yielding the submatrix ${\displaystyle R(q)_{E'}}$. We can find ${\displaystyle k}$ independent columns of ${\displaystyle R(q)_{E'}}$. Denote the entries in these columns by the vectors ${\displaystyle y=y_{1},\dots ,y_{k}}$. Denote the entries of the remaining columns by the vectors ${\displaystyle x=x_{1},\dots ,x_{2|V|-3-k}}$. The ${\displaystyle k\times k}$ submatrix of ${\displaystyle R(q)_{E'}}$ induced the ${\displaystyle y_{1},\dots ,y_{k}}$ is invertible, so by the implicit function theorem, there exists a continuously differentiable function ${\displaystyle g}$ such that ${\displaystyle y=g(x)}$ and ${\displaystyle \rho (x,y)_{E'}=\rho (q)_{E'}}$. Hence, the framework ${\displaystyle q_{E'})}$ of the subgraph ${\displaystyle G'=(V,E')}$ is not rigid, and since the rows of ${\displaystyle R(q)_{E'}}$ span the row space of ${\displaystyle R(q)}$, ${\displaystyle q}$ is also not rigid. This contradicts our assumption, so ${\displaystyle p}$ is infinitesimally rigid.

Proposition 5. Rigidity is a generic property of graphs.

Proof. Let ${\displaystyle p}$ be a rigid framework of ${\displaystyle G}$ that is generic with respect to rigidity. By definition, there is a neighborhood of rigid frameworks ${\displaystyle N(p)}$ of ${\displaystyle p}$. By Proposition 1, there is a framework ${\displaystyle q}$ in ${\displaystyle N(p)}$ that is generic with respect to infinitesimal rigidity, so by Proposition 4, ${\displaystyle q}$ is infinitesimally rigid. Hence, by Proposition 2, all frameworks that are generic with respect to infinitesimal rigidity are infinitesimally rigid, and by Proposition 3 they are also rigid. Finally, every neighborhood ${\displaystyle N(p')}$ of every framework ${\displaystyle p'}$ that is generic with respect to rigidity contains a framework ${\displaystyle q'}$ that is generic with respect to infinitesimal rigidity, by Proposition 1. Thus, if ${\displaystyle p}$ is rigid then ${\displaystyle p'}$ is rigid.

Figure 2. Visualizations of the both directions of the proof of Theorem 1. (a) also depicts the proof of Proposition 5.

Theorem 1. A graph ${\displaystyle G}$ is generically rigid if and only if it is generically infinitesimally rigid.

Proof. The proof follows a similar argument to the proof of Proposition 5. If ${\displaystyle G}$ is generically rigid, then there exists a generic framework ${\displaystyle p}$ with respect to rigidity that is rigid by definition. By Propositions 1 and 4, in any neighborhood of ${\displaystyle p}$ there is a framework ${\displaystyle q}$ that is generic with respect to infinitesimal rigidity and infinitesimally rigid. Hence, by Proposition 2, ${\displaystyle G}$ is generically infinitesimally rigid.

For the other direction, assume to the contrary that ${\displaystyle G}$ is generically infinitesimally rigid, but not generically rigid. Then there exists a generic framework ${\displaystyle p}$ with respect to rigidity that is not rigid by definition. By Proposition 1, in any neighborhood of ${\displaystyle p}$ there is a framework ${\displaystyle q}$ that is generic with respect to infinitesimal rigidity. By assumption ${\displaystyle q}$ is infinitesimally rigid, and by Proposition 3, ${\displaystyle q}$ is also rigid. Thus, ${\displaystyle p}$ must be rigid and, by Proposition 5, all frameworks that are generic with respect to rigidity are rigid. This contradicts our assumption that ${\displaystyle G}$ is not generically rigid.

The Maxwell Direction of the Geiringer-Laman theorem follows from a simple counting argument on the rigidity matrix.

Maxwell Direction. If a graph ${\displaystyle G}$ has a generic infinitesimally rigid framework, then ${\displaystyle G}$ has a Geiringer-Laman subgraph.

Proof. Let ${\displaystyle p}$ be a generic infinitesimally rigid framework of ${\displaystyle G}$. By definition, ${\displaystyle R(p)}$ has max rank, i.e., ${\displaystyle rank(R(p))=2|V|-3}$. In particular, ${\displaystyle R(p)}$ has ${\displaystyle 2|V|-3}$ independent rows. Each row of ${\displaystyle R(p)}$ corresponds to an edge of ${\displaystyle G}$, so the submatrix ${\displaystyle R(p)_{G'}}$ with just the independent rows corresponds to a subgraph ${\displaystyle G'=(V,E')}$ such that ${\displaystyle |E'|=2|V|-3}$. Furthermore, any subgraph ${\displaystyle H=(V',F)}$ of ${\displaystyle G'}$ corresponds to a submatrix ${\displaystyle R(p)_{H}}$ of ${\displaystyle R(p)_{G'}}$. Since the rows of ${\displaystyle R(p)_{G'}}$ are independent, so are the rows of ${\displaystyle R(p)_{H}}$. Hence, ${\displaystyle rank(R(p)_{H})=|F|}$, which clearly satisfies ${\displaystyle |F|\leq 2|V(F)|-3}$.

Now we begin the proof of the other direction of the Geiringer-Laman theorem by first showing that a generically minimally rigid graph has a Henneberg construction. A Henneberg graph ${\displaystyle G}$ has the following recursive definition:

1. ${\displaystyle G}$ is a single edge or
2. ${\displaystyle G}$ can be obtained from a Henneberg graph ${\displaystyle G'}$ via one of the following operations
   1. add a vertex to ${\displaystyle G'}$ and connect it to ${\displaystyle 2}$ distinct vertices of ${\displaystyle G'}$
   2. For an edge ${\displaystyle (u,v)}$ and a vertex ${\displaystyle w}$ of ${\displaystyle G'}$, add a vertex to ${\displaystyle G'}$, connect it to ${\displaystyle u,v,}$ and ${\displaystyle w}$, and then remove ${\displaystyle (u,v)}$.

The two operations above are called a ${\displaystyle 0}$-extension and a ${\displaystyle 1}$-extension respectively.

The following propositions are proved in:[2]

Proposition 6. A generically minimally rigid graph has no vertex with degree ${\displaystyle 1}$ and at least one vertex with degree less than ${\displaystyle 4}$

Proposition 7. If ${\displaystyle G}$ is a generically minimally rigid graph with a vertex ${\displaystyle v}$ of degree ${\displaystyle 3}$, connected to vertices ${\displaystyle u_{1},u_{2},}$ and ${\displaystyle u_{3}}$, then for at least one pair of the neighbors of ${\displaystyle v}$, without loss of generality say ${\displaystyle (u_{1},u_{2})}$, there is no subgraph ${\displaystyle G'=(V',E')}$ of ${\displaystyle G}$ that contains ${\displaystyle u_{1}}$ and ${\displaystyle u_{2}}$ and satisfies ${\displaystyle |F|=2|U|-3}$.

Theorem 2. A generically minimally rigid graph ${\displaystyle G}$ with at least ${\displaystyle 2}$ vertices has a Henneberg construction.

Proof. We proceed by induction on the number of vertices ${\displaystyle |V|}$. The base case of ${\displaystyle |V|=2}$ is the base case Henneberg graph. Assume ${\displaystyle G=(V,E)}$ has a Henneberg construction when ${\displaystyle |V|=k}$ and we will prove it for ${\displaystyle |V|=k+1}$. When ${\displaystyle |V|=k+1}$, ${\displaystyle G}$ has a vertex ${\displaystyle v}$ with degree ${\displaystyle 2}$ or ${\displaystyle 3}$, by Proposition 6.

Case 1: ${\displaystyle v}$ has degree 2.

Let ${\displaystyle G'=(V',E')}$ be the subgraph of ${\displaystyle G}$ obtained by removing ${\displaystyle v}$, so ${\displaystyle |V'|=|V|-1}$ and ${\displaystyle |E'|=|E|-2}$. Since ${\displaystyle G}$ is minimally rigid, we have

${\displaystyle |E'|=|E|-2=2|V|-3-2=2|V'|-3.}$

Furthermore, any subgraph ${\displaystyle H=(V'',F)}$ of ${\displaystyle G'}$ is also a subgraph of ${\displaystyle G}$, so ${\displaystyle |F|\leq 2|V''|-4,}$ by assumption. Hence, ${\displaystyle G'}$ is minimally rigid, by the Maxwell Direction, and ${\displaystyle G'}$ has a Henneberg construction by the inductive hypothesis. Now simply notice that ${\displaystyle G}$ can be obtained from ${\displaystyle G'}$ via a ${\displaystyle 0}$-extension.

Case 2: ${\displaystyle v}$ has degree 3.

Let the edges incident to ${\displaystyle v}$ be ${\displaystyle (v,u_{1}),(v,u_{2}),}$ and ${\displaystyle (v,u_{3})}$. By Proposition 7, for one pair of the neighbors of ${\displaystyle v}$, without loss of generality say ${\displaystyle (u_{1},u_{2})}$, there is no subgraph ${\displaystyle H=(U,F)}$ of ${\displaystyle G}$ that contains ${\displaystyle u_{1}}$ and ${\displaystyle u_{2}}$ and satisfies ${\displaystyle |F|=2|U|-3}$. Note that ${\displaystyle (u_{1},u_{2})}$ cannot be an edge, or else the subgraph on just that edge satisfies the previous equality. Consider the graph ${\displaystyle G'=(V',E')}$ obtained by removing ${\displaystyle v}$ from ${\displaystyle G}$ and adding the edge ${\displaystyle (u_{1},u_{2})}$. We have

${\displaystyle |E'|=|E|-3+1=2|V|-3-2=2|V'|-3}$.

Furthermore, as with Case 1, any subgraph of ${\displaystyle G'}$ that does not contain ${\displaystyle (u_{1},u_{2})}$ satisfies the second condition for minimal rigidity by assumption. For a subgraph of ${\displaystyle G''=(V'',E'')}$ that does contain ${\displaystyle (u_{1},u_{2})}$, removing this edge yields a subgraph ${\displaystyle G'''=(V''',E''')}$ of ${\displaystyle G}$. By Proposition 7, ${\displaystyle |E'''|\leq 2|V'''|-2}$, so ${\displaystyle |E''|\leq 2|V''|-3}$. Hence, ${\displaystyle G'}$ is minimally rigid, and ${\displaystyle G'}$ has a Henneberg construction by the inductive hypothesis. Finally, notice that ${\displaystyle G}$ can be obtained from ${\displaystyle G'}$ via a ${\displaystyle 1}$-extension.

Combining Cases 1 and 2 proves the theorem by induction.

It is also easy to the converse of Theorem 2 by induction.

Proposition 8. A graph with a Henneberg construction is generically minimally rigid.

To complete the proof of the Geringer-Laman theorem, we show that if a graph has a Henneberg construction then it is generically infinitesimmaly rigid. The proof of this result relies on the following proposition from.[2]

Proposition 9. If ${\displaystyle p_{1},p_{2},p_{3}}$ are three non-colinear ${\displaystyle 2}$-dimensional points and ${\displaystyle u_{1},u_{2},u_{3}}$ are three ${\displaystyle 2}$-dimensional vectors, then the following statements are equivalent:

• ${\displaystyle (p_{i}-p_{j})\cdot (u_{i}-u_{j})=0}$ for all ${\displaystyle i,j\in \{1,2,3\}}$
• The function

${\displaystyle f(p)={\begin{vmatrix}p-p_{1}&(p-p_{1})\cdot u_{1}\\p-p_{2}&(p-p_{2})\cdot u_{2}\\p-p_{3}&(p-p_{3})\cdot u_{3}\end{vmatrix}}}$

vanishes at every point ${\displaystyle p}$.

Theorem 3. If a graph ${\displaystyle G}$ with at least ${\displaystyle 3}$ vertices has a Henneberg construction, then ${\displaystyle G}$ is generically infinitesimally rigid.

Proof. We proceed by induction on the number of vertices ${\displaystyle |V|}$. The graph in the base case ${\displaystyle |V|=3}$ is a triangle, which is generically infinitesimally rigid. Assume that when ${\displaystyle |V|=k}$ ${\displaystyle G}$ is generically infinitesimally rigid and we will prove it for ${\displaystyle k+1}$. For ${\displaystyle |V|=k+1}$, consider the graph ${\displaystyle G'=(V',E')}$ that ${\displaystyle G}$ was obtained from via ${\displaystyle 0}$- or ${\displaystyle 1}$-extension. By the inductive hypothesis, ${\displaystyle G'}$ is generically infinitesimally rigid. Hence, ${\displaystyle G'}$ has a generic infinitesimally rigid framework ${\displaystyle p'\in \mathbb {R} ^{2k}}$ such that the kernel of ${\displaystyle R(p')}$ has dimension ${\displaystyle 3}$. Let ${\displaystyle v}$ be the vertex added to ${\displaystyle G'}$ to obtain ${\displaystyle G}$. We must choose a placement ${\displaystyle p_{v}}$ in ${\displaystyle 2}$-dimensions such that ${\displaystyle p=p'\cup p_{v}}$ is a generic infinitesimally rigid framework of ${\displaystyle G}$.

Case 1: ${\displaystyle G}$ is obtained from ${\displaystyle G'}$ via a ${\displaystyle 0}$-extension.

Choosing such a placement for ${\displaystyle p_{v}}$ is equivalent to adding rows corresponding to the equations

${\displaystyle {\begin{aligned}&(p_{v}-p_{u})\cdot (q_{v}-q_{u})=0\\&(p_{v}-p_{w})\cdot (q_{v}-q_{w})=0\end{aligned}}}$

to the rigidity matrix ${\displaystyle R(p')}$, where ${\displaystyle u}$ and ${\displaystyle w}$ are the neighbors of ${\displaystyle v}$ after the ${\displaystyle 0}$-extension and ${\displaystyle q_{v}}$ is the velocity assigned to ${\displaystyle p_{v}}$ by an infinitesimal motion. Our goal is to choose ${\displaystyle p_{v}}$ such the dimension of the space of infinitesimal motions of ${\displaystyle R(p)}$ is the same as that of ${\displaystyle R(p')}$. We can choose ${\displaystyle p_{v}}$ such that it is not colinear to ${\displaystyle p_{u}}$ and ${\displaystyle p_{w}}$, which ensures that there is only one solution to these equations. Hence, the kernel of ${\displaystyle R(p)}$ has dimension ${\displaystyle 3}$, so ${\displaystyle p}$ is a generic infinitesimally rigid framework of ${\displaystyle G}$.

Case 2: ${\displaystyle G}$ is obtained from ${\displaystyle G'}$ via a ${\displaystyle 1}$-extension.

Let the neighbors of ${\displaystyle v}$ after the ${\displaystyle 1}$-extension be the edges ${\displaystyle (v,u_{1}),(v,u_{2})}$, and ${\displaystyle (v,u_{3})}$, and let ${\displaystyle (u_{1},u_{2})}$ be the edge that was removed. Removing the edge ${\displaystyle (u_{1},u_{2})}$ from ${\displaystyle G'}$ yields the subgraph ${\displaystyle G''}$. Let ${\displaystyle p''}$ be the framework of ${\displaystyle G''}$ that is equivalent to ${\displaystyle p'}$, except for the removed edge. The rigidity matrix ${\displaystyle R(p'')}$ can be obtained from ${\displaystyle R(p')}$ by removing the row corresponding to the removed edge. By Proposition 8, ${\displaystyle G'}$ is generically minimally rigid, so the rows of ${\displaystyle R(p')}$ are independent. Hence, the rows of ${\displaystyle R(p'')}$ are independent and its kernel has dimension ${\displaystyle 4}$. Let ${\displaystyle \lambda _{1},\lambda _{2},\lambda _{3},\lambda _{4}}$ be a basis vector for the space of infinitesimal motions of ${\displaystyle p''}$ such that ${\displaystyle \lambda _{1},\lambda _{2},\lambda _{3}}$ is a basis for the space of trivial infinitesimal motions. Then, any infinitesimal motion of ${\displaystyle p''}$ can be written as a linear combination of these ${\displaystyle 4}$ basis vectors. Choosing a placement for ${\displaystyle p_{v}}$ that results in a generic infinitesimally rigid framework of ${\displaystyle G}$ is equivalent to adding rows corresponding to the equations

${\displaystyle {\begin{aligned}&(p_{v}-p_{u_{1}})\cdot (q_{v}-q_{u_{1}})=0\\&(p_{v}-p_{u_{2}})\cdot (q_{v}-q_{u_{2}})=0\\&(p_{v}-p_{u_{3}})\cdot (q_{v}-q_{u_{3}})=0\end{aligned}}}$

to the rigidity matrix ${\displaystyle R(p'')}$. Our goal is to choose ${\displaystyle p_{v}}$ such the dimension of the space of infinitesimal motions of ${\displaystyle R(p)}$ is ${\displaystyle 1}$ less than that of ${\displaystyle R(p'')}$. After rearranging, these equations have a solution if and only if

${\displaystyle {\begin{vmatrix}p_{v}-p_{u_{1}}&(p_{v}-p_{u_{1}})\cdot q_{u_{1}}\\p_{v}-p_{u_{2}}&(p_{v}-p_{u_{2}})\cdot q_{u_{2}}\\p_{v}-p_{u_{3}}&(p_{v}-p_{u_{3}})\cdot q_{u_{3}}\end{vmatrix}}=0.}$

Note that ${\displaystyle q_{u_{j}}}$ can be written as ${\displaystyle \sum _{i}^{4}{c_{i}\lambda _{i,u_{j}}}}$, for constants ${\displaystyle c_{1},c_{2},c_{3},c_{4}}$. Furthermore, we can move the summation outside of the determinant to obtain

${\displaystyle \sum _{i}^{4}c_{i}{\begin{vmatrix}p_{v}-p_{u_{1}}&(p_{v}-p_{u_{1}})\cdot \lambda _{i,u_{1}}\\p_{v}-p_{u_{2}}&(p_{v}-p_{u_{2}})\cdot \lambda _{i,u_{2}}\\p_{v}-p_{u_{3}}&(p_{v}-p_{u_{3}})\cdot \lambda _{i,u_{3}}\end{vmatrix}}=0.}$

Since ${\displaystyle \lambda _{1},\lambda _{2},\lambda _{3}}$ form a basis for the trivial infinitesimal motions, the first three terms in the summation are ${\displaystyle 0}$, leaving only

${\displaystyle c_{4}{\begin{vmatrix}p_{v}-p_{u_{1}}&(p_{v}-p_{u_{1}})\cdot \lambda _{4,u_{1}}\\p_{v}-p_{u_{2}}&(p_{v}-p_{u_{2}})\cdot \lambda _{4,u_{2}}\\p_{v}-p_{u_{3}}&(p_{v}-p_{u_{3}})\cdot \lambda _{4,u_{3}}\end{vmatrix}}=0.}$

Solutions to this equation form a curve in ${\displaystyle 2}$-dimensions. We can choose ${\displaystyle p_{v}}$ not along this curve so that ${\displaystyle c_{4}=0}$, which ensures that there is only one solution to this equation. Hence, by Proposition 9, the kernel of ${\displaystyle R(p)}$ has dimension ${\displaystyle 3}$, so ${\displaystyle p}$ is a generic infinitesimally rigid framework of ${\displaystyle G}$.

Combining Cases 1 and 2 proves the theorem by induction.