20 The matroid \(M(\tilde G)\), deficiency, and \(k\)-dof graphs
This chapter develops the combinatorics of Katoh and Tanigawa’s proof [ KT11 , § 2.5 and § 3 ] . Throughout, \(G\) is a multigraph, \(D = \binom {d+1}{2}\), and \(\tilde G = (D-1)\cdot G\) is the multigraph of section 17, in which each edge of \(G\) is repeated \(D - 1\) times. We study two numbers attached to \(\tilde G\): the rank of a matroid \(M(\tilde G)\) on its edges, the union of \(D\) copies of its cycle matroid, and the deficiency \(\operatorname {def}(\tilde G)\), a maximum over the partitions of \(V(G)\). Katoh and Tanigawa’s Proposition 2.3, which they credit to Jackson and Jordán [ JJ10 ] , relates both to the rank of the rigidity matrix \(R(G,p)\) of a generic body-hinge framework \((G,p)\) (section 19):
This chapter proves the second equality, KT eq. (2.4), and the inequality \(\le \) in the first at every realization. The first is the rank formula of Jackson and Jordán. We prove it in a conditional form, from a bound on the space of motions, in the chapter on the algebraic induction (proposition 23.19), and at every generic hinge-point assignment of a multigraph in a later chapter (theorem 28.40, proposition 28.42).
Section 20.1 defines \(M(\tilde G)\), the deficiency, and the \(k\)-dof-graphs, the multigraphs with \(\operatorname {def}(\tilde G) = k\). Section 20.2 proves KT eq. (2.4) from the rank of a matroid union (section 15), and characterizes deficiency zero by \(D\) edge-disjoint spanning trees (KT Proposition 2.2). Section 20.3 bounds the rank of \(R(G,p)\) by the deficiency. Section 20.4 proves Katoh and Tanigawa’s lemmas on \(k\)-dof-graphs from their §3, and computes the deficiency at cuts, cut vertices and ears. The combinatorial induction of the next chapter (section 21) uses these results.
20.1 The matroid \(M(\tilde G)\), the deficiency and \(k\)-dof-graphs
This subsection follows Katoh and Tanigawa [ KT11 , § 2.5 and the start of § 3 ] . We define a matroid \(M(\tilde G)\) on the edges of \(\tilde G\), the deficiency \(\operatorname {def}(\tilde G)\), a maximum over the partitions of \(V(G)\), and the partitions that attain it. Every base \(B\) of \(M(\tilde G)\) has \(|B| + \operatorname {def}(\tilde G) = D(|V(G)| - 1)\) (KT eq. (2.4)), which we prove in section 20.2. Then we define the \(k\)-dof-graphs, the multigraphs \(G\) with \(\operatorname {def}(\tilde G) = k\), and the minimal ones.
We use the notation of section 16.1: \(V(F)\) is the set of vertices incident with an edge of a set \(F\) of edges, and \(\tilde G \restriction F\) is the multigraph with the vertices of \(\tilde G\) and the edges of \(F\). Katoh and Tanigawa define \(M(\tilde G)\) as the matroid on \(E(\tilde G)\) induced by the submodular function \(F \mapsto D(|V(F)| - 1)\) (definition 15.3). A set \(F\) is independent in it if and only if \(\tilde G \restriction F\) is \((D, D)\)-sparse (definition 16.1). They remark that this matroid is the union of \(D\) copies of the cycle matroid [ KT11 , p. 655 ] , and we take the union as the definition.
Let \(G\) be a multigraph. The matroid \(M(\tilde G)\) is the union of \(D\) copies of the cycle matroid of \(\tilde G\) (definition 15.6). A set \(F\) of edges of \(\tilde G\) is independent in \(M(\tilde G)\) if and only if \(\tilde G \restriction F\) is \((D, D)\)-sparse.
Apply theorem 16.2 to the multigraph \(\tilde G\), with \(k = D\).
As for the \(k\)-frame matroid (formalization note 16.17), the formal union is a matroid on all pairs \((e, i)\) of an edge label \(e\) and an index \(1 \le i \le D - 1\), in which a pair outside \(E(\tilde G)\) is a loop. The matroid \(M(\tilde G)\) is its restriction to \(E(\tilde G)\).
So \(M(\tilde G)\) is Katoh and Tanigawa’s matroid. By lemma 15.8, its independent sets are the unions of \(D\) forests of \(\tilde G\). They are also the sets \(F\) such that the multigraph \(\tilde G \restriction F\) has an independent body-bar framework in \({\mathbb {R}}^d\), by Tay’s theorem (theorem 16.27).
Let \(G\) be a multigraph. For a partition \(P\) of \(V(G)\) into nonempty parts, let \(d_G(P)\) be the number of edges of \(G\) that join different parts of \(P\). The \(D\)-deficiency of \(P\) is
and the deficiency \(\operatorname {def}(\tilde G)\) is the largest value of \(\operatorname {def}_{\tilde G}(P)\) over the partitions \(P\) of \(V(G)\).
In the formalization a partition of \(V(G)\) is given by a labeling of the vertices whose labels are again vertices. Its parts are the sets of vertices of \(G\) with a common label. So \(|P|\) is the number of labels used on \(V(G)\), and an edge joins different parts when its ends have different labels. The values of the labelings are integers, and the deficiency is their supremum, which is attained because there are finitely many labelings.
Katoh and Tanigawa [ KT11 , p. 655 ] write \(\operatorname {def}_{\tilde G}(P) = D(|P| - 1) - d_{\tilde G}(P)\), where \(d_{\tilde G}(P) = (D-1)\, d_G(P)\) is the number of edges of \(\tilde G\) that join different parts of \(P\). If \(V(G)\) is nonempty, then the partition \(\{ V(G)\} \) has value \(0\), so \(\operatorname {def}(\tilde G) \ge 0\). By the theorem of Tutte and Nash-Williams [ Tut61 , NW61 ] (KT Proposition 2.2), \(\operatorname {def}(\tilde G) = 0\) if and only if \(\tilde G\) contains \(D\) edge-disjoint spanning trees. We prove this for \(D \ge 2\) in lemma 20.14.
Several proofs below start from a partition of \(V(G)\) of largest value.
Let \(G\) be a multigraph. Following Jackson and Jordán [ JJ08a , § 2 ] , a partition \(P\) of \(V(G)\) is tight if it attains the deficiency, that is, if \(\operatorname {def}_{\tilde G}(P) = \operatorname {def}(\tilde G)\).
Let \(G\) be a multigraph whose vertex set is finite and nonempty. Then some partition \(P\) of \(V(G)\) is tight, that is, \(\operatorname {def}_{\tilde G}(P) = \operatorname {def}(\tilde G)\).
A finite set has finitely many partitions, so the maximum that defines \(\operatorname {def}(\tilde G)\) is attained.
The deficiency depends on the dimension \(d\) through \(D = \binom {d+1}{2}\). When \(d\) varies, we write \(\operatorname {def}_d(G)\) for \(\operatorname {def}(\tilde G)\) at this \(D\). So \(\operatorname {def}_2(G)\) and \(\operatorname {def}_3(G)\) are the deficiencies at \(D = 3\) and \(D = 6\), which section 30 compares.
Let \(G\) be a connected multigraph, and let \(d \le d'\) be natural numbers. Then \(\operatorname {def}_{d'}(G) \le \operatorname {def}_d(G)\). In particular \(\operatorname {def}_3(G) \le \operatorname {def}_2(G)\).
Let \(D \le D'\) be the values of \(\binom {d+1}{2}\) and \(\binom {d’+1}{2}\), and let \(P\) be a partition of \(V(G)\). At least \(|P| - 1\) edges of \(G\) join different parts of \(P\). Indeed, once these edges are deleted, each component lies in one part, so there are at least \(|P|\) components. Deleting an edge raises the number of components by at most one, and \(G\) is connected. Hence the value of \(P\) at \(D'\) minus its value at \(D\) is
So the value of \(P\) at \(D'\) is at most \(\operatorname {def}_d(G)\), and the lemma follows.
By Jackson and Jordán’s rank formula (KT Proposition 2.3; proposition 28.42), a generic realization of \(G\) has \(\operatorname {def}(\tilde G)\) degrees of freedom (definition 19.16, corollary 28.41). This is why Katoh and Tanigawa speak of \(k\)-dof-graphs, for \(k\) degrees of freedom [ KT11 , § 3 ] .
Let \(G\) be a multigraph and let \(k\) be an integer. Then \(G\) is a \(k\)-dof-graph if \(\operatorname {def}(\tilde G) = k\). It is a minimal \(k\)-dof-graph if moreover, for every edge \(e\) of \(G\), every base of \(M(\tilde G)\) meets the set \(\tilde e\) of the \(D - 1\) copies of \(e\) in \(\tilde G\).
Katoh and Tanigawa call a \(k\)-dof-graph minimal if removing any edge gives a graph that is not a \(k\)-dof-graph, and observe that this is the condition above [ KT11 , pp. 656–657 ] . Indeed, removing an edge \(e\) of \(G\) leaves the deficiency unchanged if and only if some base of \(M(\tilde G)\) avoids \(\tilde e\). This follows from KT eq. (2.4) (theorem 20.12 below), since \(M(\widetilde{G - e})\) is the restriction of \(M(\tilde G)\) to \(E(\tilde G) \setminus \tilde e\) (lemma 20.24).
20.2 The deficiency and the rank of \(M(\tilde G)\)
This subsection proves KT eq. (2.4). Let \(D \ge 1\), and let \(G\) have at least one vertex. Every base of \(M(\tilde G)\) has \(\operatorname {rank} M(\tilde G)\) elements, so eq. (2.4) says that
We call the right-hand side the corank of \(M(\tilde G)\). Katoh and Tanigawa observe eq. (2.4) from the equivalence of (ii) and (iii) in their Proposition 2.3. They note that the deficiency is the corank \(|E(\tilde G)| - \operatorname {rank} M(\tilde G)\) in the usual sense when \(\tilde G\) has \(D(|V(G)| - 1)\) edges [ KT11 , pp. 655–656 ] .
Since the independent sets of \(M(\tilde G)\) are the unions of \(D\) forests of \(\tilde G\), eq. (2.4) is the classical formula for the largest size of such a union, applied to \(\tilde G\) (see Jackson and Jordán [ JJ10 , Theorem 4.1(a) ] ). We derive it from the rank of a matroid union (theorem 15.10). For a partition \(P\) of \(V(G)\), the edges of \(\tilde G\) inside the parts of \(P\) give \(\operatorname {rank} M(\tilde G) + \operatorname {def}_{\tilde G}(P) \le D(|V(G)| - 1)\) (lemma 20.11). Conversely, let \(Y\) be a set of edges at which the rank formula attains its minimum. Then equality holds at the partition of \(V(G)\) into the vertex sets of the components of \(\tilde G \restriction Y\) (theorem 20.12). We begin with an upper bound on the rank that follows from sparsity alone. Finally we characterize deficiency zero by spanning trees.
Let \(G\) be a multigraph with at least one vertex. Then
Let \(B\) be a base of \(M(\tilde G)\). Then \(\tilde G \restriction B\) is \((D, D)\)-sparse (definition 20.1). If \(B\) is empty, the bound holds as \(|V(G)| \ge 1\). Otherwise sparsity, applied to \(B\) itself, gives \(|B| \le D\, |V(B)| - D \le D\, (|V(G)| - 1)\).
For a set \(Y\) of edges of \(\tilde G\), the multigraph \(\tilde G \restriction Y\) has all the vertices of \(G\), and each vertex outside \(V(Y)\) is a component of its own. So the rank of \(Y\) in the cycle matroid of \(\tilde G\) is \(|V(G)| - c\), where \(c\) is the number of components of \(\tilde G \restriction Y\) (section 16.1).
Let \(G\) be a multigraph, and let \(r\) be the rank function of the cycle matroid of \(\tilde G\). Let \(P\) be a partition of \(V(G)\), and let \(Y\) be a set of edges of \(\tilde G\) such that the ends of each edge of \(Y\) lie in one part of \(P\). Then \(r(Y) + |P| \le |V(G)|\).
The ends of each edge of \(Y\) lie in one part of \(P\), so each component of \(\tilde G \restriction Y\) lies in one part. Each part is nonempty, so it contains a component, and \(\tilde G \restriction Y\) has at least \(|P|\) components. Hence \(r(Y) \le |V(G)| - |P|\).
The proof of lemma 20.11 applies the lemma to the set of all the edges of \(\tilde G\) inside the parts of \(P\), and the formal proof of theorem 20.12 to the set \(Y_0\) of its proof.
Let \(D \ge 1\), and let \(G\) be a multigraph with at least one vertex. Then every partition \(P\) of \(V(G)\) satisfies
In particular, \(\operatorname {rank} M(\tilde G) + \operatorname {def}(\tilde G) \le D\, (|V(G)| - 1)\).
Let \(r\) be as in lemma 20.10, and let \(Y\) be the set of edges of \(\tilde G\) whose ends lie in one part of \(P\). The edges of \(\tilde G\) outside \(Y\) are the \(D - 1\) copies of each of the \(d_G(P)\) edges of \(G\) that join different parts of \(P\). The matroid \(M(\tilde G)\) is the union of \(D\) copies of the cycle matroid of \(\tilde G\) (definition 20.1). So the rank of a matroid union (theorem 15.10) gives the first inequality of
The second holds by lemma 20.10. As \(\operatorname {def}_{\tilde G}(P) = D(|P| - 1) - (D-1)\, d_G(P)\), this is the inequality at \(P\). Taking \(P\) of largest value gives the inequality for \(\operatorname {def}(\tilde G)\).
Let \(D \ge 1\), and let \(G\) be a multigraph with at least one vertex. Then every base \(B\) of \(M(\tilde G)\) satisfies
That is, \(\operatorname {rank} M(\tilde G) + \operatorname {def}(\tilde G) = D\, (|V(G)| - 1)\).
By lemma 20.11, \(\operatorname {rank} M(\tilde G) + \operatorname {def}(\tilde G) \le D\, (|V(G)| - 1)\). For the reverse inequality we find a partition \(P\) of \(V(G)\) with \(\operatorname {rank} M(\tilde G) + \operatorname {def}_{\tilde G}(P) \ge D\, (|V(G)| - 1)\).
Let \(r\) be the rank function of the cycle matroid of \(\tilde G\). By the rank of a matroid union (theorem 15.10), applied to the \(D\) copies of this matroid, some set \(Y_0\) of edges of \(\tilde G\) satisfies
Let \(P\) be the partition of \(V(G)\) into the vertex sets of the components of \(\tilde G \restriction Y_0\). Then \(r(Y_0) = |V(G)| - |P|\), as before lemma 20.10. The ends of an edge of \(Y_0\) lie in one component of \(\tilde G \restriction Y_0\), so in one part of \(P\). Hence the \(D - 1\) copies of each of the \(d_G(P)\) edges of \(G\) that join different parts of \(P\) lie in \(E(\tilde G) \setminus Y_0\), and
As \(\operatorname {def}_{\tilde G}(P) \le \operatorname {def}(\tilde G)\), the reverse inequality follows. Every base \(B\) of \(M(\tilde G)\) has \(|B| = \operatorname {rank} M(\tilde G)\).
The first pin is the identity for the rank, the second the identity for a base, and the third the reverse inequality. In the third, the partition into components is the labeling that sends each vertex to a chosen vertex of its component (formalization note 20.4). By lemma 20.10, applied to \(Y_0\), this labeling has at most as many parts as there are components. It has at least as many, as different components get different labels.
The characterization of deficiency zero announced in section 20.1 follows from KT eq. (2.4).
Let \(D \ge 2\), and let \(G\) be a multigraph with at least one vertex. Then \(\operatorname {def}(\tilde G) = 0\) if and only if \(\tilde G\) contains \(D\) edge-disjoint spanning trees.
Suppose that \(\tilde G\) contains \(D\) edge-disjoint spanning trees. Each has \(|V(G)| - 1\) edges, so their union \(F\) has \(D(|V(G)| - 1)\) edges. As a union of \(D\) forests, \(F\) is independent in \(M(\tilde G)\) (lemma 15.8). As \(\operatorname {def}(\tilde G) \ge 0\), KT eq. (2.4) (theorem 20.12) gives \(\operatorname {rank} M(\tilde G) \le D(|V(G)| - 1)\). So \(F\) is a base, and KT eq. (2.4) gives \(\operatorname {def}(\tilde G) = 0\).
Conversely, let \(\operatorname {def}(\tilde G) = 0\), and let \(B\) be a base of \(M(\tilde G)\). Then \(|B| = D(|V(G)| - 1)\) by KT eq. (2.4). The multigraph \(H = \tilde G \restriction B\) is \((D, D)\)-sparse (definition 20.1), so it is \((D, D)\)-tight. It is also connected. Otherwise \(V(G)\) is the union of two disjoint nonempty sets \(V_1\) and \(V_2\) with no edge of \(H\) between them. For \(i = 1, 2\), the edges of \(H\) inside \(V_i\) number at most \(D|V_i| - D\): by sparsity if there are any, and as \(|V_i| \ge 1\) if there are none. So \(|B| \le D|V(G)| - 2D\), against \(|B| = D|V(G)| - D\). By corollary 16.19, \(B\) is the union of \(D\) disjoint spanning trees of \(H\), and these are spanning trees of \(\tilde G\).
20.3 The deficiency and the rank of \(R(G,p)\)
This subsection bounds the rank of the rigidity matrix \(R(G,p)\) of a body-hinge framework \((G,p)\) (section 19) by the deficiency of \(\tilde G\): first for a framework on \(G\), then for one that also has bodies on no edge of \(G\).
Let \((G,p)\) be a body-hinge framework with \(V\) nonempty, and suppose that \(C(p(e)) \neq 0\) at every edge \(e\) of \(G\) whose two ends differ. Then
that is, \(\operatorname {rank} R(G,p) \le D(|V|-1) - \operatorname {def}(\tilde G)\).
Let \(P\) be a partition of \(V\), and let \(W_P\) be the space of screw assignments that are constant on each part of \(P\). It has dimension \(D|P|\). On \(W_P\), the hinge constraint at an edge inside a part always holds. At an edge \(e\) that joins two parts it consists of \(D - 1\) linear equations, since \(C(p(e)) \neq 0\) (definition 19.5); a loop joins no two parts, so the hypothesis is not asked of it. So the infinitesimal motions in \(W_P\) form a subspace of dimension at least
A partition \(P\) with \(\operatorname {def}_{\tilde G}(P) = \operatorname {def}(\tilde G)\) gives the bound.
This bound holds at every realization, generic or not, and it is one of the two inequalities of the rank formula in proposition 28.42. Jackson and Jordán derive its rank form from a count of independent rows [ JJ10 , § 4 ] ; we count motions instead.
Later chapters consider a framework on a subgraph \(G\) of a fixed graph together with all the bodies of the fixed graph, as section 19.3 does. Its screw assignments are maps \(B \to \bigwedge ^{d-1}K^{d+1}\) on a finite set \(B\) of bodies that contains \(V(G)\), and \(R(G,p)\) and \(Z(G,p)\) are defined as before. A body of \(B \setminus V(G)\) lies on no edge of \(G\), so no hinge constraint involves it.
Let \((G,p)\) be a body-hinge framework whose screw assignments are defined on a finite set \(B\) of bodies with \(\emptyset \neq V(G) \subseteq B\), and suppose that \(C(p(e)) \neq 0\) at every edge \(e\) of \(G\) that is not a loop. Then
that is, \(\operatorname {rank} R(G,p) \le D(|V(G)| - 1) - \operatorname {def}(\tilde G)\).
Let \(P\) be a partition of \(V(G)\) with \(\operatorname {def}_{\tilde G}(P) = \operatorname {def}(\tilde G)\), and let \(P'\) be the partition of \(B\) whose parts are those of \(P\) and the singletons \(\{ b\} \) for \(b \in B \setminus V(G)\). No edge meets these singletons, so exactly \(d_G(P)\) edges join different parts of \(P'\). The count in the proof of lemma 20.15, applied to \(P'\), gives
The rank form follows, as \(\operatorname {rank} R(G,p) = D|B| - \dim Z(G,p)\).
20.4 Rigid subgraphs and structural lemmas
This subsection proves the properties of \(k\)-dof-graphs that Katoh and Tanigawa establish in their §3, and some deficiency computations that later chapters use. We define rigid subgraphs, and show that a \(0\)-dof-graph is \(2\)-edge-connected (KT Lemma 3.1) and that minimality passes to subgraphs (KT Lemma 3.3). Then we compare the deficiency of a multigraph with those of its pieces: at a cut of at most one edge (KT Lemma 3.6), at a cut vertex, and along an ear. We also define the largest value of a partition that keeps two given vertices in one part, and show that every multigraph has a minimal spanning subgraph of the same deficiency. Finally we treat the circuits of \(M(\tilde G)\) (the first step of KT Lemma 3.4), show that the two-vertex double edge and a short cycle are \(0\)-dof-graphs, and list the minimal \(k\)-dof-graphs with at most two vertices.
Katoh and Tanigawa’s combinatorial induction contracts proper rigid subgraphs (section 21).
Let \(H\) be a subgraph of a multigraph \(G\). Then \(H\) is a rigid subgraph of \(G\) if \(H\) is a \(0\)-dof-graph. It is a proper rigid subgraph if moreover \(1 {\lt} |V(H)| {\lt} |V(G)|\).
These are Katoh and Tanigawa’s definitions [ KT11 , pp. 658–659 ] . When \(V(H)\) is nonempty, \(H\) is rigid exactly when \(\tilde H\) contains \(D\) edge-disjoint spanning trees (KT Proposition 2.2). A subgraph with one vertex is always rigid, as its only partition has one part; the condition \(|V(H)| {\gt} 1\) excludes these.
Let \(D \ge 1\), let \(G\) be a \(0\)-dof-graph, and let \(V'\) be a set of vertices of \(G\) with \(\emptyset \neq V' \neq V(G)\). Then at least two edges of \(G\) join \(V'\) to \(V(G) \setminus V'\).
Let \(P = \{ V', V(G) \setminus V'\} \). If at most one edge joined \(V'\) to \(V(G) \setminus V'\), then \(d_G(P) \le 1\), and
contradicting \(\operatorname {def}(\tilde G) = 0\).
The formal statement fixes \(a \in V'\) and \(b \in V(G) \setminus V'\), and counts the edges whose ends get different labels under the labeling that sends \(V'\) to \(a\) and every other vertex to \(b\) (formalization note 20.4). A second pin defines this labeling, and a third shows that it has two parts.
We name the edges of such a cut, with Katoh and Tanigawa’s notation [ KT11 , p. 654 ] , and define \(2\)-edge-connectivity by the condition of lemma 20.18.
Let \(G\) be a multigraph. For a set \(V'\) of vertices of \(G\), let \(\delta _G(V')\) be the set of edges of \(G\) that join \(V'\) to \(V(G) \setminus V'\), and let \(d_G(V') = |\delta _G(V')|\). Then \(G\) is \(2\)-edge-connected if \(d_G(V') \ge 2\) for every set \(V'\) with \(\emptyset \neq V' \neq V(G)\).
Let \(G\) be a multigraph. If \(D \ge 1\) and \(G\) is a \(0\)-dof-graph, then \(G\) is \(2\)-edge-connected. If \(G\) is \(2\)-edge-connected and has at least two vertices, then every vertex of \(G\) has degree at least \(2\).
The first claim is lemma 20.18. For the second, let \(v\) be a vertex of \(G\). As \(G\) has another vertex, \(\emptyset \neq \{ v\} \neq V(G)\), so \(d_G(\{ v\} ) \ge 2\). The edges of \(\delta _G(\{ v\} )\) are the edges at \(v\) that are not loops, so \(d_G(\{ v\} )\) is at most the degree of \(v\).
The formalization states lemma 20.18 with a labeling, as its formalization note explains. The formal proof identifies \(\delta _G(V')\) with the set of edges whose ends get different labels under that labeling (cutEdges_eq_crossingEdges_cutLabeling). For \(V' = \{ v\} \), these are the edges at \(v\) that are not loops (crossingEdges_cutLabeling_singleton_subset), and their number is at most the degree of \(v\) (crossingEdges_cutLabeling_singleton_ncard_le).
Let \(D \ge 1\), and let \(G\) be a \(0\)-dof-graph with at least one vertex. Then \(G\) is connected. If \(G\) has at least two vertices, then every vertex of \(G\) has degree at least \(2\).
By lemma 20.21, \(G\) is \(2\)-edge-connected, and this gives the bound on the degrees. If \(G\) were disconnected, the vertex set \(V'\) of one of its components would have \(\emptyset \neq V' \neq V(G)\) and \(d_G(V') = 0\).
Next we show that minimality passes to subgraphs. If \(H\) is a subgraph of \(G\), then \(\tilde H\) is a subgraph of \(\tilde G\), and their matroids are related as follows.
Let \(H\) be a subgraph of a multigraph \(G\). Then \(M(\tilde H)\) is the restriction of \(M(\tilde G)\) to \(E(\tilde H)\):
Both matroids have the ground set \(E(\tilde H)\). Let \(F \subseteq E(\tilde H)\). By definition 20.1, \(F\) is independent in \(M(\tilde G)\) if and only if \(\tilde G \restriction F\) is \((D, D)\)-sparse, and in \(M(\tilde H)\) if and only if \(\tilde H \restriction F\) is. Each edge of \(\tilde H\) has the same ends in \(\tilde H\) as in \(\tilde G\), and sparsity depends only on the edges and their ends (definition 16.1). So the two conditions agree.
Let \(G\) be a minimal \(k\)-dof-graph, and let \(H\) be a subgraph of \(G\) with \(\operatorname {def}(\tilde H) = k'\). Then \(H\) is a minimal \(k'\)-dof-graph. In particular, a rigid subgraph of a minimal \(k\)-dof-graph is a minimal \(0\)-dof-graph.
We follow Katoh and Tanigawa’s proof [ KT11 , p. 657 ] . As \(H\) is a \(k'\)-dof-graph, we must show that a base \(B'\) of \(M(\tilde H)\) meets \(\tilde e\) for every edge \(e\) of \(H\). By lemma 20.24, \(B'\) is a maximal subset of \(E(\tilde H)\) that is independent in \(M(\tilde G)\). Extend \(B'\) to a base \(B\) of \(M(\tilde G)\). Then \(B \cap E(\tilde H)\) is independent and contains \(B'\), so it equals \(B'\). As \(G\) is minimal, \(B\) meets \(\tilde e\), and \(\tilde e \subseteq E(\tilde H)\) because \(e\) is an edge of \(H\). Hence \(B'\) meets \(\tilde e\).
Katoh and Tanigawa prove their Lemma 3.6 by writing \(M(\tilde G)\) as a direct sum, using their Lemmas 3.1 and 3.4; we compare partitions directly. For a set \(X\) of vertices of \(G\), \(G[X]\) is the subgraph induced by \(X\), and \(\tilde G[X] = (D-1)\cdot G[X]\). We first compute the value of a partition none of whose parts meets both sides of a cut.
Let \(G\) be a multigraph, let \(V'\) be a set of vertices of \(G\) with \(\emptyset \neq V' \neq V(G)\), and let \(V'' = V(G) \setminus V'\). Let \(P\) be a partition of \(V(G)\) that is separated, that is, each of its parts lies in \(V'\) or in \(V''\). Let \(P'\) and \(P''\) be the partitions of \(V'\) and of \(V''\) formed by these parts. Then
An edge of \(G\) joins different parts of \(P\) if and only if it joins different parts of \(P'\), or of \(P''\), or lies in \(\delta _G(V')\). As \(|P| - 1 = (|P'| - 1) + (|P''| - 1) + 1\), the identity follows.
Let \(G\) be a multigraph.
Let \(V'\) be a set of vertices of \(G\) with \(V' \neq V(G)\) and \(d_G(V') \le 1\), and let \(V'' = V(G) \setminus V'\). Then
\[ \operatorname {def}(\tilde G) \; =\; \operatorname {def}(\tilde G[V']) + \operatorname {def}(\tilde G[V'']) + D - (D-1)\, d_G(V'). \]So the cut adds \(1\) to the sum if \(d_G(V') = 1\), and \(D\) if \(d_G(V') = 0\).
If \(G\) is a minimal \(k\)-dof-graph that is not \(2\)-edge-connected, then for some nonempty set \(V'\) as in (1), \(G[V']\) and \(G[V'']\) are minimal \(k'\)- and \(k''\)-dof-graphs, where \(k' = \operatorname {def}(\tilde G[V'])\), \(k'' = \operatorname {def}(\tilde G[V''])\), and \(k = k' + k'' + D - (D-1)\, d_G(V')\).
If \(G\) has no loops, \(V'\) is as in (1), and an edge of \(G\) joins \(V'\) to a vertex \(w \notin V'\), then \(\operatorname {def}(\tilde G[V' \cup \{ w\} ]) = \operatorname {def}(\tilde G[V']) + 1\).
(1) If \(V' = \emptyset \), then \(V'' = V(G)\) and \(d_G(V') = 0\), and the only partition of \(\emptyset \) has no part, so \(\operatorname {def}(\tilde G[V']) = -D\) and (1) holds. Let \(V' \neq \emptyset \). The union of a partition \(P'\) of \(V'\) and a partition \(P''\) of \(V''\) is a separated partition of \(V(G)\), whose value is given by lemma 20.26. Taking \(P'\) and \(P''\) of largest value gives the inequality \(\ge \) in (1).
For \(\le \), let \(P\) be any partition of \(V(G)\), and split each part \(Q\) that meets both \(V'\) and \(V''\) into \(Q \cap V'\) and \(Q \cap V''\). The result is a separated partition. If \(s\) parts are split, the number of parts rises by \(s\). Let \(c\) be the number of edges that join different parts of the new partition but not of \(P\). Each of them lies in \(\delta _G(V')\), so \(c \le 1\), and \(c = 0\) if \(s = 0\). So the value changes by \(Ds - (D-1)c \ge 0\). Hence the value of \(P\) is at most that of a separated partition (exists_sides_separated_partitionDef_le). By lemma 20.26, the value of a separated partition is at most the right-hand side of (1).
(2) As \(G\) is not \(2\)-edge-connected, some set \(V'\) with \(\emptyset \neq V' \neq V(G)\) has \(d_G(V') \le 1\). The formula for \(k\) is (1), and \(G[V']\) and \(G[V'']\) are minimal by KT Lemma 3.3 (lemma 20.25). This is the first step of Katoh and Tanigawa’s proof of their Lemma 6.1 [ KT11 , p. 672 ] .
(3) Apply (1) to the multigraph \(G[V' \cup \{ w\} ]\) and the set \(\{ w\} \). Since \(d_G(V') \le 1\), the given edge is the only edge of \(G[V' \cup \{ w\} ]\) at \(w\). The multigraph \(G[\{ w\} ]\) has no edge, as \(G\) has no loops, and its deficiency is \(0\), as its only partition has one part. The other side is \(G[V']\), and \(D - (D-1) = 1\).
The three pins are statements (1), (2) and (3). Partitions are labelings in the formalization (formalization note 20.4). The value of a labeling depends only on its labels on \(V(G)\) (partitionDef_congr), and it does not change when the labels are renamed injectively (partitionDef_comp_of_injOn). The proof of (1) uses these two facts to give the two sides disjoint sets of labels before it combines their partitions.
Let \(G\) be a multigraph without loops, and let \(V_1\) and \(V_2\) be sets of vertices of \(G\) with \(V_1 \cup V_2 = V(G)\) and \(V_1 \cap V_2 = \{ v\} \), such that every edge of \(G\) lies inside \(V_1\) or inside \(V_2\). Then
Let \(P\) be a partition of \(V(G)\). For \(i = 1, 2\), the nonempty sets \(Q \cap V_i\) with \(Q \in P\) form a partition \(P_i\) of \(V_i\). Let \(I\) be the set of parts of \(P\) that meet both \(V_1\) and \(V_2\), so that \(|P_1| + |P_2| = |P| + |I|\). An edge of \(G\) inside \(V_i\) joins different parts of \(P\) if and only if it joins different parts of \(P_i\). No edge lies inside both \(V_1\) and \(V_2\), since it would be a loop at \(v\). Hence
The part of \(P\) that contains \(v\) lies in \(I\), so \(|I| \ge 1\), and the value of \(P\) is at most the right-hand side of the lemma.
Conversely, let \(P_1\) and \(P_2\) be partitions of \(V_1\) and \(V_2\) of largest value. Let \(P\) consist of the union of their two parts that contain \(v\), together with their other parts. Then \(P\) is a partition of \(V(G)\), the partitions of \(V_1\) and \(V_2\) that it gives as above are \(P_1\) and \(P_2\), and \(|I| = 1\). By the identity above, the value of \(P\) is the right-hand side.
With partitions as labelings (formalization note 20.4), \(I\) is the set of labels used both on \(V_1\) and on \(V_2\). The third pin is the identity of the proof for two sets \(V_1\) and \(V_2\) that meet in two vertices \(u\) and \(v\) not joined by an edge; a cut vertex is the case \(u = v\). The second pin is the lemma, and the first is its inequality \(\ge \). The proof of the first renames the labels of two attaining labelings injectively (partitionDef_comp_of_injOn), so that their sets of labels meet only in the label of \(v\).
Let \(V_1\) be a set of vertices of \(G\). A path of \(G\) whose ends lie in \(V_1\), possibly equal, and whose other vertices lie outside \(V_1\) is an ear on \(V_1\); section 30.6 calls it open if its ends differ and closed otherwise. The next two lemmas compare the deficiency of \(G\) with that of \(G[V_1]\) when \(G\) consists of \(G[V_1]\) and one ear.
Let \(D \ge 1\), let \(G\) be a multigraph, and let \(V_1\) be a set of vertices of \(G\). Let \(a - x_1 - \cdots - x_k - b\) (\(k \ge 1\)) be a path of \(G\) with \(a, b \in V_1\), possibly \(a = b\), and distinct vertices \(x_1, \dots , x_k\) outside \(V_1\), such that \(V(G) = V_1 \cup \{ x_1, \dots , x_k\} \) and every edge of \(G\) off the path lies inside \(V_1\). Then
Let \(V'' = \{ x_1, \dots , x_k\} \), and let \(P''\) be the partition of \(V''\) into single vertices. Take a partition \(P_1\) of \(V_1\) of largest value, and let \(P = P_1 \cup P''\). Each part of \(P\) lies in \(V_1\) or in \(V''\), so \(P\) is separated in the sense of lemma 20.26, with \(V' = V_1\). That lemma gives
The edges of \(G[V'']\) are among the \(k - 1\) edges \(x_i x_{i+1}\) of the path. As \(D \ge 1\), the value of \(P''\) is therefore at least \(D(k - 1) - (D - 1)(k - 1) = k - 1\). The edges of \(\delta _G(V_1)\) are among the two end edges \(a x_1\) and \(x_k b\) of the path, so \(D - (D-1)\, d_G(V_1) \ge 2 - D\). Since \(\operatorname {def}(\tilde G) \ge \operatorname {def}_{\tilde G}(P)\), the bound follows.
In the proof of lemma 20.31, the vertices of the ear form parts of their own. If they can instead join a part that contains both ends of the ear, the deficiency does not drop.
Let \(G\) be a multigraph, and let \(V_1\) be a set of vertices of \(G\). Let \(a - x_1 - \cdots - x_k - b\) (\(k \ge 0\)) be a walk of \(G\) with \(a, b \in V_1\), possibly \(a = b\), and vertices \(x_1, \dots , x_k\) outside \(V_1\), not necessarily distinct, such that \(V(G) = V_1 \cup \{ x_1, \dots , x_k\} \) and every edge of \(G\) off the walk lies inside \(V_1\). Suppose that some partition of \(V_1\) of value \(\operatorname {def}(\tilde G[V_1])\) has \(a\) and \(b\) in one part. Then
Let \(P_1\) be such a partition, and let \(P\) be obtained from it by adding \(x_1, \dots , x_k\) to the part that contains \(a\) and \(b\). Then \(|P| = |P_1|\). Every edge of the walk lies inside that part. Every other edge of \(G\) lies inside \(V_1\), where \(P\) and \(P_1\) agree, so it joins different parts of \(P\) if and only if it joins different parts of \(P_1\). Hence the value of \(P\) is that of \(P_1\), which is \(\operatorname {def}(\tilde G[V_1])\).
The hypothesis of lemma 20.32 says that the largest value of a partition of \(V_1\) with \(a\) and \(b\) in one part is \(\operatorname {def}(\tilde G[V_1])\). We give this largest value a name.
Let \(G\) be a multigraph, and let \(u\) and \(v\) be vertices of \(G\). The merged deficiency of \(\tilde G\) at \(u\) and \(v\) is
the maximum over the partitions \(P\) of \(V(G)\) that have \(u\) and \(v\) in one part.
So \(\operatorname {def}_{\tilde G}(P) \le \operatorname {def}(\tilde G; u, v)\) for every partition \(P\) with \(u\) and \(v\) in one part, and \(\operatorname {def}(\tilde G; u, v) \le \operatorname {def}(\tilde G)\). We use the merged deficiency when an edge joining \(u\) and \(v\) is added: the new edge lowers the value of each partition that separates \(u\) and \(v\) by \(D - 1\), and leaves the value of every other partition unchanged (lemma 21.36).
Katoh and Tanigawa reduce their Theorem 5.6, on the realizations of an arbitrary multigraph, to minimal \(k\)-dof-graphs, by deleting edges while the deficiency stays the same [ KT11 , p. 670 ] .
Let \(D \ge 1\), and let \(G\) be a multigraph with at least one vertex. Then \(G\) has a spanning subgraph that is a minimal \(\operatorname {def}(\tilde G)\)-dof-graph.
Among the sets \(F\) of edges of \(G\) with \(\operatorname {def}(\widetilde{G \restriction F}) = \operatorname {def}(\tilde G)\), such as \(E(G)\), choose one, \(F_0\), of least size. Then \(G' = G \restriction F_0\) is a spanning subgraph of \(G\) with \(\operatorname {def}(\widetilde{G'}) = \operatorname {def}(\tilde G)\).
Suppose that a base \(B\) of \(M(\widetilde{G'})\) misses \(\tilde e\) for some edge \(e\) of \(G'\), and let \(G'' = G \restriction (F_0 \setminus \{ e\} )\). Then \(B \subseteq E(\widetilde{G''})\), so \(B\) is independent in \(M(\widetilde{G''})\) (lemma 20.24). The multigraphs \(G'\) and \(G''\) have the vertices of \(G\), so KT eq. (2.4) (theorem 20.12) gives
As \(D \ge 1\), deleting an edge does not lower the value of a partition, so \(\operatorname {def}(\widetilde{G''}) \ge \operatorname {def}(\widetilde{G'})\). Hence \(F_0 \setminus \{ e\} \) keeps the deficiency of \(G\), against the choice of \(F_0\). So every base of \(M(\widetilde{G'})\) meets \(\tilde e\) for every edge \(e\) of \(G'\), and \(G'\) is minimal.
Let \(G\) be a multigraph, let \(X\) be a circuit of \(M(\tilde G)\), and let \(e \in X\). Then \(\tilde G \restriction (X - e)\) is \((D, D)\)-sparse, and \(X - e\) is a basis of \(X\), that is, a maximal subset of \(X\) that is independent in \(M(\tilde G)\).
As \(X\) is a minimal dependent set, \(X - e\) is independent, so \(\tilde G \restriction (X - e)\) is \((D, D)\)-sparse (definition 20.1). As \(X\) itself is dependent, no larger subset of \(X\) is independent.
Katoh and Tanigawa’s Lemma 3.4 says more: \(G[V(X)]\) is a rigid subgraph of \(G\), and \(X - e\) is the union of \(D\) edge-disjoint spanning trees on \(V(X)\) [ KT11 , p. 658 ] . We prove this in the next chapter (lemma 21.2), using KT eq. (2.4).
Katoh and Tanigawa prove their Theorem 5.5 by induction on the number of vertices, from the case of two vertices [ KT11 , p. 671 ] . The next lemma computes the deficiency of the two-vertex double edge, and the one after it that of a short cycle, which the next chapter uses (section 21). The third lists the minimal \(k\)-dof-graphs with two vertices, and with one.
Let \(D \ge 2\), and let \(H\) be a multigraph with two vertices \(x \neq y\) and two edges \(e_1 \neq e_2\), each joining \(x\) and \(y\). Then \(H\) is a \(0\)-dof-graph.
The partitions of \(V(H)\) are \(\{ V(H)\} \), of value \(0\), and \(\{ \{ x\} , \{ y\} \} \). Both edges join the two parts of the second, so its value is \(D - 2(D - 1) = 2 - D \le 0\) (definition 20.3). Hence \(\operatorname {def}(\tilde H) = 0\).
Let \(3 \le m \le D\), and let \(C\) be a multigraph whose vertices are \(m\) distinct vertices \(v_0, \dots , v_{m-1}\) and whose edges are \(m\) edges \(f_0, \dots , f_{m-1}\), where \(f_i\) joins \(v_i\) and \(v_{i+1}\), with indices modulo \(m\). Then \(C\) is a \(0\)-dof-graph.
Let \(P\) be a partition of \(V(C)\) into at least two parts. Each part is a proper subset of \(V(C)\), so it has a vertex \(v_i\) whose successor \(v_{i+1}\) lies in another part. The edge \(f_i\) joins two parts, and different parts give different edges. So at least \(|P|\) edges join different parts, and the value of \(P\) (definition 20.3) is at most \(D(|P| - 1) - (D-1)|P| = |P| - D \le 0\), as \(|P| \le m \le D\). The partition into one part has value \(0\), so \(\operatorname {def}(\tilde C) = 0\).
The pin takes the vertices and the edges of \(C\) as two maps on \(\{ 0, \dots , m-1\} \), and it does not ask that the vertices be distinct.
Let \(D \ge 2\), and let \(G\) be a minimal \(k\)-dof-graph with one or two vertices. Then exactly one of the following holds: (i) \(G\) has no edge, and \(k = D(|V(G)| - 1)\); (ii) \(G\) has two vertices and one edge, which joins them, and \(k = 1\); (iii) \(G\) has two vertices and two edges, each of which joins them, and \(k = 0\).
We first compute three deficiencies. If a multigraph \(H\) has no edge, then every partition \(P\) of \(V(H)\) has value \(D(|P| - 1) \le D(|V(H)| - 1)\), with equality for the partition into single vertices, so \(\operatorname {def}(\tilde H) = D(|V(H)| - 1)\) (deficiency_of_edgeSet_empty). Let \(H\) have two vertices \(x\) and \(y\). Its partitions are \(\{ V(H)\} \), of value \(0\), and \(\{ \{ x\} , \{ y\} \} \). If \(H\) has one edge, joining \(x\) and \(y\), the second has value \(D - (D - 1) = 1\), so \(\operatorname {def}(\tilde H) = 1\) (deficiency_of_single_edge). If \(H\) has two edges, each joining \(x\) and \(y\), the second has value \(D - 2(D - 1) = 2 - D \le 0\), so \(\operatorname {def}(\tilde H) = 0\). This last computation is lemma 20.36.
A minimal \(k\)-dof-graph has no loops. Indeed, let \(p\) be a copy of a loop of \(G\). Then \(\tilde G \restriction \{ p\} \) is not \((D, D)\)-sparse, as \(1 {\gt} D \cdot 1 - D\), so no base of \(M(\tilde G)\) contains \(p\) (definition 20.1). As every base of \(M(\tilde G)\) meets the copies of each edge of \(G\), \(G\) has no loop. Hence if \(G\) has one vertex, it has no edge, and (i) holds.
Let \(G\) have two vertices \(x\) and \(y\), so that every edge of \(G\) joins them. Suppose that \(G\) had three edges \(e_1, e_2, e_3\), and let \(H = G \restriction \{ e_1, e_2\} \). Then \(\operatorname {def}(\tilde H) = 0\), so a base \(B_H\) of \(M(\tilde H)\) has \(D\) elements by KT eq. (2.4) (theorem 20.12). It is independent in \(M(\tilde G)\) (lemma 20.24), so \(\operatorname {rank} M(\tilde G) \ge D\). By KT eq. (2.4) for \(G\), \(k = D - \operatorname {rank} M(\tilde G) \le 0\). As \(k \ge 0\), it follows that \(k = 0\) and that \(B_H\) is a base of \(M(\tilde G)\). But \(B_H \subseteq E(\tilde H)\) misses \(\tilde e_3\), against the minimality of \(G\). So \(G\) has at most two edges (edgeSet_ncard_le_two_of_isMinimalKDof_of_ncard_two), and the three computations give (i), (ii) and (iii). Katoh and Tanigawa deduce that \(G\) has at most two edges from their Lemma 3.2: a minimal \(k\)-dof-graph is not \(3\)-edge-connected.