Let \(H\) be a subgraph of a Laman graph \(H'\). Every edge of \(H\) inside a set \(X \subseteq V\) is an edge of \(H'\) inside \(X\), so \(\bigl|E_{H}[X]\bigr| \le \bigl|E_{H'}[X]\bigr| \le 3|X| - 6\) whenever \(|X| \ge 3\).

The edges of \(H\) inside \(X\) are exactly the two-element subsets of \(X\).

Let \(v\) be a vertex of \(G\). Its closed neighborhood \(N_G[v]\) is a clique of \(G^2\) on \(d_G(v) + 1\) vertices (lemma 25.2). If \(d_G(v) \ge 4\), five of these vertices form a clique of \(G^2\), which spans \(\binom {5}{2} = 10 {\gt} 3 \cdot 5 - 6\) edges of \(G^2\) (lemma 27.4). Then \(G^2\) is not Laman. So \(d_G(v) \le 3\).

The partition \(P'\) has \(|Q| - 1\) fewer parts than \(P\). An edge joins different parts of \(P'\) exactly when it joins different parts of \(P\) and does not join two members of \(Q\), so \(d_G(P') = d_G(P) - e_G(Q)\). The identity follows from the definition of the value (definition 20.3); when \(|Q| = 1\), it says that \(P' = P\) has the value of \(P\). Read from right to left, it gives the change in value when a part is split into several: if a part of \(P'\) is split into the members of \(Q\), the value rises by \(D(|Q| - 1) - (D-1)\, e_G(Q)\).

Merging the members of \(Q\) changes the value of \(P\) by \((D-1)\, e_G(Q) - D(|Q| - 1)\) (lemma 27.7). The merged partition has value at most \(\operatorname {def}(\tilde G)\), which is the value of \(P\) because \(P\) is tight. So the change is at most zero.

Let \(A \in P\) with \(|A| \ge 2\), let \(v \in A\), and let \(m\) be the number of neighbors of \(v\) in \(A\). Splitting \(v\) off \(A\) as a part of its own raises the value of \(P\) by \(D - (D-1)\, m\) (lemma 27.7, read from right to left with \(Q = \{ A \setminus \{ v\} , \{ v\} \} \)). As \(P\) is tight, the value does not rise, so \(D \le (D-1)\, m\). Since \(D \ge 2\), this forces \(m \ge 2\). So \(A\) contains \(v\) and at least two neighbors of \(v\).

Let \(A \ne B\) be parts of \(P\). For \(Q = \{ A, B\} \), lemma 27.8 gives \((D-1)\, e_G(Q) \le D\). If \(e_G(Q) \ge 2\), then \(2(D-1) \le D\), that is, \(D \le 2\), against \(D \ge 3\).

Let \(u\) and \(w\) lie in distinct parts of \(P\), and suppose that they have two common neighbors \(v \ne v'\). The vertices \(u, v, w, v'\) are distinct, as \(u \ne w\) and adjacent vertices are distinct. So \(uv\), \(vw\), \(wv'\) and \(v'u\) are four distinct edges of \(G\), and they form a closed walk.

Let \(Q\) be the set of parts of \(P\) that meet \(\{ u, v, w, v'\} \), so that \(2 \le |Q| \le 4\). The walk meets at least two parts, so it enters every member of \(Q\) from another member at least once. These entries use distinct edges, each joining two members of \(Q\), so \(e_G(Q) \ge |Q|\). Now lemma 27.8 gives \((D-1)\, |Q| \le D(|Q| - 1)\), that is, \(D \le |Q| \le 4\), a contradiction. When \(|Q| = 2\), two of the four edges join the same two parts, which lemma 27.10 excludes directly.

An edge of \(G^2\) lies inside a part or joins two parts. In the latter case it is an edge of \(G\) or a cross edge, and a cross edge is normal or special. The first three classes are disjoint by definition. The last two are disjoint because the common neighbor of a cross edge is unique (lemma 27.11).

Let \(uw\) be a special cross edge with common neighbor \(v\). Then \(u\) and \(w\) are two neighbors of \(v\) outside its part. If the part of \(v\) were not a singleton, \(v\) would also have two neighbors inside it (lemma 27.9), and so degree at least four. This contradicts the degree bound (lemma 27.5). Now let \(uw\) be a normal cross edge with common neighbor \(v\). As \(u\) and \(w\) lie in distinct parts, \(v\) shares its part with exactly one of them. This part contains two adjacent vertices, so it is not a singleton, and it has at least three vertices (lemma 27.9).

The neighborhood \(N_G(v)\) is a clique of \(G^2\) (lemma 25.2). Let \(u \ne w\) be neighbors of \(v\). Neither lies in the part \(\{ v\} \). They do not lie in one part \(A\), as then \(vu\) and \(vw\) would be two edges between \(A\) and \(\{ v\} \) (lemma 27.10). They are not adjacent in \(G\). Otherwise the triangle \(uvw\) would put three edges between the three parts that contain \(u\), \(v\) and \(w\). Then \(3(D - 1) \le 2D\) (lemma 27.8), that is, \(D \le 3\), while \(D = 6\). So \(uw\) is a cross edge with common neighbor \(v\). It is special, as the part \(\{ v\} \) contains neither \(u\) nor \(w\).

Finally, \(v\) has degree two or three (lemma 27.5). So the clique has \(\binom {d_G(v)}{2} = 2\, d_G(v) - 3\) edges (lemma 27.4).

Let \(uw\) be a special cross edge with common neighbor \(v\). Then \(\{ v\} \) is a part of \(P\) (lemma 27.13), and \(u, w \in N_G(v)\). If also \(u, w \in N_G(v')\) for a singleton part \(\{ v'\} \), then \(v'\) is a common neighbor of \(u\) and \(w\), so \(v' = v\) (lemma 27.11).

The common neighbor of a normal cross edge is unique (lemma 27.11), so the edge is rooted at exactly one part. This part has at least three vertices by lemma 27.13.

By lemma 27.9, \(v\) has at least two neighbors in \(A\). It has at most three neighbors (lemma 27.5), and one of them lies outside \(A\). So exactly two lie in \(A\).

The vertices \(u\) and \(w\) lie in distinct parts, and both are neighbors of \(v\). So \(uw\) is an edge of \(G^2\) (lemma 25.2) that joins two parts. It is not an edge of \(G\). Otherwise \(vw\) and \(uw\) would be two edges between the part of \(v\) and that of \(w\) (lemma 27.10). So \(uw\) is a cross edge, and \(v\) is its common neighbor (lemma 27.11). As \(v\) lies in the part of \(u\), the cross edge is normal and rooted at the part of \(v\).

The map \(u \mapsto uw\) is injective on \(N_G(v) \cap A\), as no vertex of \(A\) is \(w\). So there are as many edges \(uw\) as neighbors of \(v\) in \(A\), that is, two (lemma 27.20). Each is a normal cross edge rooted at \(A\) (lemma 27.21).

An edge of \(G\) with exactly one endpoint in \(A\) is \(vw\) for exactly one of these pairs, the one with \(v \in A\). By lemma 27.21, every edge \(uw\) with \(u \in N_G(v) \cap A\) is a normal cross edge rooted at \(A\). Conversely, let \(e\) be a normal cross edge rooted at \(A\), with common neighbor \(v \in A\). Exactly one endpoint \(u\) of \(e\) lies in \(A\) (lemma 27.13). Let \(w\) be the other. Then \((v, w)\) is one of the pairs, and \(e = uw\) with \(u \in N_G(v) \cap A\).

Finally, let \(uw\), with \(u \in A\), lie in the sets of two pairs \((v, w)\) and \((v', w')\). Then \(w' = w\), as \(w\) is the endpoint outside \(A\). So \(v\) and \(v'\) are common neighbors of \(u\) and \(w\), and \(v = v'\) (lemma 27.11).

By lemma 27.24, the normal cross edges rooted at \(A\) are the disjoint union of \(d_G(A)\) sets, one for each edge of \(G\) with exactly one endpoint in \(A\). Each of these sets has exactly two elements (lemma 27.22).

Let \(P\) be a tight partition of \(V\) (lemma 20.6), and let \(t\) be its number of parts. Let \(C_n\) and \(C_s\) be the numbers of normal and of special cross edges. By lemma 27.13,

Each part has one vertex or at least three (lemma 27.9). A singleton part spans no edge, and a part \(A\) with \(|A| \ge 3\) spans at most \(3|A| - 6\) edges of \(G^2\), as \(G^2\) is Laman.

We count each cross edge at its root (definition 27.17), the part that contains its common neighbor, which is unique (lemma 27.11). No normal cross edge is rooted at a part \(A\) unless \(|A| \ge 3\) (lemma 27.19). So \(C_n\) is the sum of \(2\, d_G(A)\) over the parts \(A\) with \(|A| \ge 3\) (lemma 27.25), which is JJ eq. (6).

The special cross edges are rooted at singleton parts (lemma 27.13). Those rooted at \(\{ v\} \) have common neighbor \(v\), so they lie inside \(N_G(v)\). Conversely, the edges of \(G^2\) inside \(N_G(v)\) are special cross edges with common neighbor \(v\), and there are \(2\, d_G(v) - 3\) of them (lemma 27.15). So \(C_s\) is the sum of \(2\, d_G(v) - 3\) over the singleton parts \(\{ v\} \), which is JJ eqs. (5) and (7).

For a singleton part \(A = \{ v\} \) we have \(d_G(A) = d_G(v)\), so \(2\, d_G(v) - 3 = (3|A| - 6) + 2\, d_G(A)\). Hence, for each part \(A\), the edges of \(G^2\) inside \(A\) and the cross edges counted at \(A\) number at most \(3|A| - 6 + 2\, d_G(A)\), and

Here \(\sum _A |A| = |V|\), and \(\sum _A d_G(A) = 2\, d_G(P)\), as an edge that joins two parts has one endpoint in each. The right-hand side is \(3|V| - 6 - \operatorname {def}_{\tilde G}(P)\) (definition 20.3, at \(D = 6\)), and \(\operatorname {def}_{\tilde G}(P) = \operatorname {def}(\tilde G)\), as \(P\) is tight.

Let \(X \subseteq V\) with \(|X| \ge 3\). If \(|X| = 3\), then \(X\) spans at most \(3 = 3|X| - 6\) edges. Let \(|X| \ge 4\), let \(H[X]\) be the subgraph of \(H\) induced on \(X\), and let \(p|_X\) be the restriction of \(p\) to \(X\). The row of an edge of \(H[X]\) at \(p|_X\), composed with the restriction \(({\mathbb {R}}^3)^V \to ({\mathbb {R}}^3)^X\), is the row of \(H\) at \(p\) indexed by the same edge. The rows of \(H\) at \(p\) are linearly independent, so the rows of \(H[X]\) at \(p|_X\) are too, and their number is the rank of \(R(H[X], p|_X)\), as in the proof of lemma 9.12:

The points \(p(v)\), \(v \in X\), affinely span \({\mathbb {R}}^3\), so this rank is at most \(3|X| - 6\) (lemma 9.10, at \(d = 3\)).

Choose a placement \(p\) of \(V\) in \({\mathbb {R}}^3\) that is generic for row independence and in general position up to order four (lemma 25.17). As \(E(H)\) is independent, it is row-independent at some placement (lemma 24.4), and hence at \(p\), since \(p\) is generic. A set of at least four vertices contains four whose points are affinely independent (definition 25.16), and four affinely independent points affinely span \({\mathbb {R}}^3\). So lemma 27.28 applies at \(p\).

The points \(p'(u_1), \dots , p'(u_s)\) are affinely independent and \(s \le 3\), so their affine hull is a proper affine subspace of \({\mathbb {R}}^3\). Choose a point \(q\) outside it, and let \(p\) place \(v\) at \(q\) and agree with \(p'\) elsewhere. The vectors \(q - p'(u_i)\) are linearly independent. Indeed, let \(\sum _i c_i \bigl(q - p'(u_i)\bigr) = 0\). If \(\sum _i c_i \ne 0\), then \(q\) is an affine combination of the points \(p'(u_i)\), which it is not. So \(\sum _i c_i = 0\), the relation reads \(\sum _i c_i\, p'(u_i) = 0\), and every \(c_i\) is zero by affine independence.

The edges of \(H\) are the edges of \(H'\) and the edges \(vu_i\). Neither end of an edge of \(H'\) is \(v\), so its row at \(p\) is its row at \(p'\) (lemma 6.4). Suppose that a linear combination of the rows of \(E(H)\) at \(p\) vanishes, with coefficient \(c_i\) at the row of \(vu_i\). For \(\alpha \in {\mathbb {R}}^3\), let \(x^{\alpha }\) give \(v\) the velocity \(\alpha \) and every other vertex the velocity zero, as in the proof of lemma 10.2. The rows of the edges of \(H'\) vanish at \(x^{\alpha }\), and the row of \(vu_i\) takes the value \(\langle q - p'(u_i),\, \alpha \rangle \). Evaluating the relation at every \(x^{\alpha }\) gives \(\sum _i c_i \bigl(q - p'(u_i)\bigr) = 0\), so every \(c_i\) is zero. What remains is a vanishing combination of the rows of \(E(H')\) at \(p'\), and its coefficients are zero, as \(E(H')\) is row-independent at \(p'\).

Let \(H' = H - E_H(v)\) and \(s = d_H(v)\). The edges of \(H\) are the edges of \(H'\) and the \(s\) edges at \(v\). Adding \(s\) elements to a set raises its rank by at most \(s\), so \(r(H) \le r(H') + s\).

For the reverse inequality, choose a placement \(p'\) of \(V\) in \({\mathbb {R}}^3\) that is generic for row independence and in general position up to order four (lemma 25.17). Let \(J\) be a maximal independent subset of \(E(H')\), so that \(|J| = r(H')\), and let \(H_J\) be the graph whose edges are those of \(J\) and the \(s\) edges at \(v\). Then \(H_J - E_{H_J}(v)\) has edge set \(J\). As \(p'\) is generic, \(J\) is row-independent at \(p'\) (lemma 24.4). The neighbors of \(v\) in \(H_J\) are its \(s \le 3\) neighbors in \(H\), and their points are affinely independent, as \(p'\) is in general position (definition 25.16). So \(E(H_J)\) is row-independent at some placement (lemma 27.30), that is, independent in \(\mathcal{R}_3(V)\). It is a subset of \(E(H)\) with \(r(H') + s\) elements, so \(r(H) \ge r(H') + s\).

Finally, \(|E(H)| = |E(H')| + s\), and a finite edge set is independent exactly when its rank equals its size. So \(E(H)\) is independent if and only if \(E(H')\) is.

Let \(H' = H - E_H(v)\) and \(s = d_H(v)\). If \(s \le 3\), the claim is corollary 27.31. Let \(s \ge 4\), fix three neighbors \(u_1, u_2, u_3\) of \(v\), and let \(H_3\) be \(H'\) together with the edges \(vu_1\), \(vu_2\) and \(vu_3\). Then \(H_3 - E_{H_3}(v) = H'\) and \(d_{H_3}(v) = 3\), so \(r(H_3) = r(H') + 3\) (corollary 27.31). As \(E(H_3) \subseteq E(H)\), this gives \(r(H) \ge r(H') + 3\). This lower bound holds without the clique hypothesis.

For the upper bound we show that every further edge \(vw\), with \(w \in N_H(v) \setminus \{ u_1, u_2, u_3\} \), lies in the closure of \(E(H_3)\) in \(\mathcal{R}_3(V)\). Then \(E(H)\) lies in this closure, and \(r(H) \le r(H_3) = r(H') + 3\). As \(N_H(v)\) is a clique, the five vertices \(v, u_1, u_2, u_3, w\) span a complete graph \(K_5\) in \(H\). Its edges other than \(vw\) lie in \(E(H_3)\): the edges \(vu_i\) by construction, and the six edges among \(u_1, u_2, u_3, w\) because they are edges of \(H\) not at \(v\).

These nine edges are independent. Indeed, starting from the graph with no edges, join \(u_2\) to \(u_1\), then \(u_3\) to \(u_1\) and \(u_2\), then \(w\) to \(u_1\), \(u_2\) and \(u_3\), and last \(v\) to \(u_1\), \(u_2\) and \(u_3\). Each step is a \(0\)-extension at a vertex of degree at most three, which preserves independence (corollary 27.31). All ten edges of the \(K_5\) are dependent. Otherwise the graph they form would be Laman (corollary 27.29). But its five vertices form a clique, which spans \(\binom {5}{2} = 10 {\gt} 3 \cdot 5 - 6\) edges (lemma 27.4). Hence \(vw\) lies in the closure of the other nine edges, and so in the closure of \(E(H_3)\).

Let \(q\) be a placement of \(S\) in \({\mathbb {R}}^d\), and let \(p\) be a placement of \(V\) that agrees with \(q\) on \(S\). The row at \(p\) of an edge of \(H\) is its row at \(q\) composed with the restriction \(\rho \colon ({\mathbb {R}}^d)^V \to ({\mathbb {R}}^d)^S\), as in the proof of lemma 9.12. Since \(\rho \) is surjective, the rows of the edges of \(H\) at \(p\) are linearly independent if and only if their rows at \(q\) are. Every placement of \(S\) extends to one of \(V\), and every placement of \(V\) restricts to one of \(S\). By lemma 24.4, this proves the first claim.

The inclusion maps the subsets of \(E(H)\) bijectively onto the subsets of its image, preserving their size. By the first claim, applied to the subgraphs of \(H\), it also preserves independence. The rank of a set is the largest size of an independent subset, so the two ranks are equal.

Neither side has an edge at \(v\). Let \(x \ne y\) be vertices other than \(v\). If \(v\) were a common neighbor of \(x\) and \(y\), it would have two neighbors. So \(x\) and \(y\) are adjacent or have a common neighbor in \(G\) if and only if they do in \(G - E_G(v)\). That is, \(xy\) is an edge of \(G^2\) if and only if it is an edge of \((G - E_G(v))^2\) (definition 25.1).

Let \(w \ne v\). If \(w\) is adjacent to \(v\), then \(w = u\). If \(w\) and \(v\) have a common neighbor, then it is \(u\), so \(w \in N_G(u)\). Conversely, \(u\) is adjacent to \(v\), and every vertex of \(N_G(u)\) other than \(v\) has the common neighbor \(u\) with \(v\). This proves the identity. As \(v \in N_G(u)\), the set \(N_G[u] \setminus \{ v\} \) has \(d_G(u)\) elements. It lies in \(N_G[u]\), which is a clique of \(G^2\) (lemma 25.2).

Each end of an edge of \(G^2\) lies on an edge of \(G\), so it lies in \(S\). Let \(x \ne y\) lie in \(S\). An edge \(xy\) of \(G\) is an edge of \(G[S]\). A common neighbor of \(x\) and \(y\) in \(G\) lies on an edge of \(G\), so it lies in \(S\), and it is a common neighbor of \(x\) and \(y\) in \(G[S]\). So \(xy\) is an edge of \(G[S]^2\) if and only if it is an edge of \(G^2\).

A set \(X \subseteq S\) of at least three vertices spans the same edges in \(G[S]\) as in \(G\), and so at most \(3|X| - 6\) of them.

The rank of a finite set is at most its size, with equality if and only if the set is independent. By theorem 27.26 and the rank formula (corollary 26.8),

So \(r(G^2) = |E(G^2)|\), and \(E(G^2)\) is independent.

Independence implies the Laman condition by corollary 27.29. For the converse, suppose that \(G^2\) is Laman. We show that \(E(G^2)\) is independent, by induction on the number of edges of \(G\).

Suppose first that \(G\) has a vertex \(v\) of degree one, with neighbor \(u\), and let \(G' = G - E_G(v)\). Then \(G'^2 = G^2 - E_{G^2}(v)\) (lemma 27.34). So \(G'^2\) is Laman (lemma 27.3), and \(E(G'^2)\) is independent by induction, as \(G'\) has one edge fewer than \(G\). In \(G^2\) the vertex \(v\) has degree \(d_G(u)\) (lemma 27.35), and \(d_G(u) \le 3\) (lemma 27.5). So \(E(G^2)\) is independent because \(E(G'^2)\) is (corollary 27.31).

Otherwise every vertex of \(G\) has degree zero or at least two. If \(G\) has no edges, then \(G^2\) has none either, and the empty set is independent. Else let \(S\) be the set of non-isolated vertices of \(G\). Every edge of \(G^2\) lies inside \(S\), and the square of the induced subgraph \(G[S]\) is the subgraph of \(G^2\) induced on \(S\) (lemma 27.36). So \(G[S]^2\) is Laman (lemma 27.37). A vertex of \(S\) has the same neighbors in \(G[S]\) as in \(G\), so \(G[S]\) has minimum degree at least two. Hence \(E(G[S]^2)\) is independent in \(\mathcal{R}_3(S)\) (theorem 27.38, on the nonempty set \(S\)). Its image under the inclusion \(S \hookrightarrow V\) is \(E(G^2)\), which is therefore independent in \(\mathcal{R}_3(V)\) (lemma 27.33).

The first two claims hold by definition. A vertex of the support of the core lies on an edge of some subgraph \(H\) as in the definition. So it has at least two neighbors in \(H\), and hence in the core.

If every vertex of the support of \(G\) has degree at least two, then \(G\) is one of the subgraphs \(H\) that define the core. So \(G\) is a subgraph of its core, which is a subgraph of \(G\) (lemma 27.41).

Let \(v\) have degree at most one. A vertex of the support of the core has degree at least two in the core, and so in \(G\), as the core is a subgraph of \(G\) (lemma 27.41). So \(v\) is not in the support of the core. A subgraph of \(G\) in which every vertex of the support has degree at least two has no edge at \(v\), as \(v\) has degree at most one. So \(G\) and \(G - E_G(v)\) have the same such subgraphs, and the same core.

We induct on \(|V|\). If \(|V| = 2\), then \(G\) is a single edge, and \(G^2 = G\). Deleting the edge at one of its ends leaves no edge, so \(r(G^2) = 1\) (corollary 27.31). And \(2 \cdot 2 - 5 + 2 = 1\).

Let \(|V| \ge 3\), and let \(v\) be a vertex of degree one, with neighbor \(u\). Then \(d_G(u) \ge 2\), as otherwise \(\{ u, v\} \) would be a connected component of \(G\). The graph \(G - v\) is a tree on \(|V| - 1\) vertices, and its square is \(G^2 - v\) (lemma 27.34). In \(G^2\) the vertex \(v\) has \(d_G(u)\) neighbors, and they form a clique (lemma 27.35). So

(corollary 27.32).

The term \(2|V|\) is two less for \(G - v\) than for \(G\). If \(d_G(u) \ge 3\), then \(V_1(G - v) = V_1(G) \setminus \{ v\} \), so the right-hand side of the formula is three less for \(G - v\). If \(d_G(u) = 2\), then \(V_1(G - v)\) is \(V_1(G)\) with \(u\) in place of \(v\), so the right-hand side is two less. In both cases it falls by \(\min (3, d_G(u))\), as the rank does. So the formula for \(G - v\), which holds by induction, gives the formula for \(G\).

We induct on \(|V|\). If \(V_1(G)\) is empty, then every vertex of \(G\) has degree at least two, as \(G\) is connected and \(|V| \ge 2\). So \(G\) is its own core (lemma 27.42), its support is \(V\), and both sides equal \(r(G^2)\).

Otherwise let \(v\) be a vertex of degree one, with neighbor \(u\). Then \(d_G(u) \ge 2\), as otherwise \(G\) would be the single edge \(uv\), a tree. A connected graph is a tree exactly when it has one edge fewer than vertices, so \(G\) has at least as many edges as vertices. Deleting \(v\) removes one vertex and one edge. So \(G - v\) is connected, has at least two vertices, and is not a tree. As in the proof of theorem 27.43, \(r(G^2) = r((G - v)^2) + \min (3, d_G(u))\).

Deleting \(v\) does not change the core, and \(v\) is not in \(V(G^{\mathrm{core}})\) (lemma 27.42). So \(|V \setminus V(G^{\mathrm{core}})|\) is one less for \(G - v\) than for \(G\). The set \(V_1\) changes as in the proof of theorem 27.43. So the right-hand side falls by \(2 + 1 = 3\) if \(d_G(u) \ge 3\), and by \(2\) if \(d_G(u) = 2\). In both cases it falls by \(\min (3, d_G(u))\), as the rank does, and the formula for \(G - v\), which holds by induction, gives the formula for \(G\).