For the count we follow Katoh and Tanigawa  [ KT11 , p. 658 ] . As \(X\) is a circuit, \(X - e\) is independent, so \(\tilde G \restriction (X - e)\) is \((D, D)\)-sparse (lemma 20.35). If \(X - e\) is not empty, sparsity applied to \(X - e\) itself gives

If \(X - e\) is empty, the bound holds as \(V(X)\) is not empty. Conversely, \(X\) is dependent, so some nonempty \(F \subseteq X\) has \(|F| {\gt} D(|V(F)| - 1)\) (definition 20.1). If \(F\) were a proper subset of \(X\), it would miss some \(f \in X\) and lie in the independent set \(X - f\), whose sparsity gives \(|F| \le D(|V(F)| - 1)\). Hence \(F = X\), and \(|X| {\gt} D(|V(X)| - 1)\), that is, \(|X - e| \ge D(|V(X)| - 1)\). So \(|X - e| = D(|V(X)| - 1)\).

If \(X - e\) is empty, then \(|V(X)| = 1\), and the \(D\) spanning trees are empty. Otherwise both inequalities above are equalities, so \(V(X - e) = V(X)\), and the multigraph on \(V(X)\) with the edges \(X - e\) is \((D, D)\)-tight. It is connected, by the count in the proof of lemma 20.14. By corollary 16.19, \(X - e\) is the union of \(D\) edge-disjoint spanning trees on \(V(X)\).

Let \(H = G[V(X)]\). The ends of each edge of \(X\) lie in \(V(X)\), so \(X \subseteq E(\tilde H)\). Hence \(X - e\) is independent in \(M(\tilde G)\, |\, E(\tilde H)\), which is \(M(\tilde H)\) (lemma 20.24). So \(\operatorname {rank} M(\tilde H) \ge |X - e| = D(|V(H)| - 1)\), and the reverse inequality is lemma 20.9. By KT eq. (2.4) (theorem 20.12), \(\operatorname {def}(\tilde H) = 0\). As \(H\) is a subgraph of \(G\), it is a rigid subgraph of \(G\).

By KT eq. (2.4) (theorem 20.12), \(\operatorname {rank} M(\tilde H) + \operatorname {def}(\tilde H) = D(|V(H)| - 1)\), and \(\operatorname {def}(\tilde H) = 0\) as \(H\) is rigid.

A matroid \(M\) on \(E\) and a set \(T \subseteq E\) satisfy \(\operatorname {rank}(M/T) = \operatorname {rank} M - r_M(T)\), by Proposition 3.1.6 of Oxley  [ Oxl11 ] at \(X = E \setminus T\). Take \(M = M(\tilde G)\) and \(T = E(\tilde H)\). Then \(r_M(T)\) is the rank of \(M(\tilde G)\, |\, E(\tilde H)\), which is \(M(\tilde H)\) (lemma 20.24).

By lemma 21.5 and lemma 21.4,

The vertex set of \(G\) contains that of \(H\), so it is not empty, and KT eq. (2.4) (theorem 20.12) gives \(\operatorname {rank} M(\tilde G) = D(|V(G)| - 1) - \operatorname {def}(\tilde G)\). Substituting this into the first identity gives the lemma. This is Katoh and Tanigawa’s count  [ KT11 , p. 658 ] .

Let \(B'\) be a base of \(M(\tilde G)/E(\tilde H)\), and let \(J\) be a maximal subset of \(E(\tilde H)\) that is independent in \(M(\tilde G)\). By Corollary 3.1.8 of Oxley  [ Oxl11 ] , \(B' \cup J\) is a base of \(M(\tilde G)\). Let \(e\) be an edge of \(G\) that is not an edge of \(H\). As \(G\) is minimal, \(B' \cup J\) meets \(\tilde e\). The copies of \(e\) are not in \(E(\tilde H)\), which contains \(J\), so \(B'\) meets \(\tilde e\). This is Katoh and Tanigawa’s argument  [ KT11 , p. 659 ] .

As \(H\) is proper, it has at least two vertices, and \(\operatorname {def}(\tilde G) = k\) as \(G\) is a \(k\)-dof-graph. So the identity is lemma 21.6, and the second claim is lemma 21.7.

By lemma 21.8,

and every base of \(M(\tilde G)/E(\tilde H)\) meets \(\tilde e\) for every edge \(e\) of \(G\) not in \(H\). These edges are the edges of \(G/E(H)\), and their copies form the common ground set of \(M(\tilde G)/E(\tilde H)\) and \(M(\widetilde{G/E(H)})\). We show below that

Then every base of \(M(\widetilde{G/E(H)})\) meets the copies of every edge of \(G/E(H)\). The graph \(G/E(H)\) has \(|V(G)| - |V(H)| + 1\) vertices (lemma 21.51), so KT eq. (2.4) (theorem 20.12) gives

Hence \(G/E(H)\) is a minimal \(k\)-dof-graph.

The identity is not a renaming of edges. Let \(M_c\) be the cycle matroid of \(\tilde G\), so that \(M(\tilde G)\) is the union of \(D\) copies of \(M_c\) (definition 20.1). As \(H\) is rigid, it is connected (lemma 20.18), and so is \(\tilde H\), since \(D \ge 2\) gives every edge of \(H\) a copy in \(\tilde H\). So contracting the edges of \(\tilde H\) in \(\tilde G\) identifies all the vertices of \(H\), and gives \(\widetilde{G/E(H)}\). The cycle matroid of \(\widetilde{G/E(H)}\) is therefore \(M_c/E(\tilde H)\)  [ Oxl11 , Proposition 3.2.1 ] . So \(M(\widetilde{G/E(H)})\) is the union of \(D\) copies of \(M_c/E(\tilde H)\), while \(M(\tilde G)/E(\tilde H)\) is the contraction of the union of \(D\) copies of \(M_c\). In general a union of matroids does not commute with contraction. Let \(M\) be the matroid of rank one on two elements \(a\) and \(c\), neither of which is a loop. Then \(a\) is independent in the contraction by \(c\) of the union of two copies of \(M\), but \(a\) is a loop of \(M/c\), and so of the union of two copies of \(M/c\).

The two matroids coincide here because the union attains \(D\) times the cycle rank on \(E(\tilde H)\). Let \(r_c\) be the rank function of \(M_c\). The rank of \(E(\tilde H)\) in \(M(\tilde G)\) is the rank of \(M(\tilde H)\) (lemma 20.24), which is \(D(|V(H)| - 1)\) as \(H\) is rigid (lemma 21.4). The connected graph \(\tilde H\) has \(r_c(E(\tilde H)) = |V(H)| - 1\). So

