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
is a single-element coextension of Δ4, the rank-4 triangular 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
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 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
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
that contains ei-
ther M(K3,3) or M
We characterize the internally 4-connected members
of these classes, and show that each such class has a polynomial-time recognition
Previous Page Next Page