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 Δ4

+-minor.

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