Hence a base of \(E(\tilde H)\) in \(M(\tilde G)\) has \(D(|V(H)| - 1)\) elements. It is the union of \(D\) disjoint forests in \(\tilde H\) (theorem 16.18), each with at most \(|V(H)| - 1\) edges, and so each of them is a spanning tree on \(V(H)\). This is Katoh and Tanigawa’s (3.1)  [ KT11 , p. 658 ] , on which their proof of Lemma 3.5 rests.

We derive the identity from this equality. A set \(X\) is independent in the union of \(D\) copies of a matroid with rank function \(\rho \) if and only if \(|Y| \le D\, \rho (Y)\) for every \(Y \subseteq X\) (theorem 15.11). Let \(C = E(\tilde H)\), let \(J\) be a base of \(C\) in \(M(\tilde G)\), so that \(|J| = D\, r_c(C)\), and let \(I\) be a set of copies of edges not in \(H\). Then \(I\) is independent in \(M(\tilde G)/C\) if and only if \(I \cup J\) is independent in \(M(\tilde G)\)  [ Oxl11 , Proposition 3.1.7 ] , that is, if and only if \(|Z| \le D\, r_c(Z)\) for every \(Z \subseteq I \cup J\). The rank function of \(M_c/C\) is \(Y \mapsto r_c(Y \cup C) - r_c(C)\)  [ Oxl11 , Proposition 3.1.6 ] . So \(I\) is independent in the union of \(D\) copies of \(M_c/C\) if and only if \(|Y| \le D\, \bigl(r_c(Y \cup C) - r_c(C)\bigr)\) for every \(Y \subseteq I\).

Suppose this second condition, and let \(Z \subseteq I \cup J\). Write \(Z = Y \cup W\) with \(Y \subseteq I\) and \(W \subseteq J\). Since \(W \subseteq C\), submodularity gives \(r_c(Y \cup C) + r_c(W) \le r_c(Y \cup W) + r_c(C)\). Also \(|W| \le D\, r_c(W)\), as \(J\) is independent in \(M(\tilde G)\). Adding these two bounds to the bound for \(Y\) gives \(|Z| \le D\, r_c(Z)\). Conversely, suppose the first condition, and let \(Y \subseteq I\). Then

So the two matroids have the same independent sets. The converse used \(|J| = D\, r_c(C)\), and it fails without it, as in the example above.

The graphs \(G_v\) and \(G_v^{ab}\) both have the vertices of \(G\) other than \(v\). An edge of \(G_v\) is an edge of \(G\) whose ends differ from \(v\), with the same ends. It is not the new edge \(ab\), which is not an edge of \(G\), so it is an edge of \(G_v^{ab}\) with the same ends. Hence \(G_v\) is a subgraph of both graphs, and the new edge \(ab\) is an edge of \(G_v^{ab}\) but not of \(G\). An edge of \(G\) whose ends both differ from \(v\) is an edge of \(G_v\), which gives the last assertion.

By definition 20.1, \(M(\tilde G)\) is the union of \(D\) copies of the cycle matroid of \(\tilde G\). The independent sets of the cycle matroid are the forests (section 16.1). The independent sets of a union of matroids are the unions of independent sets of the matroids (lemma 15.8).

Let \(G_v = G - v\) (definition 21.10), and let \(B_0 = B \setminus (\tilde e_a \cup \tilde e_b)\). An edge of \(B_0\) is a copy of an edge of \(G\) other than \(e_a\) and \(e_b\), so it is not incident with \(v\). Hence \(B_0\) is a set of edges of \(\widetilde{G_v}\). It is independent in \(M(\tilde G)\), and hence in the restriction \(M(\widetilde{G_v})\) of \(M(\tilde G)\) (lemma 20.24). So \(|B_0| \le \operatorname {rank} M(\widetilde{G_v})\).

The multigraph \(G_v\) has the vertex \(a\), so KT eq. (2.4) (theorem 20.12) applies to \(G\) and to \(G_v\):

Hence

The last step is KT Lemma 4.4 (lemma 21.38), which uses \(D \ge 2\): it gives \(\operatorname {def}(\tilde G) \le \operatorname {def}(\widetilde{G_v})\). Remark 21.15 uses this count to find a balanced partition of a base.

In \(\tilde G \restriction (F \cup \{ x\} )\) the only edge incident with \(v\) is \(x\), and \(x\) is not a loop. So deleting \(x\) leaves \(v\) isolated, and in particular separates \(v\) from \(w\): the edge \(x\) is a bridge. A bridge lies on no cycle, and \(F\) contains no cycle, so \(F \cup \{ x\} \) contains none. The argument uses only that no edge of \(F\) is incident with \(v\), not the degree of \(v\). Remark 21.15 uses the lemma to move an edge at \(v\) between the forests of a partition of a base.

