1. INTRODUCTION 3 M with no M(K3,3)-minor. In Lemmas 4.5 and 4.9 we show that if M obeys The- orem 1.1, then M also satisfies the theorem. From this it follows that a minimal counterexample to Theorem 1.1 can be assumed to be vertically 4-connected. The regular matroid R12 was introduced by Seymour in the proof of his decom- position theorem. He shows that R12 contains a 3-separation, and that this 3-sepa- ration persists in any regular matroid that contains R12 as a minor. In Chapter 5 we introduce a binary matroid Δ+ 4 that plays a similar role in our proof. The matroid Δ+ 4 is a single-element coextension of Δ4, the rank-4 triangular M¨ obius matroid. It contains a four-element circuit-cocircuit, which necessarily induces a 3-separa- tion. We show that this 3-separation persists in any binary matroid without an M(K3,3)-minor that has Δ+ 4 as a minor. Hence no internally 4-connected binary matroid without an M(K3,3)-minor can have Δ4 + as a minor. In Corollary 5.3 we show that if M is a 3-connected binary matroid without an M(K3,3)-minor such that M has both a Δ4-minor and a four-element circuit-cocircuit, then M has Δ+ 4 as a minor. Suppose that M is a minimal counterexample to Theorem 1.1. It follows easily from a result of Zhou [Zho04] that M must have a minor isomorphic to Δ4. Hence we deduce that if M is a 3-connected minor of M, and M has a Δ4-minor, then M has no four-element circuit-cocircuit. This is one of the conditions required to apply the connectivity lemma that we prove in Chapter 6. The hypotheses of the connectivity result in Chapter 6 are that M and N are simple vertically 4-connected binary matroids such that |E(N)| ≥ 10 and M has a proper N-minor. Moreover, whenever M is a 3-connected minor of M with an N-minor, then M has no four-element circuit-cocircuit. Under these conditions, Theorem 6.1 asserts that M has a internally 4-connected proper minor M0 such that M0 has an N-minor and |E(M)| − |E(M0)| ≤ 4. The case-checking required to complete our proof would be impossible if we had no more information than that provided by Theorem 6.1. Lemma 6.7 provides a much more fine-grained analysis. It shows that there are nine very specific ways in which M0 can be obtained from M. In Chapter 7 we complete the proof of Theorem 1.1. Our strategy is to assume that M is a vertically 4-connected minimal counterexample to the theorem. We then apply Lemma 6.7, and deduce the presence of a non-cographic proper minor M0 of M that must necessarily obey Theorem 1.1. The rest of the proof consists of a case-check to show that the counterexample M cannot be produced by reversing the nine procedures detailed by Lemma 6.7 and applying them to the M¨ obius matroids and the 18 sporadic matroids. Thus a counterexample to Theorem 1.1 cannot exist. The first of the three appendices contains a description of the case-checking required to complete the proof that a 3-connected binary matroid with both a Δ4-minor and a four-element circuit-cocircuit has a Δ+-minor. 4 The second ap- pendix describes the sporadic matroids, and the third contains information on the three-element circuits of the sporadic matroids. In a subsequent article [MRW] we consider various applications of Theo- rem 1.1. In particular, we consider the classes of binary matroids produced by excluding any subset of {M(K3,3), M(K5), M ∗ (K3,3), M ∗ (K5)} that contains ei- ther M(K3,3) or M ∗ (K3,3). We characterize the internally 4-connected members of these classes, and show that each such class has a polynomial-time recognition

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2010 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.