The Geiringer–Laman theorem gives a combinatorial characterization of generically rigid graphsnot defined at the linked page in -dimensional Euclidean space, with respect to bar-joint frameworks. This theorem was first proved by Hilda Pollaczek-Geiringer in 1927, and later by Gerard Laman in 1970. An efficient algorithm called the pebble game is used to identify this class of graphs. This theorem has been the inspiration for many Geiringer-Laman type results for other types of frameworks with generalized pebble games.
Statement of the theorem This theorem relies on the definitions of genericity in structural rigidity. Let denote the vertex set of a set of edges .
Geiringer-Laman Theorem. A graph is generically rigid in -dimensions with respect to bar-joint frameworks if and only if has a spanning subgraph such that
for all subsets , .
The spanning subgraph satisfying the conditions of the theorem is called a Geiringer-Laman, or minimally rigid, graph. Graphs satisfying the second condition form the independent sets of a sparsity matroid, and are called -sparse. A graph satisfying both conditions is also called a -tight graph. The direction of the theorem which states that a generically rigid graph is -tight is called the Maxwell direction, because James Clerk Maxwell gave an analogous necessary condition of -sparsity for a graph to be independent in the -dimensional generic rigidity matroid. The other direction of the theorem is the more difficult direction to prove. For dimensions , a graph that is -tight is not necessarily generically minimally rigid, i.e., the converse of the Maxwell Direction is not true.
Example. Consider the graphs in Figure 1. The graph in (c) is generically minimally rigid, but it is not infinitesimally rigid. The red velocity vectors depict a non-trivial infinitesimal flex. Removing the red edge in (a) yields a generically minimally rigid spanning graph. Adding the dashed red edge in (b) makes the graph generically minimally rigid.
Theorem. Let be a graph. The following statements are equivalent:
is a generically minimally rigid; is -tight; and contains three edge-disjoint spanning trees and such that (i) each vertex of is contained in exactly two of these spanning trees and (ii) distinct subtrees of these spanning trees do not have the same vertex set.
The equivalence of the first and second statements is the Geiringer-Laman theorem. The equivalence of the first and third statements was first proved by Crapo via the Geiringer-Laman theorem, and later by Tay via a more direct approach.
Outline of proof The proof of the Geiringer-Laman theorem given below is based on Laman's proof. Furthermore, the details of the proofs below are based on lecture notes found here
Consider a bar-joint system and a framework of this system, where is a map that places the vertices of in the plane such that the distance constraints are satisfied. For convenience, we refer to as a framework of . The proof of the Geiringer-Laman theorem follows the outline below.
A graph is generically rigid if and only if it is generically infinitesimally rigid. Infinitesimal rigidity is a generic property of graphs. Rigidity is a generic property of graphs. If a framework is infinitesimally rigid, then it is rigid. If a framework is generic with respect to infinitesimally rigidity and rigid, then it is infinitesimally rigid. If a graph has a generic infinitesimally rigid framework, then is a Geiringer-Laman graph. A graph is a Geiringer-Laman graph if and only if has a Henneberg construction. If a graph has a Henneberg construction, then has a generic infinitesimally rigid framework.
Step 1 sets up the generic setting of rigidity so that we can focus on generic infinitesimal rigidity rather than generic rigidity. This is an easier approach, because infinitesimal rigidity involves a system of linear equations, rather than quadratic in the case of regular rigidity. In particular, we can prove structural properties about the rigidity matrix of a generic framework. These results were first proved by Asimow and Roth, see Combinatorial characterizations of generically rigid graphs. Note that in Step 1.4 the framework must be generic with respect to infinitesimal rigidity. In particular, a framework that is rigid and generic with respect to rigidity is not necessarily infinitesimally rigid. Step 2 is the Maxwell Direction of the proof, which follows from simple counting arguments on the rigidity matrix. Step 3 shows that generically minimally rigid graphs are exactly the graphs that can be constructed starting from a single edge using two simple operations, which are defined below. Step 4 shows that graphs with this type of construction are generically infinitesimally rigid. Finally, once Step 1 is proved, Steps 2-3 prove the Geiringer-Laman theorem.
Equivalence of generic rigidity and generic infinitesimal rigidity
Let be a graph. First, we show that generic frameworks with respect to infinitesimal rigidity form an open and dense set in . One necessary and sufficient condition for a framework of to be infinitesimally rigid is for its rigidity matrix to have max rank over all frameworks of .
Proposition 1. For any framework of and any neighborhood , there exists a framework in such that the rigidity matrix has max rank.
Proof. If the rigidity matrix does not have max rank, then it has a set of dependent rows corresponding to a subset of edges such that for some other rigidity matrix , the rows corresponding to are independent. Let be the set of frameworks such that the rows corresponding to in their rigidity matrices are dependent. In other words, is the set of frameworks such that the minor of the rows corresponding to in is . Hence, is a curve in , because a minor is a polynomial in the entries of a matrix. Let be the union of these curves over all subsets of edges of . If a framework does not have max rank for some framework , then is contained in . Finally, since 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 of a graph is infinitesimally rigid, then has max rank. Note that the kernel of the rigidity matrix is the space of infinitesimal motions of a framework, which has dimension 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 of a graph is infinitesimally rigid, then it is rigid.
Proof. Assume that is not rigid, so there exists a framework in a neighborhood such that and is cannot be obtained via a trivial motion of . Since is in , there exists a and such that . Applying some algebra yields:
Hence,
We can choose a sequence of such that and . This causes and . Hence,
The first and last expressions in the equations above state that is an infinitesimal motion of the framework . Since there is no trivial motion between and , is not a trivial infinitesimal motion. Thus, is not infinitesimally rigid.
Proposition 4. If a framework of a graph is rigid and generic with respect to infinitesimal rigidity, then is infinitesimally rigid.
Proof. This follows from the implicit function theorem. First, we will factor out all trivial motions of . Since has max rank, no points of are colinear. Hence, we can pin points of to factor out trivial motions: one point at the origin and another along the -axis at a distance from the origin consistent with all constraints. This yields a pinned framework that lives in . This can be done for all frameworks in a neighborhood of to obtain a neighborhood of 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 of a pinned framework has columns and rank equal to , where is the unpinned framework corresponding to . In this pinned setting, a framework is rigid if it is the only nearby solution to the rigidity map.
Now, assume an unpinned framework is not infinitesimally rigid, so that . Then the , where is the pinned version of . We now set up to apply the implicit function theorem. Our continuously differentiable function is the rigidity map . The Jacobian of is the rigidity matrix. Consider the subset of edges corresponding to the independent rows of , yielding the submatrix . We can find independent columns of . Denote the entries in these columns by the vectors . Denote the entries of the remaining columns by the vectors . The submatrix of induced the is invertible, so by the implicit function theorem, there exists a continuously differentiable function such that and . Hence, the framework of the subgraph is not rigid, and since the rows of span the row space of , is also not rigid. This contradicts our assumption, so is infinitesimally rigid.
Proposition 5. Rigidity is a generic property of graphs.
Proof. Let be a rigid framework of that is generic with respect to rigidity. By definition, there is a neighborhood of rigid frameworks of . By Proposition 1, there is a framework in that is generic with respect to infinitesimal rigidity, so by Proposition 4, 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 of every framework that is generic with respect to rigidity contains a framework that is generic with respect to infinitesimal rigidity, by Proposition 1. Thus, if is rigid then is rigid.
Theorem 1. A graph 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 is generically rigid, then there exists a generic framework with respect to rigidity that is rigid by definition. By Propositions 1 and 4, in any neighborhood of there is a framework that is generic with respect to infinitesimal rigidity and infinitesimally rigid. Hence, by Proposition 2, is generically infinitesimally rigid.
For the other direction, assume to the contrary that is generically infinitesimally rigid, but not generically rigid. Then there exists a generic framework with respect to rigidity that is not rigid by definition. By Proposition 1, in any neighborhood of there is a framework that is generic with respect to infinitesimal rigidity. By assumption is infinitesimally rigid, and by Proposition 3, is also rigid. Thus, must be rigid and, by Proposition 5, all frameworks that are generic with respect to rigidity are rigid. This contradicts our assumption that is not generically rigid.
Maxwell direction The Maxwell Direction of the Geiringer-Laman theorem follows from a simple counting argument on the rigidity matrix.
Maxwell Direction. If a graph has a generic infinitesimally rigid framework, then has a Geiringer-Laman subgraph.
Proof. Let be a generic infinitesimally rigid framework of . By definition, has max rank, i.e., . In particular, has independent rows. Each row of corresponds to an edge of , so the submatrix with just the independent rows corresponds to a subgraph such that . Furthermore, any subgraph of corresponds to a submatrix of . Since the rows of are independent, so are the rows of . Hence, , which clearly satisfies .
Equivalence of generic infinitesimal rigidity and Henneberg constructions 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 has the following recursive definition:
is a single edge or can be obtained from a Henneberg graph via one of the following operations