The set \(F'_j\) is a forest by lemma 21.19, and each \(F'_i\) with \(i \neq j\) is a forest as a subset of \(F_i\). The union is still \(I\), since \(x \in I\) moves from the other forests to \(F'_j\).

By lemma 21.17, \(B\) is the union of \(D\) forests, which we make pairwise disjoint as above. We induct on the number of these forests with no edge incident with \(v\). If there is none, we are done. Otherwise let \(F_j\) be one. By lemma 21.18, \(B\) contains at least \(D\) edges incident with \(v\), and they lie in the \(D - 1\) forests other than \(F_j\). So one of these, \(F_i\), contains two of them. Let \(x\) be one of the two. It joins \(v\) to \(a\) or to \(b\).

Move \(x\) from \(F_i\) to \(F_j\) (lemma 21.20): the new \(F_j\) is a forest by lemma 21.19, and the forests still have union \(B\). They are still pairwise disjoint, since \(x\) lay in \(F_i\) only. Now \(F_j\) has an edge incident with \(v\), and \(F_i\) keeps its other one. So the number of forests with no edge incident with \(v\) drops by one, and the induction hypothesis gives the partition. Katoh and Tanigawa’s proof of their Lemma 4.1 assumes such a partition (remark 21.15).

The edges of \(\tilde G\) not incident with \(v\) are the edges of \(\widetilde{G_v}\), where \(G_v = G - v\) (definition 21.10). As \(G_v\) is a subgraph of \(G_v^{ab}\), they are edges of \(\widetilde{G_v^{ab}}\) with the same ends. Those of them in \(F\) contain no cycle, since \(F\) contains none.

Let \(F_0 = F \setminus \{ p_a, p_b\} \), the set of edges of \(F\) not incident with \(v\). By lemma 21.22, \(F_0\) is a forest of \(\widetilde{G_v^{ab}}\), so a cycle \(C\) of \(F_0 \cup \{ r\} \) passes through \(r\). Then \(C - r\) is a path from \(a\) to \(b\) in \(F_0\). Its edges have the same ends in \(\tilde G\), and it does not pass through \(v\). So together with \(p_a\) and \(p_b\) it forms a cycle of \(\tilde G\) in \(F\), which is impossible. Hence \(F_0 \cup \{ r\} \) contains no cycle.

Two copies of an edge form a cycle, so each \(F_i\) has at most one edge in \(\tilde e_a\) and at most one in \(\tilde e_b\). These are its only edges incident with \(v\), and it has at least one, so it has one or two. Let \(h'\) be the number of forests with two, and let \(h = |(\tilde e_a \cup \tilde e_b) \cap I|\). As the \(F_i\) are disjoint, \(h = 2h' + (D - h') = D + h'\). As \(|\tilde e_a \cup \tilde e_b| = 2(D - 1)\), also \(h \le 2(D - 1)\), so \(h' \le D - 2\).

Since \(\widetilde{ab}\) has \(D - 1 {\gt} h'\) elements, we can choose a different copy \(r_i \in \widetilde{ab}\) for each forest \(F_i\) with two edges incident with \(v\). For such an \(i\), let \(F'_i\) be obtained from \(F_i\) by replacing these two edges by \(r_i\). It is a forest of \(\widetilde{G_v^{ab}}\) by lemma 21.23. For every other \(i\), let \(F'_i\) be \(F_i\) without its edge incident with \(v\), a forest of \(\widetilde{G_v^{ab}}\) by lemma 21.22. In both cases \(|F'_i| = |F_i| - 1\).

The edges of the \(F'_i\) other than the \(r_i\) lie in the disjoint sets \(F_i\), and none of them is a copy of \(ab\). So the \(F'_i\) are pairwise disjoint, and their union \(I'\) has \(|I'| = \sum _i |F_i| - D = |I| - D\). Its copies of \(ab\) are the \(h'\) copies \(r_i\), so \(|\widetilde{ab} \cap I'| = h' {\lt} D - 1\). By lemma 21.17, \(I'\) is independent in \(M(\widetilde{G_v^{ab}})\), as the union of \(D\) forests.

Let \(B\) be a base of \(M(\tilde G)\). By lemma 21.21, \(B\) is the union of \(D\) pairwise disjoint forests of \(\tilde G\), each of which has an edge incident with \(v\). By lemma 21.24, \(M(\widetilde{G_v^{ab}})\) has an independent set \(I'\) with \(|I'| = |B| - D\). Hence

The vertices of \(G_v^{ab}\) are the \(|V(G)| - 1\) vertices of \(G\) other than \(v\), among them \(a\). So KT eq. (2.4) (theorem 20.12) applies to \(G_v^{ab}\) and to \(G\), and gives

Katoh and Tanigawa  [ KT11 , p. 661 ] derive their eq. (4.1), \(\operatorname {def}(\widetilde{G_v^{ab}}) \le k\) for a minimal \(k\)-dof-graph \(G\), from their Lemma 4.1 in the same way.

This is lemma 21.25.

We reverse the argument of lemma 21.23. Two copies of \(ab\) form a cycle, so \(r\) is the only copy of \(ab\) in \(F'\). Hence the edges of \(F_0 = F' \setminus \{ r\} \) are edges of \(\widetilde{G_v}\). They have the same ends in \(\tilde G\) as in \(\widetilde{G_v^{ab}}\), and none of them is incident with \(v\). Let \(C\) be a cycle of \(\tilde G\) in \(F_0 \cup \{ p_a, p_b\} \). If \(C\) does not pass through \(v\), then \(C\) lies in \(F_0\), and it is a cycle of \(\widetilde{G_v^{ab}}\) in \(F'\). Otherwise \(C\) uses both \(p_a\) and \(p_b\), the only edges of the set at \(v\). Then the rest of \(C\) is a path from \(b\) to \(a\) in \(F_0\), and with \(r\) it forms a cycle of \(\widetilde{G_v^{ab}}\) in \(F'\). Both cases are impossible, as \(F'\) is a forest.

As \(F\) contains no copy of \(ab\), its edges are edges of \(\widetilde{G_v}\). As in the proof of lemma 21.22, they have the same ends in \(\tilde G\) as in \(\widetilde{G_v^{ab}}\). So \(F\) is a forest of \(\tilde G\), and none of its edges is incident with \(v\). By lemma 21.19, \(F \cup \{ x\} \) is a forest of \(\tilde G\).

We follow Katoh and Tanigawa’s proof. By lemma 21.17, \(I'\) is the union of \(D\) forests of \(\widetilde{G_v^{ab}}\), which we make pairwise disjoint as after that lemma. Two copies of \(ab\) form a cycle, so exactly \(h'\) of the forests contain a copy of \(ab\), one each. Renumbering the forests and the copies of \(ab\), we call them \(F'_1, \dots , F'_D\), where \(F'_i\) contains \((ab, i)\) for \(i \le h'\) and no copy of \(ab\) for \(i {\gt} h'\).

For \(i \le h'\), let \(F_i\) be \(F'_i\) with \((ab, i)\) replaced by \((e_a, i)\) and \((e_b, i)\), a forest of \(\tilde G\) by lemma 21.27. In case (i), let \(F_i = F'_i \cup \{ (e_a, i)\} \) for \(h' {\lt} i \le D - 1\), and \(F_D = F'_D \cup \{ (e_b, h' + 1)\} \). These are forests of \(\tilde G\) by lemma 21.28. In case (ii), let \(F_D = F'_D\). It contains no copy of \(ab\), so it is a forest of \(\tilde G\), as in the proof of lemma 21.28.

The added edges are different copies of \(e_a\) and \(e_b\), and they are not edges of \(\widetilde{G_v^{ab}}\). So \(F_1, \dots , F_D\) are pairwise disjoint forests of \(\tilde G\), and their union \(I\) is independent in \(M(\tilde G)\) (lemma 21.17). Deleting the copies of \(e_a\) and \(e_b\) from \(I\) leaves the union of the \(F'_i\) without their copies of \(ab\), which is \(I' \setminus \widetilde{ab}\). In case (i) every forest gains one edge, so \(|I| = |I'| + D\), and the copies of \(e_b\) in \(I\) are \((e_b, 1), \dots , (e_b, h' + 1)\). In case (ii) the forests \(F_1, \dots , F_{D-1}\) gain one edge each and \(F_D\) none, so \(|I| = |I'| + D - 1\).

By lemma 21.17, \(I'\) is the union of \(D\) forests \(F'_1, \dots , F'_D\) of \(\widetilde{G_v^{ab}}\), which we make pairwise disjoint as after that lemma. None of them contains a copy of \(ab\). Let \(F_i = F'_i \cup \{ (e_a, i)\} \) for \(i \le D - 1\), and \(F_D = F'_D \cup \{ (e_b, 1)\} \); the copy \((e_b, 1)\) exists as \(D \ge 2\). These are forests of \(\tilde G\) by lemma 21.28. The added edges are distinct copies of \(e_a\) and \(e_b\), and they are not edges of \(\widetilde{G_v^{ab}}\). So \(F_1, \dots , F_D\) are pairwise disjoint, and their union \(I\) is independent in \(M(\tilde G)\) (lemma 21.17). Each forest gains one edge, so \(|I| = |I'| + D\). The edges of \(I\) outside \(\tilde e_a \cup \tilde e_b\) are those of \(I'\), and \((e_b, 1)\) is the only copy of \(e_b\) in \(I\). This is Katoh and Tanigawa’s construction when no forest contains a copy of \(ab\).

We compare the values \(\operatorname {def}_{\tilde G}(P)\) of partitions (definition 20.3). The vertices of \(G_v^{ab}\) are those of \(G\) other than \(v\). As \(D \ge 1\), the value \(D\, (|P| - 1) - (D - 1)\, d_G(P)\) does not increase when \(d_G(P)\) increases.

For the upper bound, let \(P'\) be a partition of \(V(G) - v\), and let \(P\) be the partition of \(V(G)\) obtained by adding \(v\) to the part of \(P'\) that contains \(a\). Then \(|P| = |P'|\). The edge \(e_a\) joins two vertices of one part of \(P\). The edge \(e_b\) joins different parts of \(P\) exactly when \(a\) and \(b\) lie in different parts of \(P'\), that is, when the new edge \(ab\) of \(G_v^{ab}\) joins different parts of \(P'\). Every other edge has the same ends in \(G\) and in \(G_v^{ab}\). Hence \(d_G(P) = d_{G_v^{ab}}(P')\), and the value of \(P'\) for \(\widetilde{G_v^{ab}}\) is the value of \(P\) for \(\tilde G\), which is at most \(\operatorname {def}(\tilde G)\).

For the lower bound, let \(P\) be a partition of \(V(G)\) of value \(\operatorname {def}(\tilde G)\), and let \(P'\) be the partition of \(V(G) - v\) into the nonempty sets \(X - v\) with \(X \in P\). The edges of \(G_v^{ab}\) are the edges of \(G\) other than \(e_a\) and \(e_b\), with the same ends, and the new edge \(ab\).

Suppose first that \(v\) is not alone in its part of \(P\). Then \(|P'| = |P|\). If \(ab\) joins different parts of \(P'\), then \(v\) lies in a different part from \(a\) or from \(b\), so \(e_a\) or \(e_b\) joins different parts of \(P\). Hence \(d_{G_v^{ab}}(P') \le d_G(P)\), and the value of \(P'\) is at least \(\operatorname {def}(\tilde G)\).

Suppose now that \(\{ v\} \) is a part of \(P\). Then \(|P'| = |P| - 1\), and both \(e_a\) and \(e_b\) join different parts of \(P\), so \(d_{G_v^{ab}}(P') \le d_G(P) - 1\). The value of \(P'\) is then at least

In both cases \(\operatorname {def}(\widetilde{G_v^{ab}}) \ge \operatorname {def}(\tilde G) - 1\).

The graph \(G''\) is \(G_v^{ab}\) with \(e_a\) as its new edge \(ab\), and we argue as for the upper bound of lemma 21.33. Let \(P'\) be a partition of \(V(G) - v\), and let \(P\) be the partition of \(V(G)\) obtained by adding \(v\) to the part of \(a\). Then \(|P| = |P'|\). In \(G\) the edge \(e_a\) joins two vertices of one part of \(P\), and \(e_b\) joins different parts of \(P\) exactly when \(e_a\) joins different parts of \(P'\) in \(G''\). Every other edge has the same ends in \(G\) and in \(G''\). So \(P'\) has the same value for \(\tilde G''\) as \(P\) for \(\tilde G\).

The graphs \(H\) and \(G'\) have the same vertices, and \(H\) has one more edge, \(ab\). Let \(P\) be a partition of \(V(G')\). If \(P\) separates \(a\) and \(b\), then \(d_H(P) = d_{G'}(P) + 1\). So the value of \(P\) for \(\tilde H\) is its value for \(\tilde G'\) minus \(D - 1\), which is at most \(\operatorname {def}(\tilde G') - (D - 1)\). If \(a\) and \(b\) lie in one part of \(P\), then \(d_H(P) = d_{G'}(P)\). So the value of \(P\) for \(\tilde H\) is at most \(\operatorname {def}(\tilde G'; a, b)\), which the hypothesis bounds.

We compare the values of partitions, as for the lower bound of lemma 21.33. Let \(P\) be a partition of \(V(G)\) of value \(\operatorname {def}(\tilde G)\), and let \(P'\) be the partition of \(V(G) - v\) into the nonempty sets \(X - v\) with \(X \in P\). The edges of \(G_v\) are the edges of \(G\) other than \(e_a\) and \(e_b\), the only edges at \(v\), with the same ends. So

where \(c \in \{ 0, 1, 2\} \) is the number of the edges \(e_a\) and \(e_b\) that join different parts of \(P\).

Suppose first that \(v\) is not alone in its part of \(P\). Then \(|P'| = |P|\), and the value of \(P'\) for \(\widetilde{G_v}\) is \(\operatorname {def}(\tilde G) + (D - 1)\, c \ge \operatorname {def}(\tilde G)\).

Suppose now that \(\{ v\} \) is a part of \(P\). Then \(|P'| = |P| - 1\). The neighbours \(a\) and \(b\) of \(v\) lie in other parts, so both \(e_a\) and \(e_b\) join different parts of \(P\), and \(c = 2\). The value of \(P'\) is

which is at least \(\operatorname {def}(\tilde G)\) as \(D \ge 2\). In both cases \(\operatorname {def}(\widetilde{G_v}) \ge \operatorname {def}(\tilde G)\).

Combine lemma 21.33, which holds as \(D \ge 1\), with lemma 21.38.

The vertices of \(G_v^{ab}\) are the \(|V(G)| - 1\) vertices of \(G\) other than \(v\). So KT eq. (2.4) (theorem 20.12) gives

Suppose that \(G_v^{ab}\) is a \(k\)-dof-graph, and let \(B\) be a base of \(M(\tilde G)\). By lemma 21.21, \(B\) is the union of \(D\) pairwise disjoint forests of \(\tilde G\), each of which has an edge incident with \(v\). The surgery on these forests (lemma 21.24) gives an independent set \(I'\) of \(M(\widetilde{G_v^{ab}})\) with \(|I'| = |B| - D\) and \(|\widetilde{ab} \cap I'| {\lt} D - 1\). Then \(|I'| = D(|V(G)| - 2) - k\), which is the rank of \(M(\widetilde{G_v^{ab}})\), so \(I'\) is a base. This is Katoh and Tanigawa’s argument  [ KT11 , p. 661 ] , with the balanced partition that they assume (remark 21.15).

Conversely, let \(B'\) be a base of \(M(\widetilde{G_v^{ab}})\) with \(|\widetilde{ab} \cap B'| {\lt} D - 1\). By case (i) of KT Lemma 4.2 (lemma 21.29), \(M(\tilde G)\) has an independent set \(I\) with \(|I| = |B'| + D\). As \(|I| \le \operatorname {rank} M(\tilde G)\), we get \(|B'| \le D(|V(G)| - 2) - k\), that is, \(\operatorname {def}(\widetilde{G_v^{ab}}) \ge k\). The upper bound of KT Lemma 4.3(i) (lemma 21.33) gives \(\operatorname {def}(\widetilde{G_v^{ab}}) \le k\).

We follow Katoh and Tanigawa’s proof  [ KT11 , p. 663 ] , which they give for \(k = 0\). If \(G\) has no edge, then the partition of \(V(G)\) into single vertices has the largest value, so \(k = D(|V(G)| - 1)\), and the bound reads \(0 {\lt} D - 1\). Otherwise, fix an edge \(e\) of \(G\). Let \(h^*\) be the least value of \(|\tilde e \cap B|\) over the bases \(B\) of \(M(\tilde G)\), and let \(B^*\) be a base with \(|\tilde e \cap B^*| = h^*\). As \(G\) is minimal, \(h^* \ge 1\). By KT eq. (2.4) (theorem 20.12), every base of \(M(\tilde G)\) has \(D(|V(G)| - 1) - k\) elements.

We show that every edge of \(\tilde G\) outside \(\tilde e\) lies in \(B^*\) (KT eq. (4.3)). Suppose that an edge \(f \notin \tilde e\) of \(\tilde G\) is not in \(B^*\), and let \(X\) be the fundamental circuit of \(f\) with respect to \(B^*\), the only circuit contained in \(B^* + f\). Then \(V(X) = V(G)\), as \(G\) has no loops and no proper rigid subgraph. Suppose first that \(X\) does not meet \(\tilde e\), and let \(x \in X\). By lemma 21.2, \(X - x\) is an independent set with \(D(|V(G)| - 1)\) elements. It lies in a base, which has \(D(|V(G)| - 1) - k\) elements, so \(k \le 0\). As \(V(G)\) is not empty, \(k \ge 0\). So \(k = 0\), and \(X - x\) is a base of \(M(\tilde G)\) that does not meet \(\tilde e\), against the minimality of \(G\). Hence \(X\) contains a copy \(e_j \in \tilde e\). Then \(B^* + f - e_j\) is a base of \(M(\tilde G)\) that meets \(\tilde e\) in \(h^* - 1\) elements, against the choice of \(B^*\).

So the edges of \(\tilde G\) outside \(B^*\) are the \(D - 1 - h^*\) copies of \(e\) outside \(B^*\). As \(\tilde G\) has \((D-1)\, |E(G)|\) edges,

Suppose that \(E(\tilde G)\) contains a circuit \(X\) of \(M(\tilde G)\). As \(G\) has no loops and no proper rigid subgraph, \(V(X) = V(G)\). So \(H = G[V(X)]\) is a rigid subgraph of \(G\) with the vertices of \(G\) (lemma 21.2). By lemma 21.4, \(\operatorname {rank} M(\tilde H) = D(|V(G)| - 1)\), and \(M(\tilde H)\) is a restriction of \(M(\tilde G)\) (lemma 20.24). So \(\operatorname {rank} M(\tilde G) \ge D(|V(G)| - 1)\), and KT eq. (2.4) (theorem 20.12) gives \(k = \operatorname {def}(\tilde G) \le 0\), a contradiction. Hence \(E(\tilde G)\) is independent. A base of \(M(\tilde G)\) is a maximal independent subset of \(E(\tilde G)\), so it is \(E(\tilde G)\).

We argue as Katoh and Tanigawa do (remark 21.39). Let \(B'\) be a base of \(M(\widetilde{G_v})\). As \(G_v\) is a subgraph of \(G_v^{ab}\), the set \(B'\) is independent in \(M(\widetilde{G_v^{ab}})\) (lemma 20.24), and it contains no copy of \(ab\). By case (i) of KT Lemma 4.2 with \(h' = 0\) (lemma 21.29), \(M(\tilde G)\) has an independent set \(I\) with \(|I| = |B'| + D\) and \(|\tilde e_b \cap I| = 1\). The vertices of \(G_v\) are the \(|V(G)| - 1\) vertices of \(G\) other than \(v\). So KT eq. (2.4) (theorem 20.12), for \(G_v\) and for \(G\), gives

and \(I\) is a base.

KT Lemma 4.4 (lemma 21.38) gives \(\operatorname {def}(\widetilde{G_v}) \ge k\), and we show that equality fails. Suppose that \(\operatorname {def}(\widetilde{G_v}) = k\). If \(k = 0\), then \(G_v\) is a rigid subgraph of \(G\) whose vertices, those of \(G\) other than \(v\), include \(a\) and \(b\): at least two, and not all of those of \(G\). This is impossible. If \(k {\gt} 0\), then by lemma 21.45 some base \(B\) of \(M(\tilde G)\) has \(|\tilde e_b \cap B| = 1\). But \(B = E(\tilde G)\) (lemma 21.44), which contains all \(D - 1 \ge 2\) copies of \(e_b\). This is Katoh and Tanigawa’s proof  [ KT11 , p. 665 ] .

As \(V(G)\) is not empty, \(k \ge 0\), so lemma 21.43 gives

The degrees of the vertices of \(G\) sum to \(2|E(G)|\), so their average is less than \(2D/(D-1) = 2 + 2/(D-1)\), which is at most \(3\) as \(D \ge 3\). Hence some vertex has degree at most two. This is KT eq. (4.5)  [ KT11 , p. 664 ] .

By lemma 21.49, \(G\) has a vertex of degree at most two. As \(G\) is \(2\)-edge-connected and has at least two vertices, every vertex of \(G\) has degree at least two (lemma 20.21).

The vertices of \(G_v^{ab}\) are those of \(G\) other than \(v\) (definition 21.10). The vertices of \(G/E(H)\) are the chosen vertex of \(H\) and the vertices of \(G\) not in \(H\) (definition 21.3), which gives the count.

Part (ii) is the case \(k = 0\) of lemma 21.8.

For (i) we follow Katoh and Tanigawa’s proof  [ KT11 , pp. 665–666 ] up to its last step. Let \(G' = G_v^{ab}\), and let \(G_v = G - v\). Both have the \(|V(G)| - 1\) vertices of \(G\) other than \(v\), and the edges of \(\widetilde{G'}\) are those of \(\widetilde{G_v}\) and the \(D - 1\) copies of \(ab\). By the upper bound of lemma 21.33, \(\operatorname {def}(\widetilde{G'}) \le \operatorname {def}(\tilde G) = 0\), and \(\operatorname {def}(\widetilde{G'}) \ge 0\) as \(G'\) has a vertex. So \(G'\) is a \(0\)-dof-graph. The subgraph \(G_v\) of \(G\) has \(|V(G)| - 1 \ge 2\) vertices, but not all of those of \(G\). As \(G\) has no proper rigid subgraph, \(G_v\) is not rigid, and so \(\operatorname {def}(\widetilde{G_v}) {\gt} 0\). This is the case \(k = 0\) of KT Lemma 4.7.

Every circuit \(X\) of \(M(\widetilde{G'})\) meets \(\widetilde{ab}\) (KT eq. (4.10)). Otherwise \(X\) is a set of edges of \(\widetilde{G_v}\). As \(G_v\) is a subgraph of both \(G'\) and \(G\), \(X\) is then a circuit of \(M(\widetilde{G_v})\) and of \(M(\tilde G)\) (lemma 20.24). As \(G\) has no loops, \(|V(X)| \ge 2\), and no edge of \(X\) is incident with \(v\). So \(G[V(X)]\) is a proper rigid subgraph of \(G\) (lemma 21.2), which is impossible. Hence \(E(\widetilde{G_v})\) contains no circuit of \(M(\widetilde{G'})\), and it is independent in \(M(\widetilde{G'})\) and in its restriction \(M(\widetilde{G_v})\), whose ground set it is. Thus \(E(\widetilde{G_v})\) is the only base of \(M(\widetilde{G_v})\), and KT eq. (2.4) (theorem 20.12) gives

Now let \(B'\) be a base of \(M(\widetilde{G'})\), and let \(e\) be an edge of \(G'\). By KT eq. (2.4), \(|B'| = D(|V(G)| - 2)\). Suppose that \(B'\) does not meet \(\tilde e\). If \(e\) is the new edge \(ab\), then \(B'\) is a set of edges of \(\widetilde{G_v}\). Otherwise \(e\) is an edge of \(G_v\), and \(B'\) consists of at most \(D - 1\) copies of \(ab\) and of edges of \(\widetilde{G_v}\) outside \(\tilde e\), of which there are \(|E(\widetilde{G_v})| - (D - 1)\). In both cases \(|B'| \le |E(\widetilde{G_v})| {\lt} D(|V(G)| - 2)\), a contradiction. So every base of \(M(\widetilde{G'})\) meets \(\tilde e\) for every edge \(e\) of \(G'\), and \(G'\) is minimal.

Katoh and Tanigawa end differently. They start from a base of \(M(\widetilde{G'})\) that misses \(\tilde e\) for an edge \(e \neq ab\), and use KT eq. (4.10) to exchange its copies of \(ab\), one at a time, for copies of \(e\). This gives a base of \(M(\widetilde{G'})\) with no copy of \(ab\), which is a base of \(M(\widetilde{G_v})\) with \(D(|V(G)| - 2)\) elements, against KT Lemma 4.7. We replace this exchange by the count above.

Let \(G' = G_v^{ab}\). Its vertices are the \(|V(G)| - 1\) vertices of \(G\) other than \(v\), and by lemma 21.40, \(\operatorname {def}(\widetilde{G'})\) is \(k - 1\) or \(k\).

We show, as Katoh and Tanigawa do  [ KT11 , p. 666 ] , that \(\operatorname {def}(\widetilde{G'}) \neq k\). Suppose that \(\operatorname {def}(\widetilde{G'}) = k\). By KT Lemma 4.3(ii) (lemma 21.41), \(M(\widetilde{G'})\) has a base \(B'\) that misses a copy \(p\) of \(ab\). Let \(X\) be the fundamental circuit of \(p\) with respect to \(B'\), and let \(H = G'[V(X)]\), a rigid subgraph of \(G'\) (lemma 21.2). If \(V(H) = V(G')\), then \(\operatorname {rank} M(\widetilde{G'}) \ge \operatorname {rank} M(\tilde H) = D(|V(G')| - 1)\) (lemma 21.4), and KT eq. (2.4) gives \(\operatorname {def}(\widetilde{G'}) \le 0 {\lt} k\). So \(V(H)\) is a proper subset of \(V(G')\). It contains the ends \(a\) and \(b\) of \(p\).

Let \(K = G[V(H) \cup \{ v\} ]\). Then \(v\) has degree two in \(K\), and \(K_v^{ab} = H\). The set \(I = X - p\) is independent in \(M(\tilde H)\), with \(|I| = D(|V(H)| - 1)\) (lemma 21.2). As \(I \subseteq B'\) and \(p \notin B'\), also \(|\widetilde{ab} \cap I| {\lt} D - 1\). By case (i) of KT Lemma 4.2 (lemma 21.29) for \(K\), \(M(\tilde K)\) has an independent set with \(|I| + D = D(|V(K)| - 1)\) elements. So \(\operatorname {def}(\tilde K) = 0\) by KT eq. (2.4), and \(K\) is a rigid subgraph of \(G\). Its vertex set \(V(H) \cup \{ v\} \) has at least two elements, and it is a proper subset of \(V(G)\). This contradicts the hypothesis, and so \(\operatorname {def}(\widetilde{G'}) = k - 1\).

It remains to show that \(G'\) is minimal: every base \(B'\) of \(M(\widetilde{G'})\) meets \(\tilde e\) for every edge \(e\) of \(G'\). This is the minimality clause of KT Lemma 4.3(i), and we follow Katoh and Tanigawa’s proof of it  [ KT11 , p. 661 ] . As \(G'\) is not a \(k\)-dof-graph, \(B'\) contains all \(D - 1\) copies of \(ab\) (lemma 21.41), and so it meets \(\widetilde{ab}\). Suppose that \(B'\) misses \(\tilde e\). Then \(e \neq ab\), and \(e\) is an edge of \(G\) other than \(e_a\) and \(e_b\). By KT eq. (2.4), \(|B'| = D(|V(G)| - 2) - (k - 1)\). By case (ii) of KT Lemma 4.2 (lemma 21.29), \(M(\tilde G)\) has an independent set \(J\) with \(|J| = |B'| + D - 1 = D(|V(G)| - 1) - k\) and \(J \setminus (\tilde e_a \cup \tilde e_b) = B' \setminus \widetilde{ab}\). By KT eq. (2.4), \(J\) is a base of \(M(\tilde G)\), and it does not meet \(\tilde e\), against the minimality of \(G\).

We prove (ii) by induction on \(|V(G)|\). If \(G\) has two vertices, then \(P(G)\) holds by (a). Let \(G\) have at least three vertices, and suppose that \(P\) holds for every minimal \(0\)-dof-graph with at least two and fewer than \(|V(G)|\) vertices. If \(G\) has a proper rigid subgraph, then \(P(G)\) holds by (c).

Otherwise, \(G\) is \(2\)-edge-connected, as it is a \(0\)-dof-graph (lemma 20.21). So \(G\) has a vertex \(v\) of degree two (lemma 21.50). As we showed before lemma 21.43, \(G\) has no loops. So the two edges at \(v\) join it to vertices \(a, b \neq v\). By part (i) of lemma 21.52, \(G_v^{ab}\) is a minimal \(0\)-dof-graph. Its vertices are the \(|V(G)| - 1 \ge 2\) vertices of \(G\) other than \(v\) (lemma 21.51). So \(P(G_v^{ab})\) holds by the induction hypothesis, and \(P(G)\) holds by (b).

Part (i) is Katoh and Tanigawa’s statement. As in their proof, it follows from (ii), with \(P(G)\) the existence of such a sequence for \(G\). A minimal \(0\)-dof-graph with two vertices has two edges, each joining them (lemma 20.39), which gives (a). A sequence for \(G_v^{ab}\) extends to one for \(G\), which gives (b).

For (c), let \(H\) be a proper rigid subgraph of \(G\), and let \(G/E(H)\) be its contraction to a vertex of \(H\). It has \(|V(G)| - |V(H)| + 1\) vertices, at least two and fewer than \(|V(G)|\) (lemma 21.51). By KT Lemma 3.5, \(G/E(H)\) is a minimal \(0\)-dof-graph. We prove this lemma for the matroid \(M(\tilde G)/E(\tilde H)\) (lemma 21.8), and for the graph \(G/E(H)\) (lemma 21.9). So \(G/E(H)\) has a sequence, which extends to one for \(G\).

We argue by induction on \(|V(G)|\), for all \(k\) at once. Let \(G\) be a minimal \(k\)-dof-graph with at least one vertex, and suppose that \(P\) holds for every minimal \(k'\)-dof-graph with at least one and fewer than \(|V(G)|\) vertices. If \(G\) has one or two vertices, then \(P(G)\) holds by hypothesis. Otherwise one of the four cases applies. Indeed, if \(G\) is \(2\)-edge-connected and has no proper rigid subgraph, then \(k \ge 0\), as the partition of \(V(G)\) into one part has value \(0\) (definition 20.3). In each case \(P(G)\) holds by hypothesis.

As we showed before lemma 21.43, \(G\) has no loops. Suppose that two edges \(e \neq f\) join vertices \(x\) and \(y\), so that \(x \neq y\). The subgraph \(H\) of \(G\) with the vertices \(x\), \(y\) and the edges \(e\), \(f\) is a \(0\)-dof-graph (lemma 20.36), and \(1 {\lt} |V(H)| = 2 {\lt} |V(G)|\). So \(H\) is a proper rigid subgraph of \(G\) (definition 20.17), which is impossible.

We follow Katoh and Tanigawa’s proof  [ KT11 , p. 677 ] . A triangle with vertices \(x\), \(y\), \(z\) and edges joining \(x\) and \(y\), \(y\) and \(z\), \(z\) and \(x\) is a cycle on three vertices. As \(3 \le D\), it is a \(0\)-dof-graph (lemma 20.37).

As \(G\) is simple, \(e_a\) and \(e_b\) do not join \(v\) to the same vertex, so \(a \neq b\). Let \(f\) be an edge of \(G\) that joins \(a\) and \(b\). The subgraph of \(G\) induced on \(\{ v, a, b\} \) has no edge other than \(e_a\), \(e_b\) and \(f\), as \(G\) is simple, so it is a triangle, and a \(0\)-dof-graph. As \(1 {\lt} 3 {\lt} 4 \le |V(G)|\), it is a proper rigid subgraph of \(G\).

Now let \(G\) have no proper rigid subgraph. Then no edge of \(G\) joins \(a\) and \(b\). The new edge \(ab\) of \(G_v^{ab}\) is not a loop, as \(a \neq b\), and its other edges are edges of the simple graph \(G\) with the same ends (definition 21.10). None of them joins \(a\) and \(b\), so none is parallel to \(ab\), and \(G_v^{ab}\) is simple.

Suppose not. As we showed before lemma 21.43, \(G\) has no loops. As \(G\) is a \(0\)-dof-graph with at least two vertices, every vertex of \(G\) has degree at least two (lemma 20.23). Let \(X_2\) be the set of vertices of degree two, and let \(X_3\) be the set of the other vertices, which have degree at least three. No edge joins two vertices of \(X_2\), so every edge at a vertex of \(X_2\) has its other end in \(X_3\). Hence

The degrees of the vertices of \(G\) sum to \(2|E(G)|\). So \(2|E(G)| \ge 2\sum _{v \in X_2} \deg v = 4|X_2|\), and \(2|E(G)| \ge 2|X_2| + 3|X_3|\). Adding the first inequality to four times the second gives \(10|E(G)| \ge 12(|X_2| + |X_3|)\), that is, \(5|E(G)| \ge 6|V(G)|\).

On the other hand, KT Lemma 4.5(i) (lemma 21.43) at \(k = 0\) gives \((D-1)\, |E(G)| {\lt} D\, |V(G)| - 1\). So

as \(D \ge 6\). This is a contradiction. Katoh and Tanigawa prove their Lemma 4.6 with maximal chains  [ KT11 , pp. 664–665 ] ; for two adjacent vertices of degree two, the count above suffices.

By lemma 21.60, \(G\) has adjacent vertices \(v\) and \(a\) of degree two. Let \(e_a\) be an edge that joins them. By lemma 21.57, \(G\) is simple. So the other edge \(e_b\) at \(v\) joins \(v\) to a vertex \(b \notin \{ v, a\} \), and the other edge \(e_c\) at \(a\) joins \(a\) to a vertex \(c \notin \{ v, a\} \).

Suppose that \(b = c\). Then the subgraph \(T\) of \(G\) with the vertices \(v\), \(a\), \(b\) and the edges \(e_a\), \(e_b\), \(e_c\) is a triangle. It is a \(0\)-dof-graph. Indeed, two edges of \(T\) join the parts of a partition of \(V(T)\) into two parts, of value \(D - 2(D-1) \le 0\), and three join those of the partition into three parts, of value \(2D - 3(D-1) \le 0\) (definition 20.3). As \(1 {\lt} |V(T)| = 3 {\lt} |V(G)|\), \(T\) is a proper rigid subgraph of \(G\) (definition 20.17), which is impossible. Hence \(b \neq c\).

We follow Katoh and Tanigawa’s proof  [ KT11 , pp. 664–665 ] , and give its count in full. As \(D \ge 3\), we have \(d \ge 2\), and \(d \le D\). By KT Lemma 3.1 (lemma 20.18), \(G\) is \(2\)-edge-connected. So it is connected, and each of its vertices has degree at least two (lemma 20.23). By lemma 21.57, \(G\) is simple.

Let \(u_0\) be a vertex of \(G\), and let \(g_1\) be an edge at \(u_0\), joining it to \(u_1\). We extend the path \(u_0 u_1\) one edge at a time. While its last vertex \(u_j\) has degree two and \(j {\lt} d\), let \(g_{j+1}\) be the edge at \(u_j\) other than \(g_j\), and let \(u_{j+1}\) be its other end. The vertices \(u_1, \dots , u_{j-1}\) have degree two and both of their edges are on the path, so \(u_{j+1}\) is not one of them. As \(G\) is simple, \(u_{j+1} \neq u_j\), and \(u_2 \neq u_0\). So \(u_{j+1}\) is a new vertex, or \(u_{j+1} = u_0\) with \(j \ge 2\). We call the path so obtained the walk from \(u_0\) along \(g_1\). It ends in one of three ways.

If the walk reaches length \(d\), then \(u_0 u_1 \dots u_d\) is a chain of length \(d\) (definition 21.62).

If the walk closes up, with \(u_{j+1} = u_0\), then \(u_0, \dots , u_j\) and \(g_1, \dots , g_{j+1}\) form a cycle \(C\) on \(m = j + 1\) vertices, where \(3 \le m \le d\). If \(u_0\) has degree two, then no edge of \(G\) leaves \(C\). As \(G\) is connected, \(G = C\) is a cycle on at most \(d\) vertices (definition 21.64). If \(u_0\) has degree at least three, then \(C\) is a \(0\)-dof-graph, as \(m \le d \le D\) (lemma 20.37). A third edge at \(u_0\) has its other end outside \(C\), since the other vertices of \(C\) have degree two. So \(C\) is a proper rigid subgraph of \(G\) (definition 20.17), which is impossible. Katoh and Tanigawa’s maximal chains may begin and end at the same vertex. A closed one of length \(d\) has only \(d\) distinct vertices, and this case excludes it.

Otherwise the walk stops at a vertex \(u_j\) of degree at least three, with \(1 \le j \le d - 1\).

Suppose now that \(G\) is not a cycle on at most \(d\) vertices and has no chain of length \(d\). Then every walk stops at a vertex of degree at least three, after at most \(d - 1\) edges. So a walk that starts at a vertex of degree at least three has at most \(d - 2\) interior vertices, all of degree two. For \(i \ge 2\), let \(X_i\) be the set of vertices of \(G\) of degree \(i\). Let \(v \in X_2\), and let \(e\) be an edge at \(v\). The walk from \(v\) along \(e\) stops at a vertex \(u\) of degree at least three. Read backwards, it is a path that leaves \(u\) along an edge \(g\) and passes through vertices of degree two up to \(v\). At a vertex of degree two, a walk leaves by the edge by which it did not arrive. So this path is the beginning of the walk from \(u\) along \(g\), and \(v\), of degree two, is an interior vertex of that walk. The pair \((u, g)\) and the position of \(v\) on its walk determine \(v\). They also determine \(e\), as the edge by which that walk arrives at \(v\). There are \(\sum _{i \ge 3} i\, |X_i|\) pairs \((u, g)\) with \(u\) of degree at least three, and so

Katoh and Tanigawa obtain this inequality from their eqs. (4.6) and (4.7), by counting maximal chains.

As every vertex of \(G\) has degree at least two, \(|V(G)| = \sum _{i \ge 2} |X_i|\). Adding \(2|X_i|\) for each \(i \ge 3\) to both sides of the inequality gives KT eq. (4.8),

For \(i \ge 3\) we have \(i(d-2) + 2 \le (D-1)(i-2)\), the inequality before KT eq. (4.9). Indeed, at \(i = 3\) twice the right side minus twice the left side is \((d-2)(d-3) \ge 0\), as \(D = d(d+1)/2\). Each step from \(i\) to \(i + 1\) adds \(d - 2\) to the left side and \(D - 1 \ge d - 2\) to the right side. The degrees of \(G\) sum to \(2|E(G)|\), so \(\sum _{i \ge 3} (i-2)|X_i| = 2|E(G)| - 2|V(G)|\), and KT eq. (4.9) reads

Hence \(D\, |V(G)| \le (D-1)\, |E(G)|\). But KT Lemma 4.5(i) (lemma 21.43, at \(k = 0\)) gives \((D-1)\, |E(G)| {\lt} D(|V(G)| - 1) + D - 1 {\lt} D\, |V(G)|\), a contradiction.

By lemma 21.66, \(G\) is a cycle on at most \(d\) vertices, or it has a chain \(v_0 v_1 \dots v_d\) of length \(d\). Suppose the second. As \(D \ge 3\), we have \(d \ge 2\), so \(v_1\) is an interior vertex of the chain. Its only edges are \(f_0\) and \(f_1\), which join it to \(v_0\) and to \(v_2\), and \(v_0, v_1, v_2\) are distinct. As \(G\) has at least three vertices and no proper rigid subgraph, \(G_{v_1}^{v_0 v_2}\) is a minimal \(0\)-dof-graph by KT Lemma 4.8(i) (part (i) of lemma 21.52). Its vertices are the \(|V(G)| - 1 \ge 3\) vertices of \(G\) other than \(v_1\) (lemma 21.51).

It remains to show that \(G_{v_1}^{v_0 v_2}\) is simple. The graph \(G\) is simple by lemma 21.57, as it has at least three vertices and no proper rigid subgraph, and it has at least four vertices. So KT Lemma 6.7(ii) (lemma 21.58), applied to \(v_1\) and its edges \(f_0 \neq f_1\), shows that \(G_{v_1}^{v_0 v_2}\) is simple.