Result of linear algebra. Uses the submodularity of the \(\mathcal{F}\)-rank function.

Count edges and nodes.

Count edges and nodes.

A short proof is given on page 51. A longer, but more general proof uses the graphicness testing subroutine described on page 47.

Follows by the definition of minor via pivots and row/column deletions.

Check using (3.3.17) and (3.3.18) that \(B\) is connected iff it is \(2\)-connected. Thus \(M\) is \(2\)-connected, and hence connected, iff \(B\) is connected.

• (i) is equivalent to (ii) by the definition of \(3\)-connectivity.

• (iii) trivially implies (ii). (Typo in the book?)

• Assuming (ii), if the length of \(B^{1}\) is \(3\) or \(4\), then \(B\) has a zero column or row, or parallel or unit vector rows or columns, which is excluded by the first part of (ii). Thus it suffices to require \(|X_{1} \cup Y_{1}| \geq 5\) and by duality \(|X_{2} \cup Y_{2}| \geq 5\).

Verified by case enumeration.

• By Lemma 3.3.12, \(M\) has a representation matrix that displays \(N\) via a submatrix.

• Case distinction between \(z\) being represented by a nonzero or a zero vector.

• Nonzero case: immediately get submatrix representing \(N'\).

• Zero case: take a shortest path in the matrix, perform pivots, in one subcase use duality.

• \(BG(B)\) is bipartite and has at least one cycle, so there is a cycle \(C\) without chords with at least \(4\) edges.

• Up to indices, the submatrix corresponding to \(C\) is either the matrix for \(M(W_{2})\) from (5.2.8) or the matrix for some \(M(W_{k})\), \(k \geq 3\) from (5.2.9).

• In the latter case, use path shortening pivots on \(1\)s to convert the submatrix to the former case.

Use Lemma 5.2.10 and apply path shortening technique.

By Lemma 5.2.11, \(M\) has a \(2\)-separation or an \(M(W_{3})\) minor. \(M\) is \(3\)-connected, so the former case is impossible.

• Let \(C\) be a binary representation matrix of \(M\) that displays a binary representation matrix \(B\) for \(N\).

• By assumption, \(B\) is \(3\)-connected.

• \(C\) is connected, as otherwise by case analysis \(C\) contains a zero vector or unit vector, so \(M\) has a loop, coloop, parallel elements, or series elements, a contradiction.

• If \(C\) is not \(3\)-connected, then by Lemma 3.3.20 there is a \(2\)-separation of \(C\) with at least \(5\) rows/columns on each side. Then \(B\) has a \(2\)-separation with at least \(2\) rows/columns on each side, a contradiction.

• Thus, \(C\) is \(3\)-connected, so \(M\) is \(3\)-connected.

Argue about the structure of the matrix, applying steps 1 and 2 of the separation algorithm.

Further arguments about the structure of the matrix.

Further arguments about the structure of the matrix.

• (6.3.13) and (6.3.14) establish (a) and (b).

• Lemmas 6.3.15, 6.3.16, and 6.3.17 prove (c.1) and (c.2).

Reason about representation matrices using Theorem 6.3.18, Lemma 6.3.15, minimality, isomorphisms, pivots, and so on.

Follows directly from Theorem 6.3.18 and Lemma 6.3.19.

• Let \(M \in \mathcal{M}\) satisfying the assumptions. Since \(\mathcal{M}\) is closed under isomorphism, suppose that \(N\) itself is a minor of \(M\).

• Suppose the \(k\)-separation of \(N\) does not induce one in \(M\). Then \(M\) or a minor of \(M\) containing \(N\) is minimal under isomorphism.

• By Theorem 6.3.20, \(M\) has a minor represented by (6.3.21), (6.3.22), or (6.3.23). This minor is in \(\mathcal{M}\), as \(\mathcal{M}\) is closed under taking minors, but this contradicts our assumptions.

• Let \(z \in M \setminus N\). By Lemma 5.2.4, there is a connected minor \(N'\) that is a \(1\)-element extension of \(N\) by \(z\). Our theorem holds iff it holds for duals, so by duality, assume that the extension is an addition.

• Reason about a matrix representation of \(N\) and \(N'\) to get a \(2\)-separation of \(N'\). Since \(M\) is \(3\)-connected, this \(2\)-separation does not induce one in \(M\). Let \(M'\) be a minor of \(M\) that proves this fact and is minimal under isomorphism. Additionally, \(M'\) has an \(N'\) minor, so we change the element labels in \(M'\) so that \(N'\) is a minor of \(M'\).

• Apply Theorem 6.3.20 and perform case analysis, reaching either a contradiction or a desired extension.

• If \(N\) is a splitter of \(\mathcal{M}\), then clearly \(\mathcal{M}\) does not contain a \(3\)-connected \(1\)-element extension of \(N\).

• Prove the converse by contradiction. To this end, suppose that \(\mathcal{M}\) does not contain a \(3\)-connected \(1\)-element extension of \(N\) and that \(N\) is not a splitter of \(\mathcal{M}\).

• Thus, \(\mathcal{M}\) contains a \(3\)-connected matroid \(M\) with a proper \(N\) minor and no \(2\)-separation.

• Since \(\mathcal{M}\) is closed under isomorphism, we may assume \(N\) itself to be that \(N\) minor.

• By Theorem 6.4.1 (applied to \(M\) and \(N\)), \(M\) has a \(3\)-connected minor \(N'\) that is a \(3\)-connected \(1\)- or \(2\)-element extension of an \(N\) minor.

• The \(1\)-extension case has been ruled out.

• In the \(2\)-element extension case, \(N'\) is derived from the \(N\) minor by one addition and one expansion. Again, since \(\mathcal{M}\) is closed under isomorphism and minor taking, we may take \(N\) itself to be that \(N\) minor. Thus, \(N'\) is derived from \(N\) by one addition and one expansion.

• Let \(C\) be a binary matrix representing \(N'\) and displaying \(N\). By investigating the structure of \(C\), one can show that \(N'\) contains a \(3\)-connected \(1\)-element extension of an \(N\) minor, which has been ruled out.

Similar to proof of Theorem 7.2.1.a. The analysis of the matrix \(C\) can be done in one go for both cases.

Consider the corresponding graphic matroids, apply splitter theorem, extensions in graphic matroids correspond to extensions in graphs.

Consider the corresponding graphic matroids, apply splitter theorem, extensions in graphic matroids correspond to extensions in graphs.

Up to isomorphism, there is just one \(3\)-connected \(1\)-edge extension of \(K_{5}\). To obtain it, one partitions one vertex of \(K_{5}\) into two vertices of degree \(2\) and connects the two vertices by a new edge. The resulting graph has a \(K_{3,3}\) minor. Thus, the theorem follows from Corollary 7.2.10.a.

There is no \(3\)-connected \(1\)-edge extension of \(W_{3}\), so the theorem follows from Corollary 7.2.10.b.

• Inductively for \(i \geq 0\) assume the existence of a sequence \(M_{0}, \dots , M_{i}\) of \(3\)-connected minors where \(M_{0}\) is isomorphic to \(N\), \(M_{i}\) is not a wheel, and the gap is \(1\).

• If \(M_{i} = M\), we are done, so assume that \(M_{i}\) is a proper minor of \(M\).

• Use the contrapositive of the splitter Theorem 7.2.1.a to find a larger sequence.

  • Let \(\mathcal{M}\) be the collection of all matroids isomorphic to a (not necessarily proper) minor of \(M\).

  • Since \(M_{i}\) is a \(3\)-connected proper minor of the \(3\)-connected \(M \in \mathcal{M}\), it cannot be a splitter of \(\mathcal{M}\). By Theorem 7.2.1.a, \(\mathcal{M}\) contains a matroid \(M_{i + 1}\) that is a \(3\)-connected \(1\)-element extension of a matroid isomorphic to \(M_{i}\).

  • Since every \(1\)-element reduction of a wheel with at least \(6\) elements is \(2\)-separable, \(M_{i + 1}\) is not a wheel, as otherwise \(M_{i}\) is \(2\)-separable, which is a contradiction.

• If necessary, relabel \(M_{0}, \dots , M_{i}\) so that they constitute a sequence of nested minors of \(M_{i + 1}\). This sequence satisfies the induction hypothesis.

• By induction, the claimed sequence exists for \(M\).

Same as the proof of Theorem 7.3.1.a, but uses Theorem 7.2.1.b instead of 7.2.1.a to extend the sequence of minors.

• Let \(\mathcal{M}\) and \(N\) be as specified in Theorem 7.2.1. Suppose \(N\) is not a wheel.

• Prove the nontrivial “if” part by contradiction: let \(M\) be a \(3\)-connected matroid of \(\mathcal{M}\) with \(N\) as a proper minor.

• By Theorem 7.3.1, there is a sequence \(M_{0}, \dots , M_{t} = M\) of nested \(3\)-connected minors where \(M_{0}\) is isomorphic to \(N\) and where the gap is \(1\).

• Since \(\mathcal{M}\) is closed under isomorphism, we may assume that \(M\) is chosen such that \(M_{0} = N\).

• Then \(M_{1} \in \mathcal{M}\) is a \(3\)-connected \(1\)-element extension of \(N\), which contradicts the assumed absence of such extensions.

• If \(N\) is a wheel, the proof is analogous.

Translate Theorem 7.3.1.a directly into graph language.

Translate Theorem 7.3.1.b directly into graph language.

• By Corollary 5.2.15, \(G\) has a \(W_{3}\) minor.

• Let \(H\) be a largest wheel minor of \(G\). Since \(G\) is not a wheel, \(H\) is a proper minor of \(G\).

• Apply Corollary 7.3.2.b to \(G\) and \(H\) to get a sequence of nested \(3\)-connected minors \(G_{0}, \dots , G_{t} = G\) where \(G_{0}\) is isomorphic to \(H\).

• Since \(H\) is the largest wheel minor and \(G\) is not a wheel, Corollary 7.3.2.b shows that \(s = 0\) and \(t \geq 1\).

• Additionally, from corollary we know that \(G = G_{t}\) has exactly one extra edge compared to \(G_{t - 1}\). In other words, \(G_{t - 1} = G / z\) or \(G \setminus z\) for some edge \(z\).

Similar to the proof of Theorem 7.3.3, but use Theorem 7.3.1 instead of Corollary 7.3.2.

• The case in parenthesis is dual to the normally stated one. Thus, only consider expansions below.

• Apply construction from observation before Theorem 7.3.4 to the sequence of minors from Theorem 7.3.1 to get the desired sequence.

• "Only if": planarity is preserved by taking minors, and by Lemma 3.2.48 both \(K_{3,3}\) and \(K_{5}\) are not planar.

• Let \(G\) be a connected nonplanar graph with all proper minors planar. Goal: show that \(G\) is isomorphic to \(K_{3,3}\) or \(K_{5}\).

• Prove that \(G\) cannot be \(1\)- or \(2\)-separable. Thus \(G\) is \(3\)-connected.

• By Corollary 5.2.15, \(G\) has a \(W_{3}\) minor, say \(H\). Note: no \(H\) minor of \(G\) can be extended to a minor of \(G\) by addition of an edge that connects two nonadjacent nodes.

• Then by Corollary 7.3.5.b, there exists a sequence \(G_{0}, \dots , G_{t} = G\) of \(3\)-connected minors where \(G_{0}\) is an \(H\) minor and \(G_{i + 1}\) is constructed from \(G_{i}\) following very specific steps.

• By minimality, \(G_{t - 1}\) is planar and \(G\) is not. Argue about a planar drawing of \(G_{t - 1}\) and how \(G\) can be derived from it. Show that this must result in a subdivision of \(K_{3,3}\) or \(K_{5}\).

Note: Theorem 7.4.1 is equivalent to Kuratowski’s theorem: a \(K_{3,3}\) minor induces a subdivision of \(K_{3,3}\) and a \(K_{5}\) minor also leads to a subdivision of \(K_{5}\) or \(K_{3,3}\) (the latter in the case when an expansion step splits a vertex of degree \(4\) into two vertices of degree \(3\) after the new edge is inserted).

Elementary application of Theorem 3.2.25.a.

• Definitions imply everything except connectedness.

• It is easy to check that connectedness of (8.2.3) implies connectedness of (8.2.4) and vice versa.

• By Lemma 3.3.19, connectedness of representation matrices is equivalent to connectedness of the corresponding matroids.

• Ingredients: look at a \(2\)-separation and the corresponding subgraphs, use Theorem 3.2.25.b, use the switching operation of Section 3.2, use Lemma 8.2.6 and representations (8.2.3) and (8.2.4).

• Use the construction from the drawing, check that fundamental circuits match, conclude that \(M\) is graphic. For planar graphs, the edge identification can be done in a planar way.

• The converse easily follows from (8.3.10), which directly produces a desired \(3\)-separation.

• Take a \(3\)-separation. Since \(M\) is \(3\)-connected, it must be exact. Consider the representation matrix (8.3.11). Reason about that matrix.

• Analyse shortest paths in a bipartite graph based on the matrix.

• Apply path shortening technique from Chapter 5 to reduce a shortest path by pivots to one with exactly two arcs.

• Reason about the corresponding entries and about the effects of the pivots on the matrix.

• Apply Lemma 2.3.14. Eventually get an instance of (8.3.10) with (8.3.9). Thus, \(M\) is a \(3\)-sum.

• Planarity is preserved under taking minors.

• The listed matroids are not planar.

• Let \(M\) be minimally nonplanar with respect to taking minors, i.e., regular nonplanar, but with all proper minors planar.

• Goal: show that \(M\) is isomorphic to one of the listed matroids.

• By Theorem 7.4.1, \(M\) is not graphic or cographic.

• By Lemmas 8.2.2, 8.2.6, and 8.2.7, if \(M\) has a \(1\)- or \(2\)-separation, then \(M\) is a \(1\)- or \(2\)-sum. But then the components of the sum are planar, so \(M\) is also planar. Therefore, \(M\) is \(3\)-connected.

• By the census of Section 3.3, every \(3\)-connected \(\leq 8\)-element matroid is planar, so \(|M| \geq 9\).

• By the binary matroid version of the wheel Theorem 7.3.3, there exists an element \(z\) such that \(M \setminus z\) or \(M / z\) is \(3\)-connected. Dualizing does not afect the assumptions, so we may assume that \(M \setminus z\) is \(3\)-connected.

• Let \(G\) be a planar graph representing \(M \setminus z\). Extend \(G\) to a representation of \(M\) as follows:

  • If \(G\) is a wheel, invoke (10.2.6) or (10.2.4). The latter contradicts regularity of \(M\), the former shows what we need.

  • If \(G\) is not a wheel, use Theorem 7.3.3 and Menger’s theorem. Use a path argument and edge contraction to reduce to (10.2.6) and conclude the proof.

• By Theorem 7.2.1.a, we only need to show that every \(3\)-connected regular \(1\)-element extension of \(M(K_5)\) has an \(M(K_{3,3})\) minor.

• Then case analysis. (The book sketches one way of checking.)

By case analysis via graphs plus \(T\) sets.

This proof is extremely long and technical. It involves case distinctions and graph constructions.

Representations (10.2.8) and (10.2.9) for \(R_{10}\) and \(R_{12}\) show that these are nongraphic and isomorphic to their duals, hence also noncographic, so we are done.

• Let \(M\) be \(3\)-connected, regular, nongraphic, and noncographic matroid.

• Thus \(M\) is not planar, so by Theorem 10.2.11 it has a minor isomorphic to \(M(K_{5})\), \(M(K_{5})^{*}\), \(M(K_{3,3})\), or \(M(K_{3,3})^{*}\).

• By Lemma 10.3.1, \(M(K_{5})\) is a splitter for the regular matroids with no \(M(K_{3,3})\) minors.

• These results imply that \(M\) has a minor isomorphic to \(M(K_{3,3})\), or \(M(K_{3,3})^{*}\), or \(M\) is isomorphic to \(M(K_{5})\) or \(M(K_{5})^{*}\).

• The latter is a contradiction, so \(M\) or \(M^{*}\) has an \(M(K_{3,3})\) minor.

• Theorem 10.3.11 implies that \(M\) or \(M^{*}\) has \(R_{10}\) or \(R_{12}\) as a minor.

• Since \(R_{10}\) and \(R_{12}\) are self-dual, \(M\) has \(R_{10}\) or \(R_{12}\) as a minor.

• \(1\)-sum case: \(M_{1} \oplus _{1} M_{2}\) is represented by a matrix \(B = \mathrm{diag} (A_{1}, A_{2})\) where \(A_{1}\) and \(A_{2}\) represent \(M_{1}\) and \(M_{2}\). Use the same signings for \(A_{1}\) and \(A_{2}\) in \(B\) to prove that \(B\) is TU and hence the \(1\)-sum is regular.

• \(2\)-sum case: Slightly more complicated signing process. Similarly, reuse signings from \(M_{1}\) and \(M_{2}\), define signing on remaining nonzero elements via a concrete formula, then prove that the resulting matrix is TU.

Utilize signings, minimal violation matrices, intersections (inside matrices), column dependence, pivot, duality.

Follows by Lemma 11.2.7.

Yet more complicated, but similar. Uses the result that “\(\Delta Y\) exchanges maintain regularity” (Corollary 11.2.8 of Lemma 11.2.7). The rest of the arguments are similar to the \(2\)-sum case: prove that submatrices are TU, then prove that the whole matrix is TU.

Combine Lemmas 11.2.1 and 11.2.9.

Follows from definitions of \(\Delta \)-sums and \(Y\)-sum, together with Theorem 11.2.10 and Corollary 11.2.8.

• Splitter theorem case (a)

• \(R_{10}\) is self-dual, so it suffices to consider \(1\)-element additions.

• Represent \(R_{10}\) by (11.3.3)

• Up to isomorphism, there are only \(3\) distinct \(3\)-connected \(1\)-element extensions.

• Case 1 (graphic): contract a certain edge, the resulting graph contains a subdivision of (11.3.5), which represents \(F_{7}\). Thus, this extension is nonregular.

• Cases 2, 3 (nongraphic): reduce instances to (11.3.5), same conclusion.

• Preparation: calculate all \(3\)-connected regular \(1\)-element additions of \(R_{12}\). This involves somewhat tedious case checking. (Representation of \(R_{12}\) in (10.2.9) helps a lot.) By the symmetry of \(B^{12}\) and thus by duality, this effectively gives all \(3\)-connected \(1\)-element extensions as well.

• Verify conditions of theorem 11.3.10 (which implies the result).

• (11.3.7) and (11.3.9) are ruled out immediately from preparatory calculations.

• The rest is case checking ((c.1) and (c.2)), simpified by preparatory calculations.

Follows from theorem 11.2.10.

• Let \(M\) be a regular matroid. Assume \(M\) is not graphic and not cographic.

• If \(M\) is \(1\)-separable, then it is a \(1\)-sum. If \(M\) is \(2\)-separable, then it is a \(2\)-sum. Thus assume \(M\) is \(3\)-connected.

• By theorem 10.4.1, \(M\) has an \(R_{10}\) or an \(R_{12}\) minor.

• \(R_{10}\) case: by theorem 11.3.2, \(M\) is isomorphic to \(R_{10}\).

• \(R_{12}\) case: by theorem 11.3.12, \(M\) has an induced by \(3\)-separation, so by lemma 8.3.12, \(M\) is a \(3\)-sum.