4 Laman graphs
This section specializes section 3 to \((k,\ell ) = (2,3)\), the case of Laman graphs. Pollaczek-Geiringer [ PG27 ] (pp. 60 and 64), and later Laman [ Lam70 ] , proved that the Laman graphs are exactly the generically minimally rigid graphs in the plane (see Jordán [ Jor16 ] , Theorem 2.2.2). Equivalently, a graph on at least two vertices is generically rigid in the plane if and only if it has a spanning Laman subgraph. We prove this form in section 9.
The direction from Laman graphs to rigidity is proved by induction on the number of vertices. Its base case is a Laman graph on two vertices, and its inductive step deletes a vertex of degree two or three by reversing a Henneberg move (section 5). This section proves the facts about Laman graphs that the induction rests on: the Laman property is invariant under isomorphism, the only Laman graph on two vertices is the complete graph \(K_2\), and in a Laman graph on at least three vertices every vertex has degree at least two.
4.1 Definition and isomorphism invariance
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 \(\varphi \) be an isomorphism from \(G\) to a graph \(H\). If \(G\) is Laman, then so is \(H\).
Specialize lemma 3.12 to \((k, \ell ) = (2, 3)\).
4.2 The base case: \(K_2\)
The first result below is the starting point of the construction of Laman graphs by Henneberg moves, as in the example of theorem 5.14. The second is the base case of the induction in the proof of Laman’s theorem (theorem 9.2).
The complete graph \(K_2\) on two vertices is Laman.
The graph \(K_2\) has one edge, and \(1 + 3 = 2 \cdot 2\). For sparsity, the only set \(s\) of vertices with \(3 \le 2\, |s|\) is the whole vertex set. It spans the one edge (lemma 2.3), and \(1 + 3 \le 2 \cdot 2\).
Let \(G\) be a Laman graph on a set \(V\) of two vertices. Then \(G\) is the complete graph on \(V\).
Since \(|E(G)| + 3 = 2 \cdot 2\), the graph \(G\) has one edge. The complete graph on \(V\) also has exactly one edge, and it contains every edge of \(G\). So the two edge sets are equal.
4.3 Degree bounds
Both lemmas below concern a Laman graph on at least three vertices. The reverse decomposition uses the first to exclude a vertex of degree one (theorem 5.12). Lee and Streinu [ LS08 , Lemma 4 ] give the same argument for \((k,\ell )\)-tight graphs. The second lemma is the Laman form of lemma 3.8.
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 \(v \in V\). The set \(\{ v\} ^c\) has \(|V| - 1 \ge 2\) vertices, so sparsity applies to it: \(|E_{G}[\{ v\} ^c]| + 3 \le 2(|V| - 1)\). By lemma 2.6, \(|E_{G}[\{ v\} ^c]| = |E(G)| - \deg _G(v)\). Since \(|E(G)| + 3 = 2|V|\), this gives \(2|V| - \deg _G(v) \le 2|V| - 2\), that is, \(\deg _G(v) \ge 2\).
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\).