ON THE 3–CONNECTED MATROIDS THAT ARE MINIMAL HAVING A FIXED RESTRICTION

MANOEL LEMOS, JAMES OXLEY, AND TALMAGE JAMES REID

Abstract. Let N be a restriction of a 3-connected matroid M and let M′ be a 3-connected minor of M that is minimal having N as a restriction. This paper gives a best-possible upper bound on |E(M′) − E(N)|.

1. Introduction

If X is a subset of a 3-connected matroid M, what can be said about the size of a minimal 3-connected minor M′ of M that not only includes X in its ground set but also maintains the matroid structure on X? For instance, if X is a circuit, a basis, or an independent set of M, then X is a circuit, a basis, or an independent set, respectively, of M′. The purpose of this paper is to answer this question. More specifically, we solve the following:

1.1. Problem. Let N be a restriction of a 3-connected matroid M and let M′ be a 3-connected minor of M that is minimal having N as a restriction. Give a sharp upper bound on |E(M′) − E(N)|.

The natural modification of this problem in which “restriction” is replaced by “minor” seems much more difficult, although we do hope to return to it in future work. For this modified problem, Truemper [12] proved, under the additional constraints that N is 3-connected but different from M′, that |E(M′) − E(N)| ≤ 3. In certain natural cases, including those raised above, when N is a circuit, a basis, or an independent set of M, the modified and original problems coincide.

Let M be a matroid and A be a subset of E(M). We define λ_{1}(A, M) to be the number of connected components of M|A. Now M|A can be constructed from a collection Λ_{2}(A, M) of 3–connected matroids by using the operations of direct sum and 2-sum. It follows from results of Cunningham and Edmonds (see Cunningham [3]) that Λ_{2}(A, M) is unique up to isomorphism. We denote by λ_{2}(A, M) the number of matroids in Λ_{2}(A, M) that are not isomorphic to U_{1,3}, the three-element cocircuit.

The next theorem, the main result of [6], solves Problem 1.1 in the case when N spans M.

1.2. Theorem. Let M be a 3–connected matroid other than U_{1,3} and let A be a non-empty spanning subset of E(M). If M has no proper 3–connected minor M′ such that M′|A = M|A, then

|E(M)| ≤ |A| + λ_{1}(A, M) + λ_{2}(A, M) − 2,

1991 Mathematics Subject Classification. 05B35.

unless A is a circuit of M of size at least four, in which case,

|E(M)| ≤ 2|A| − 2.

It is also shown in [6] that Theorem 1.2 is best-possible. Indeed, examples are given that attain the bound for all A such that M|A is simple but not free.

In this paper, we shall prove several results. We solve Problem 1.1 when N is a free matroid by proving the following result.

1.3. Theorem. Let M be a 3–connected matroid and let A be an independent set of M. If M has no proper 3–connected minor M′ in which A is independent, then |E(M)| ≤ 3|A| − 1.

Note that this theorem is best-possible. To see this, suppose that n ≥ 3 and let K′′_{3,n} be the graph obtained from K_{3,n} by joining a degree-n vertex v_{1} of the latter to the two vertices, v_{2} and v_{3}, to which it is non-adjacent. Then it is not difficult to check that equality is attained in the theorem if we take M to be M^{∗}(K′′_{3,n}) and A to be any set consisting of all but one of the edges meeting v_{1}. When A is both independent and spanning, the bound in Theorem 1.3 can be improved by 3 as will be shown in [7].

If A is a subset of the ground set of a 3-connected matroid M, then (M, A) is a minimal pair if M has no proper 3–connected minor M′ such that M′|A = M|A. Thus, in both Theorems 1.2 and 1.3, (M, A) is a minimal pair. Our second theorem shows that the bound in Theorem 1.2 also holds when A is non-spanning, provided A has no small cocircuits. More specifically:

1.4. Theorem. Let (M, A) be a minimal pair such that M|A has no coloops, every series class of M|A has rank at most two, and M ≅ U̸_{1,3}. Then

|E(M)| ≤ |A| + λ_{1}(A, M) + λ_{2}(A, M) − 2.

When A is arbitrary, we shall describe examples in Section 3 to show that |E(M)| can exceed the bound in the last result by an arbitrarily large number. These examples prompt the introduction of another function, λ_{3}(A, M), which is defined by

λ_{3}(A, M) = ∑_{S}(|S| − 3),

where the sum is taken over all series classes S of M|A with at least four elements. The following theorem is one of the two main results of the paper.

1.5. Theorem. If (M, A) is a minimal pair, then

|E(M)| ≤ |A| + λ_{1}(A, M) + λ_{2}(A, M) + λ_{3}(A, M) − α(A, M),

where

α(A, M) = \{ \begin{matrix}0, & when A is a circuit of M \\ 1, & when A is not a circuit \end{matrix}

Note that Theorem 1.3 will follow immediately from the last theorem for, when A is independent, λ_{1}(A, M) = λ_{2}(A, M) = |A|, λ_{3}(A, M) = 0, and α(A, M) = 1. Although the function λ_{3}(A, M) may look strange, it is indispensable, even for cographic matroids. For example, for n ≥ 3, let M be M^{∗}(K′′_{3,n}) and let A be the set of edges meeting the degree-(n + 2) vertex of K′′_{3,n}. Then M|A is a circuit and it is straightforward to check that equality is attained in Theorem 1.5. In Section 3, we shall provide two families of extremal examples for Theorem 1.5 in each of which M|A can be chosen to have many series classes. Prior to that, Section 2 introduces notation, terminology, and some important known results that will be needed. Section 4 develops the properties of minimal pairs that will be used in the proofs of the main results, and these proofs will be given in Section 5.

The essential difference between the bounds in Theorems 1.2 and 1.5 is the presence of λ_{3}(A, M) in the latter. But the former assumes that A spans M. Indeed, if A is non-spanning and (M, A) is a minimal pair, then, for a basis X of M/A, clearly (M, A ∪ X) is a minimal pair in which A ∪ X is spanning. Hence Theorem 1.2 can be applied to this minimal pair. This crude technique yields the bound

|E(M)| ≤ |A| + λ_{1}(A, M) + λ_{2}(A, M) − 2 + 3(r(M) − r(A)).

In the next theorem, our second main result, we shall show that this bound can be sharpened.

1.6. Theorem. If (M, A) is a minimal pair, then

|E(M)| ≤ |A| + λ_{1}(A, M) + λ_{2}(A, M) + r(M) − r(A) − α(A, M),

where

α(A, M) = \{ \begin{matrix}0, & when A is a circuit of M \\ 1, & when A is not a circuit \end{matrix}

If M is an n-spoked wheel with n ≥ 4 and A is its rim, then (M, A) is a minimal pair for which equality is attained in the last theorem. However, for this example, the difference between the bound in Theorem 1.5 and |E(M)| is n − 4.

2. Preliminaries

In this section, we note a number of results that will be used in the proofs of the main theorems. We shall follow Oxley [9] for basic notation and terminology. We shall require some additional terminology and results relating to 3-connected matroids. Tutte [13] calls an element e of a 3–connected matroid M essential if neither the deletion M\e nor the contraction M/e remains 3–connected. Tutte showed that every essential element in a 3-connected matroid is in a triangle or a triad. Indeed, triangles and triads appear constantly in the study of 3-connected matroids, and a very useful concept in this study is that of a chain of triangles and triads. Let T_{1}, T_{2}, …, T_{k} be a non-empty sequence of sets each of which is a triangle or a triad of a matroid M such that, for all i in {1, 2, …, k − 1},

(i) exactly one of T_{i} and T_{i+1} is a triangle; (ii) |T_{i} ∩ T_{i+1}| = 2; and (iii) (T_{i+1} − T_{i}) ∩ (T_{1} ∪ T_{2} ∪ … ∪ T_{i}) is empty. Then we call T_{1}, T_{2}, …, T_{k} a chain of M of length k with links T_{1}, T_{2}, …, T_{k}. By extending the proof of Tutte’s Wheels and Whirls Theorem [13], Oxley and Wu [11] showed that maximal such chains have non-essential elements at both ends.

2.1. Lemma. Let T_{1}, T_{2}, …, T_{k} be a chain in a 3-connected matroid M. Then M has k + 2 distinct elements e_{1}, e_{2}, …, e_{k+2} such that T_{i} = {e_{i}, e_{i+1}, e_{i+2}} for all i. Suppose that |E(M)| ≥ 4 and M is not a wheel or a whirl. If the chain T_{1}, T_{2}, …, T_{k} is maximal, then the elements can be labelled so that neither e_{1} nor e_{k+2} is essential.

Let {e_{1}, e_{2}, e_{3}}, {e_{2}, e_{3}, e_{4}}, …, {e_{k}, e_{k+1}, e_{k+2}} be a chain for some k ≥ 3. Partition {e_{1}, e_{2}, …, e_{k+2}} into X_{e}, those e_{i} for which i is even, and X_{o}, those e_{i} for which i is odd. If {e_{1}, e_{2}, e_{3}} is a triad, then X_{o} is the rim of the chain and X_{e} is its set of spokes. If {e_{1}, e_{2}, e_{3}} is a triangle, then X_{e} is its rim and X_{o} is its set of spokes.

A maximal chain in a 3-connected matroid other than a wheel or whirl is called a fan. A fan has type-1, type-2, or type-3 if its first and last links consist of, respectively, two triangles, two triads, or one triangle and one triad. Oxley and Wu [11] proved the following result, which will be very useful here.

2.2. Theorem. Let M be a 3-connected matroid which is not a wheel or a whirl. Suppose that e is an essential element of M. Then e is in a fan. Moreover, this fan is unique unless

(a) every fan containing e consists of a single triangle and any two such triangles meet in {e};

(b) every fan containing e consists of a single triad and any two such triads meet in {e};

(c) e is in exactly three fans; these three fans are of the same type, each has five elements, together they contain a total of six elements; and, depending on whether these fans are of type-1 or type-2, the restriction or contraction, respectively, of M to this set of six elements is isomorphic to M(K_{4}).

The following basic result of Bixby [1] will be used repeatedly throughout the paper.

2.3. Lemma. Let e be an element of a 3–connected matroid M. Then either M\e or M/e has no non-minimal 2-separations. Moreover, in the first case, the cosimplification of M\e is 3-connected, while in the second case, the simplification of M/e is 3-connected.

The elementary proof of the next lemma is omitted.

2.4. Lemma. If {Z, W } is a k-separation of a matroid M and r(Z) = |Z|, then every k-element subset of Z contains a cocircuit of M.

The next lemma is a straightforward consequence of orthogonality, the property of a matroid that a circuit and a cocircuit cannot have exactly one common element.

2.5. Lemma. If D is a cocircuit of a matroid M such that D ∩ (cl(A) − A) ≠ ∅, then D ∩ A ≠ ∅. In particular, |D ∩ cl(A)| ≥ 2.

The following lemma is proved in [5, (2.12)].

2.6. Lemma. Let e and f be distinct elements of a 3-connected matroid M such that M\e is not 3-connected. If M has triangles T and T′ containing e and f respectively such that |T ∩ T′| = 1 and T ∪ f is a cocircuit of M, then e is in a triad of M.

The last lemma was used in the proof of the following theorem, the main result of [5]

2.7. Theorem. Let C^{∗} be a cocircuit of a 3-connected matroid M and suppose that, for every element e of C^{∗}, the contraction M/e is not 3-connected. Then M has triangles T_{1} and T_{2} such that T_{1} ∩ C^{∗} and T_{2} ∩ C^{∗} are distinct and non-empty.

Next we note a useful property of chains of triangles and triads [11, Lemma 3.4].

2.8. Lemma. Let e_{1}, e_{2}, e_{3}, e_{4}, e_{5} be distinct elements of a 3-connected matroid M that is not isomorphic to M(K_{4}). Suppose that {e_{1}, e_{2}, e_{3}} and {e_{3}, e_{4}, e_{5}} are triangles and {e_{2}, e_{3}, e_{4}} is a triad of M. Then these two triangles and this one triad are the only triangles and triads of M containing e_{3}.

3. Extremal examples

Some examples were given in the introduction showing that equality can be attained in three of the theorems. In this section, we describe families of examples that attain equality in Theorems 1.5 and 1.3.

The examples given here will use the operation of generalized parallel connection [2]. Let the intersection of the ground sets of the matroids M and M(K_{4}) be Δ, which is a triangle in both matroids. The generalized parallel connection of M(K_{4}) and M across Δ is the matroid P_{Δ}(M(K_{4}), M) whose ground set is the union of the ground set of the two matroids and whose flats are the subsets X of the ground set so that X ∩ E(M(K_{4})) is a flat of M(K_{4}) and X ∩ E(M) is a flat of M. If the elements of Δ are deleted from P_{Δ}(M(K_{4}), M), we obtain the same matroid that we would get by performing a Δ − Y -exchange on M across Δ.

Let n be an integer exceeding one. An n-raft [4] is a matroid of rank 2n − 2 whose ground set is the union of n disjoint triangles such that, for all k < n, the union of every set of k of these triangles has rank 2k. One example of an n-raft is the matroid M^{∗}(K_{3,n}). Another is the matroid that is obtained from the direct sum of two n-element circuits {x_{1}, x_{2}, …, x_{n}} and {z_{1}, z_{2}, …, z_{n}} by, for each i, freely adding a new element y_{i} on the line joining x_{i} and z_{i}.

We construct our family of examples by beginning with an n-raft N for some n ≥ 3. Let the distinguished triangles of the raft be T_{1}, T_{2}, …, T_{n} where T_{i} = {x_{i}, y_{i}, z_{i}} for all i, and assume that the raft has the additional property that {z_{1}, z_{2}, …, z_{n}} is a circuit. By repeated generalized parallel connections, attach exactly k distinct copies of M(K_{4}) across each T_{i} in N. Let the resulting matroid be M_{1}. Now, for each i, delete z_{i} from M_{1}. Take M to be the dual of the resulting matroid. In each copy of M(K_{4}) that was attached across some T_{i}, pick the opposite element to z_{i}, that is, the element that is not in a triangle with z_{i}. Do this for all i and let A consist of these nk elements together with the 2n elements of N that remain in M.

We assert that (M, A) is a minimal pair. First note that N is certainly connected. Moreover, if {X, Y } is a 2-separation of N, then neither X nor Y spans N. It is easy to see that each of X and Y may be assumed to be a union of distinguished triangles and from this we obtain a contradiction to the fact that {X, Y } is a 2-separation. Thus N is 3-connected. As M(K_{4}) is also 3-connected, so too is M_{1} [10]. Moreover, it is clear that M_{1}/z_{1} does not simplify to a 3-connected matroid. Thus the cosimplification of M_{1}\z_{1} is 3-connected. This cosimplification is equal to M_{1}\z_{1} since z_{1} is in no triads of M_{1}. By a similar argument, we obtain that M_{1}\z_{1}, z_{2} is 3-connected and, repeating this argument, we eventually obtain that M_{1}\z_{1}, z_{2}, …, z_{n} is 3-connected. But the last matroid is M^{∗}, hence M is 3connected. Let M′ be a minimal 3-connected minor of M such that M|A = M′|A. Now, for each element e of M^{∗} that is not in A, there is another element f of E(M)−A such that e and f are both in the same attached M(K_{4}) in M_{1}. Moreover, e is in a triangle of M^{∗} with two elements of A so M^{∗}/e has two elements of A in parallel. Thus no 3-connected minor of M^{∗}/e contains all the elements of A. Since M^{∗}\e has a 2-cocircuit that contains f and some element of A, a 3-connected minor of M^{∗}\e using all the elements of A must be a 3-connected minor of M^{∗}\e/f. Since f is also in a triangle of M^{∗} with two elements of A, we conclude no 3-connected minor of M^{∗}\e contains all the elements of A. Thus (M, A) is indeed a minimal pair.

Now |E(M)| = 3nk + 2n and |A| = nk + 2n. To find M|A, observe that this matroid is the dual of M^{∗}.A. But, in the last matroid, there is a parallel class that contains T_{i} − z_{i} together with all the elements of A from copies of M(K_{4}) attached across T_{i}. Moreover, by considering the n-raft N, it is not difficult to check that the simplification of M^{∗}.A is a circuit. Thus M|A is the cycle matroid of the graph obtained by joining two vertices by n internally disjoint paths each of length k + 2. Therefore λ_{1}(A, M) = 1, λ_{2}(A, M) = (k + 1)n, λ_{3}(A, M) = (k − 1)n, and α(A, M) = 1. It follows easily that equality holds in Theorem 1.5. One can also easily check that the bound in Theorem 1.6 exceeds |E(M)| by exactly one in this case.

To close this section, we observe that U_{2,6} is a 2-raft. If we perform the above construction beginning with this matroid, we obtain a matroid M for which M|A is independent and equality is attained in Theorem 1.3.

4. Minimal pairs

The purpose of this section is to prove numerous properties of minimal pairs that will be used in the proofs of the main results. The latter will be given in Section 5. We begin with a lemma that gathers together eleven such properties.

MINIMAL 3–CONNECTED MATROIDS HAVING A FIXED RESTRICTION 7

Figure 1.

4.1. Lemma. A minimal pair (M, A) has the following properties:

(i) Suppose e ∈ E(M)−cl(A). Then M\e has no non-minimal 2-separations and the cosimplification of this matroid is 3-connected. Moreover, the simplification of M/e is not 3-connected.

(ii) If e ∈ E(M) − cl(A), then e is essential and belongs to a triad of M. (iii) If A is not a spanning set of M, then |E(M)| > 6 and |A| ≥ 3. (iv) If T is a triangle and T^{∗} is a triad of M such that T ≠ T^{∗} and T ∩ T^{∗} ≠ ∅,

then T^{∗} − T = {a} for some a in cl(A).

(v) If T^{∗} is a triad of M such that |T^{∗} − cl(A)| ≥ 2, then T^{∗} ∩ A ≠ ∅. (vi) Let T_{1} and T_{2} be distinct subsets of E(M) such that both are triangles or both

are triads of M. If (T_{1} ∪ T_{2}) − cl(A) ≠ ∅, then |T_{1} ∩ T_{2}| ≤ 1. (vii) If T is a triangle of M such that {f_{1}, f_{2}} ⊆ T − cl(A), then, for each i in

{1, 2}, there is a triad of M that meets {f_{1}, f_{2}} in {f_{i}}. (viii) If {e_{1}, e_{2}, e_{3}} is a triangle T of M and T ⊆ E(M) − cl(A), then, for each

i in {1, 2, 3}, there is a unique triad T_{i}^{∗} of M such that T_{i}^{∗} ∩ T = T − e_{i}. Moreover,

(a) for each i, the unique element a_{i} of T_{i}^{∗} − T is in A, and {a_{1}, a_{2}, a_{3}} is a triad of M;

(b) M^{∗} = P_{Δ}(M(K_{4}), M^{∗}\T) where Δ = {a_{1}, a_{2}, a_{3}} and M(K_{4}) is labelled as in Figure 1, and M/T is 3-connected;

(c) {a_{1}, a_{2}, a_{3}} is contained in a series class of (M/T)|A, and (M/T)|(A −

a_{i}) = M|(A − a_{i}). (ix) Let T be the set of triangles T of M that meet both cl(A) and E(M) − cl(A).

For every T in T , there is a unique element a_{T} of T ∩ cl(A) and there is a chain T_{1T}^{∗} , T, T_{2T}^{∗} whose rim A_{T} is contained in cl(A). Moreover, if T and T′ are different elements of T , then

(a) A_{T} ≠ A_{T′} and a_{T} ≠ a_{T′};

(b) |(A_{T} ∪ A_{T′}) ∩ A| ≥ 3 with equality only when (1) A_{T} ∪ A_{T′} is contained in a series class of M|cl(A); and (2) T_{jT}^{∗} = T_{iT′}^{∗} for some i and j, or A_{T} − T = A_{T′} − T′.

(x) If r(A) ≤ 3 and A is not spanning, then M is isomorphic to the rank-four wheel having cl(A) as its rim.

(xi) If e ∈ E(M) − cl(A) such that M has no triangle that contains e but avoids cl(A), then e belongs to a triad that meets cl(A) in two elements.

Proof. (i) By Lemma 2.3, the required result follows if we can show that the simplification M′′ of M/e is not 3-connected. But e is a coloop of M|(A ∪ e), so (M/e)|A = M|A, and M′′ can be labelled so that its ground set contains A. Thus M′′ cannot be 3-connected otherwise (M′′, A) contradicts the minimality of (M, A).

(ii) If M\e or M/e is 3-connected, then, since (M\e)|A = M|A = (M/e)|A, either (M\e, A) or (M/e, A) contradicts the choice of (M, A). Thus neither M\e nor M/e is 3-connected, so e is essential. But, by (i), the cosimplification of M\e is 3-connected. Thus e must belong to a triad of M.

(iii) When |A| = 1, we have that E(M) = A; and when |A| = 2, we have that E(M) is a circuit of M having at most three elements. In both cases, A is spanning. Thus we may suppose that |A| ≥ 3. If |A| = 3 and A is dependent, then A is either a circuit or a set of parallel elements, so A is spanning; a contradiction. Thus if |A| = 3, then A is independent. As A is non-spanning, it follows that r(M) ≥ 4. Hence, since M is 3-connected, either r^{∗}(M) ≥ 3 and so |E(M)| > 6, or r^{∗}(M) = 2. In the latter case, M is uniform and so, if e ∈ E(M) − cl(A), then M/e is also uniform of corank two, so M/e is 3-connected; a contradiction to (i). It remains to consider the case when |A| ≥ 4. In that case, since A is non-spanning, there is a cocircuit contained in E(M) − cl(A) and this cocircuit has at least three elements, so |E(M)| > 6.

(iv) Since T and T^{∗} meet but are distinct, orthogonality implies that |T^{∗}−T | = 1. Let a be the unique element of T^{∗} − T. Suppose that a ∉ cl(A). Then A is nonspanning and so, by (iii), |E(M)| > 6. Now M\a has T ∩T^{∗} as a 2-element cocircuit. Thus {T ∩ T^{∗}, E(M\a) − (T ∩ T^{∗})} is a 2-separation of M\a. But T ∩ T^{∗} spans T so {T, E(M\a) − T } is a non-minimal 2-separation of M\a; a contradiction to (i). We conclude that a ∈ cl(A).

(v) Suppose that T^{∗} = {e_{1}, e_{2}, a_{3}} and that e_{i} ∉ cl(A) for each i in {1, 2}. Assume that (v) fails and suppose first that a_{3} ∈ cl(A). Then a_{3} ∈ T^{∗} ∩(cl(A)−A). Hence, by Lemma 2.5, T ∩ A ≠ ∅. We may now assume that a_{3} ∉ cl(A). Then T^{∗} ⊆ E(M)−cl(A). By the dual of Tutte’s triangle lemma [13] (see also [9, Lemma 8.4.9]), there is a triangle T of M that meets the triad T^{∗} in exactly two elements. Thus, by (iv), the unique element of T^{∗} − T is in cl(A). This is a contradiction since T^{∗} ∩ cl(A) = ∅.

(vi) Choose N to be M or M^{∗} so that both T_{1} and T_{2} are triangles of N. Assume that |T_{1} ∩ T_{2}| = 2. Then N|(T_{1} ∪ T_{2}) is isomorphic to U_{2,4}. Now take e in (T_{1} ∪ T_{2}) − cl_{M}(A). Then it is straightforward to check that N\e is 3-connected. Thus M\e or M^{∗}\e is 3-connected, so either M\e or M/e is 3-connected; a contradiction to (ii).

(vii) Suppose that T = {f_{1}, f_{2}, b} for some element b and that, for some i, say i = 1, there is no triad meeting {f_{1}, f_{2}} in {f_{i}}. By Tutte’s triangle lemma [9, Lemma 8.4.9], there is a triad T^{∗} that contains f_{1} and exactly one of b and f_{2}. Hence b ∉ T^{∗} and f_{2} ∈ T^{∗}. By (vi), T^{∗} must be the only triad of M that contains f_{1}. By (i), the cosimplification M′ of M\f_{1} is 3-connected. As the only triad that contains f_{1} is T^{∗}, it follows that M′ = M\f_{1}/f_{2}. But, as |E(M)| ≥ 7, we have |E(M′)| ≥ 5, so M′ is simple. Hence M′ equals the simplification M′′ of M/f_{2}. Therefore M′′ is 3-connected, which is contrary to (i).

(viii) Let i and j be distinct elements of {1, 2, 3}. Taking f_{1} = e_{i} and f_{2} = e_{j} in (vii), we deduce that M has a triad T_{i}^{∗} such that T_{i}^{∗} ∩ {e_{i}, e_{j}} = {e_{j}}. Thus T_{i}^{∗} ∩ T = T − e_{i}. By (vi), T_{i}^{∗} is the unique such triad. Moreover, by (v), T_{i}^{∗} meets A in a single element, say a_{i}.

To finish the proof of (viii)(a), we need to check that {a_{1}, a_{2}, a_{3}} is a triad of M. Observe that there is a cocircuit D of M such that a_{1} ∈ D ⊆ (T_{1}^{∗} ∪ T_{2}^{∗}) − e_{3} = {a_{1}, a_{2}, e_{1}, e_{2}}. As M is 3-connected, it follows that |D| ≥ 3 and hence e_{i} ∈ D for some i. By orthogonality, e_{1} and e_{2} must both belong to D, otherwise D ∩ T = {e_{i}}. As T_{3}^{∗} is the unique triad such that T_{3}^{∗} ∩ T = {e_{1}, e_{2}}, it follows that D = {a_{1}, a_{2}, e_{1}, e_{2}}. Thus there is a cocircuit D′ of M such that a_{1} ∈ D′ ⊆ (D ∪ T_{3}^{∗}) − e_{2} = {a_{1}, a_{2}, a_{3}, e_{1}}. As |D′ ∩ T | ≠ 1 and |D′| ≥ 3, it follows that e_{1} ∉ D′ and that D′ = {a_{1}, a_{2}, a_{3}}, that is, {a_{1}, a_{2}, a_{3}} is a triad of M.

Part (b) is an immediate consequence of [11, Theorem 1.11]. Now we shall prove (c). Let Z = {a_{1}, a_{2}, a_{3}, e_{1}, e_{2}}. We start by proving the following.

4.1.1. Every circuit of M|(A ∪ {e_{1}, e_{2}}) that meets Z must contain Z.

Let C be such a circuit. Since each a_{i} is a coloop of M|A, the circuit C must meet {e_{1}, e_{2}}. Moreover, as neither e_{1} nor e_{2} is spanned by A, it follows that |C − A| ≥ 2 and hence {e_{1}, e_{2}} ⊆ C. As |T_{i}^{∗} ∩ C| ≠ 1 for each i in {1, 2}, it follows that a_{i} ∈ C for each such i. To prove that Z ⊆ C, it remains to show that a_{3} ∈ C. Suppose that this is not the case. Then there is a circuit C′ of M such that e_{3} ∈ C′ ⊆ (C ∪ T) − e_{2}. As C′ ∩ T_{3}^{∗} ⊆ {e_{1}}, it follows that e_{1} ∉ C′. Hence e_{3} ∈ C′ ⊆ A∪e_{3}. This is a contradiction because A does not span e_{3}. Thus Z ⊆ C. We conclude that (4.1.1) holds.

By (viii)(b), M/T, which is isomorphic to M\e_{3}/e_{1}, e_{2}, is 3-connected. Since (M, A) is a minimal pair, M|A ≠ (M\e_{3}/e_{1}, e_{2})|A. Thus M does indeed have a circuit contained in A ∪ {e_{1}, e_{2}} and meeting {e_{1}, e_{2}}. By (4.1.1), it follows that Z is contained in a series class of M|(A∪{e_{1}, e_{2}}). Hence {a_{1}, a_{2}, a_{3}} is contained in a series class of [M|(A∪{e_{1}, e_{2}})]/{e_{1}, e_{2}}, which equals (M/T)|A. Finally, for each i in {1, 2, 3}, each member of Z−a_{i} is a coloop of [M|(A∪{e_{1}, e_{2}})]\a_{i} so M|(A−a_{i}) = [M|(A ∪ {e_{1}, e_{2}})]/{e_{1}, e_{2}}\a_{i} = (M/{e_{1}, e_{2}}\e_{3})|(A − a_{i}) = (M/T)|(A − a_{i}).

(ix) By (vii), if T ∈ T , there are triads of M such that T_{1T}^{∗} , T, T_{2,T}^{∗} is a chain of M having both its spokes in E(M) − cl(A). By (iv), it follows that the set A_{T} of rim elements of this chain is contained in cl(A). Observe that A_{T} is contained in a series class or is a set of coloops of M|cl(A). In both cases, |A_{T} ∩ A| ≥ 2.

Let a_{T} be the unique element of T ∩ cl(A). Let T′ be an element of T − {T }. By Lemma 2.8, a_{T} ∉ T′ and so a_{T} ≠ a_{T′}.

We shall show next that

4.1.2. If a_{T} ∈ T_{1T′}^{∗} ∪ T_{2T′}^{∗}, then A_{T} ≠ A_{T′}, and T_{jT}^{∗} = T_{iT′}^{∗} for some i and j.

Assume, without loss of generality, that a_{T} ∈ T_{2T′}^{∗}. Then, by Lemma 2.8, T_{2T′}^{∗} = T_{iT}^{∗} for some i, say i = 1. Hence T_{1T′}^{∗}, T′, T_{2T′}^{∗}, T is a chain. Moreover, either T_{1T′}^{∗}, T′, T_{2T′}^{∗}, T, T_{2T}^{∗} is a chain, or T_{2T}^{∗} − T ⊆ T_{1T′}^{∗} ∪ T′ ∪ T_{2T′}^{∗}. In the first case, A_{T} ≠ A_{T′}, as required. Now consider the second case, letting X = T ∪ T′ ∪ A_{T′}. By (iii), |E(M)| ≥ 7, so |E(M) − X| ≥ 1. Thus, as X − {a_{T} , a_{T′}} and A_{T′} span X in M and M^{∗}, respectively, we have

1 ≤ r(X) + r^{∗}(X) − |X| ≤ 4 + 3 − 6 = 1.

Since M is 3-connected, it follows that |E(M)| = 7 and r(X) = 4. But r(T ∪T′) = 3 and |E(M)−(T ∪T′)| = 2, so M has a cocircuit of size at most two; a contradiction. We conclude that (4.1.2) holds. It follows immediately from this that (ix)(a) holds.

If A_{T} ∩ A_{T′} = ∅, then

|(A_{T} ∪ A_{T′}) ∩ A| = |A_{T} ∩ A| + |A_{T′} ∩ A| ≥ 4.

Hence (ix)(b) holds in this case, so we may suppose that A_{T} ∩ A_{T′} ≠ ∅. Let S = A_{T} ∪ A_{T′}. Then, in M|cl(A), the set S is contained in a series class or is a set of coloops. Thus, by orthogonality and (a), |A ∩ S| ≥ |S| − 1 ≥ 3. To complete the proof of (b), we now suppose that |S ∩ A| = 3. Then |S| = 4, and S must be contained in a series class of M|cl(A) otherwise the unique element of S − A is a coloop of M|cl(A) contained in cl(A) − A; a contradiction. Thus |A_{T} ∩ A_{T′}| = 2. But, by applying (4.1.2) to both a_{T} and a_{T′}, we have that either T_{jT}^{∗} = T_{iT′}^{∗} for some i and j, or a_{T} ∉ A_{T′} and a_{T′} ∉ A_{T}. In the latter case, A_{T} − {a_{T} } = A_{T′} − {a_{T′}}, that is, A_{T} − T = A_{T′} − T′ and we have established that (ix)(b) holds.

(x) Let T′ be the set of triangles T of M such that T − cl(A) ≠ ∅. As A does not span M, there is a cocircuit of M that avoids cl(A). For each such cocircuit D, by Theorem 2.7, there are distinct triangles T′_{1} and T′_{2} such that T′_{i} ∩ D ≠ ∅. Hence |T′| ≥ 2.

Suppose that T′ has a member T such that T ∩ cl(A) = ∅. Let T = {e_{1}, e_{2}, e_{3}}. By (viii), for each i in {1, 2, 3}, there is a triad T_{i}^{∗} of M and an element a_{i} of A such that T_{i}^{∗} = (T − e_{i}) ∪ a_{i}. Thus a_{i} is a coloop of M|A and hence, |A| = 3 because r(A) ≤ 3 by hypothesis. Therefore A = {a_{1}, a_{2}, a_{3}}. If f ∈ cl(A) − A, then there is a circuit C of M such that f ∈ C ⊆ A ∪ f. Thus a_{i} ∈ C for some i, so C ∩ T_{i}^{∗} = {a_{i}}, which is contrary to orthogonality. Hence cl(A) = A. Let T′ be in T′ − {T }. Next we shall prove that T′ ∩ A ≠ ∅. Assume the contrary. Then T′ avoids T otherwise |T′ ∩ T_{i}^{∗}| = 1 for some i. Now, applying (viii)(c) to the triangle T′, it follows that A is contained in a series class of (M/T′)|A and hence, as |A| = 3, we deduce that A is a circuit of M/T′. But T_{1}^{∗} is a triad of M/T′, a contradiction since |A ∩ T_{1}^{∗}| = 1. We conclude that T′ does indeed meet A. Thus we may assume that a_{1} ∈ T′. By orthogonality, e_{2} or e_{3}, say e_{2}, belongs to T′. By (vi), T ∩T′ = {e_{2}}. As T′ ∩T_{3}^{∗} ≠ {e_{2}}, it follows that a_{3} ∈ T′ and T′ = {a_{1}, e_{2}, a_{3}}. This is a contradiction because it implies that e_{2} ∈ cl(A), yet cl(A) = A.

We may now assume that every T in T′ meets cl(A). Thus, in the notation of (ix), T′ = T . Let T ∈ T . Then A_{T} ∪ T is the union of two triads of M. Thus, in M|cl(A), either (a) A_{T} is contained in a series class, or (b) A_{T} is a set of coloops. But, in the latter case, A_{T} is an independent set of size three. Since A_{T} ⊆ cl(A), we deduce that A_{T} spans cl(A). Thus A_{T} = cl(A) = A. But |T′| ≥ 2 so there is a T′ in T − T. As A_{T′} is a 3-element subset of the 3-element set cl(A), we have A_{T′} = A = A_{T}; a contradiction to (ix)(a). Hence we may assume that (a) holds. Then, as |A_{T} | = 3, either A_{T} is a basis of A, or A_{T} is a triangle. In the second case, letting X = A_{T} ∪ T, we have r(X) + r^{∗}(X) − |X| ≤ 1. This contradicts the fact that M is 3-connected since |X| = 5 and, by (iii), |E(M)| ≥ 7. We conclude that A_{T} is a basis of A and it is not difficult to see that cl(A) is a 4-circuit of M.

Now let T and T′ be distinct triangles in T and let Z = cl(A)∪T ∪T′. Since each of cl(A), T, and T′ is a circuit and cl(A) − (T ∪ T′) is non-empty, we deduce that r(Z) ≤ |Z| − 3. Moreover, each element of T ∪ T′ is in a triad with two elements of cl(A). Thus r^{∗}(Z) ≤ |cl(A)| = 4. Hence

r(Z) + r^{∗}(Z) − |Z| ≤ (|Z| − 3) + 4 − |Z| = 1.

Since {Z, E(M)−Z} is not a 2-separation of M, it follows that |E(M)−Z| ≤ 1 and so |E(M)| ≤ 9. But A_{T} and A_{T′} are distinct 3-element subsets of the 4-element set cl(A), so cl(A) = A_{T} ∪ A_{T′}. Hence every element of cl(A) is in a triad of M. But, by (ii), every element of E(M) − cl(A) is also in a triad of M. Hence M is minimally 3-connected. Moreover, r(M) ≥ 4; and |E(M) − cl(A)| ≥ 4 otherwise E(M) − cl(A) is a triad avoiding A contradicting (v). Thus |E(M)| ≥ 8.

Suppose that r(M) = 4. Then, by Oxley [8], since M is minimally 3-connected, |E(M)| ≤ 8 with equality only if M is a wheel or a whirl. Therefore |E(M)| = 8. Since the only 4-circuit in a rank-four wheel or whirl that is a flat of the matroid is the rim of the rank-four wheel, the result holds when r(M) = 4.

We may now assume that r(M) ≥ 5. Since every cocircuit avoiding the 4circuit cl(A) has size at least four and |E(M)| ≤ 9, it follows that r(M) = 5 and |E(M)| = 9. Thus E(M) − cl(A) contains at least two cocircuits of M. By elimination, it follows that every 4-element subset of E(M) − cl(A) is a cocircuit. But T meets E(M) − cl(A) in exactly two elements, so E(M) − cl(A) contains a cocircuit meeting T in a single element; a contradiction.

(xi) From (ii), there is a triad T^{∗} of M such that e ∈ T^{∗}. Moreover, we may assume that |T^{∗} ∩ cl(A)| ≤ 1 otherwise the result holds. Thus |T^{∗} − cl(A)| ≥ 2. Hence, by Tutte’s triangle lemma, M has a triangle T that meets T^{∗} in exactly two elements, one of which is e. Let T = {e, f, g} where f ∉ cl(A). We may assume that g ∈ cl(A). By (vii), M has a triad T_{e}^{∗} that meets {e, f} in {e}. Orthogonality implies that g ∈ T_{e}^{∗}, and (iv) implies that T_{e}^{∗} − T ⊆ cl(A). Thus |T_{e}^{∗} ∩ cl(A)| = 2, as desired.

4.2. Lemma. Let (M, A) be a minimal pair and T be a triangle of M that avoids cl(A). If a is a member of A that belongs to a triad meeting T, then (M/T, A − a) is a minimal pair.

Proof. Let T = {e_{1}, e_{2}, e_{3}}. Then, by (viii) of Lemma 4.1, for each i, there is a unique triad T_{i}^{∗} of M such that T_{i}^{∗} = (T − e_{i}) ∪ a_{i} for some a_{i} in A. Thus a = a_{i} for some i and, by symmetry, we may assume that i = 3. Let M′ = M/T and A′ = A − a_{3}. By Lemma 4.1(viii)(b), M′ is 3-connected. We may suppose that (M′, A′) is not a minimal pair. Then there is a 3-connected minor N′ of M′ such that N′|A′ = M′|A′ and (N′, A′) is a minimal pair. Let N′ = M′\X/Y. Observe that a_{3} ∉ Y because Lemma 4.1(viii)(b) implies that a_{3} is spanned by A′ in M′.

Suppose that a_{3} ∈ X ∪ E(N′). Then, since {a_{1}, a_{2}, a_{3}} is a triad of M′, either (a) a_{3} ∈ E(N′) and {a_{1}, a_{2}, a_{3}} is a triad of N′; or

(b) {a_{1}, a_{2}, a_{3}} properly contains a cocircuit of N′. In case (b), since N′ is 3-connected and {a_{1}, a_{2}} has rank two in it, we deduce that N′ must be a triangle. As a_{1} and a_{2} are coloops of M′|A′ and M′|A′ = N′|A′, it follows that A′ = {a_{1}, a_{2}} and |A| = 3. This cannot happen by (x) of Lemma 4.1 since the rank-four wheel has no triangle avoiding the closure of its rim. Hence (a) must hold. Now, by Lemma 4.1(viii)(b), M^{∗} = P_{Δ}(M(K_{4}), M^{∗}\T) where Δ = {a_{1}, a_{2}, a_{3}} and M(K_{4}) is labelled as in Figure 1; and (N′)^{∗} = (M^{∗}\T)/X\Y. Since Δ is a triangle of (N′)^{∗}, it follows that

M^{∗}/X\Y = P_{Δ}(M(K_{4}), M^{∗}\T/X\Y) = P_{Δ}(M(K_{4}), (N′)^{∗}).

Let N^{∗} = M^{∗}/X\Y. Since (N′)^{∗} and M(K_{4}) are 3-connected having at least three common elements, by [10], N^{∗} is 3-connected. Hence N is 3-connected.

We shall show next that

4.2.1. N|A′ = M|A′.

To see this, first note that M′|A′ = M|A′ by Lemma 4.1(viii)(c). Moreover, by assumption, N′|A′ = M′|A′. Thus

r_{M}(A′) = r_{M′}(A′) = r_{N′}(A′).

But, since N′ is a minor of N, and N is a minor of M, we have

r_{M}(A′) ≥ r_{N}(A′) ≥ r_{N′}(A′).

Therefore equality holds throughout the last line, so r_{N}(A′) = r_{M}(A′). As N is a minor of M, it is now easy to check that N|A′ = M|A′. Hence (4.2.1) holds.

Since a_{3} is a coloop of both N|A and M|A, it follows from (4.2.1) that N|A = M|A. Therefore, as (M, A) is a minimal pair, N = M and so X ∪ Y is empty and N′ = M′. Thus (M′, A′) is a minimal pair.

4.3. Lemma. Suppose that (M, A) is a minimal pair in which A is non-spanning such that (a) M \ cl(A) has no triangles; and (b) every triad with at least two elements in cl(A) contains at least two elements of A. Let a be an element of A that is in no triangles of M, and N be a minimal 3-connected minor of M/a for which N|(A − a) = (M/a)|(A − a). Then

(i) N = M/a; or (ii) N = M/a\e for some element e of E(M) − A such that {a, e} is contained in

a triad of M whose third element is in A; or (iii) N = M/{a, e}\e′ for some elements e and e′ of E(M) − cl(A) such that

{e, a_{1}, e′} is a triangle of M and {a, e, a_{1}}, {e, a_{1}, e′}, {a_{1}, e′, a_{2}} is a fan of M for some elements a_{1} and a_{2} of A.

Proof. Suppose that N = (M/a)\X/Y. We show first that

4.3.1. Y ∩ cl(A) = ∅.

Assume that (4.3.1) fails and let y be an element of Y ∩ cl(A). As N|(A − a) = (M/a)|(A − a) and N is a minor of M/{a, y}, it follows that

r_{M/a}(A − a) = r_{N}(A − a) ≤ r_{M/{a,y}}(A − a) = r_{M/a}((A − a) ∪ y) − r_{M/a}(y).

Thus y ∉ cl_{M/a}(A − a) so y ∉ cl_{M}(A); a contradiction. Hence (4.3.1) holds. Now choose X and Y such that |X| is as large as possible. Note that

4.3.2. Y ∪ a is independent in M.

If not, there is a circuit C of M such that C ⊆ Y ∪ a. Take y ∈ C − a. Then y is a loop of M/[(Y − y) ∪ a]. Hence N = (M/a)\(X ∪ y)/(Y − y), which is contrary to the choice of X and Y.

We show next that we may also suppose that

4.3.3. |E(N)| ≥ 4.

Suppose not. Then |E(N)| ≤ 3 and so, as N is 3-connected, r(N) ≤ 2. Thus

r_{M}(A) = r_{M/a}(A − a) + 1 = r_{N}(A − a) + 1 ≤ r(N) + 1 ≤ 3

where the second equality holds since N|(A−{a}) = (M/a)|(A−{a}). But now, by (x) of Lemma 4.1, we conclude that M is isomorphic to a rank-four wheel having cl(A) as its rim. Hence a is in a triangle of M; a contradiction.

Next we prove the following.

4.3.4. Let H = M\X_{1}/Y_{1} where X_{1} ⊆ X and Y_{1} ⊆ Y ∪ a. Then H cannot have a cocircuit D such that |D| ≤ 2 and D ⊆ cl(A) − a.

Suppose that such a cocircuit D does exist. We shall prove that D ∩ A ≠ ∅. Assume that D ∩ A = ∅ and let d be an element of D. As d ∉ A, there is a circuit C of M such that d ∈ C ⊆ A ∪ d. Observe that, since A − a ⊆ E(H) and a ∉ X_{1}, the set C contains a circuit C′ of H such that d ∈ C′ ⊆ A ∪ d. Hence C′ ∩ D = {d}, which is contrary to orthogonality. Thus D ∩ A ≠ ∅. Let a′ be an element of D ∩A. Observe that a′ must belong to a cocircuit D′ of N such that D′ ⊆ D. Thus |D′| ≤ |D| ≤ 2, which contradicts (4.3.3) since N is 3-connected. Hence (4.3.4) holds.

The second result that we need about a minor H of M having N as a minor is the following.

4.3.5. If H is not 3-connected, then there is a k-separation {Z, W } of H with k in {1, 2} such that |Z ∩ E(N)| ≤ 1 and Z is closed in both H and H^{∗}.

As H is not 3-connected, it has a k-separation {Z, W } for some k in {1, 2}. But N is a 3-connected matroid and is a minor of H, so

min{|Z ∩ E(N)|, |W ∩ E(N)|} ≤ 1.

In particular, we may assume that

|Z ∩ E(N)| ≤ 1.  (1)

Now choose such a k-separation satisfying (1) so that |Z| is as large as possible. Note that, since |E(N)| ≥ 4, we must have that

|W ∩ E(N)| ≥ 3.  (2)

If Z is closed in both H and H^{∗}, then (4.3.5) follows. Thus, we may assume that there is an element w of W such that w is spanned by Z in H or H^{∗}. Hence r_{H}(Z) = r_{H}(Z ∪ w) or r_{H^{∗}}(Z) = r_{H^{∗}}(Z ∪ w), and so

r_{H}(Z) + r_{H^{∗}}(Z) − |Z| ≥ r_{H}(Z ∪ w) + r_{H^{∗}}(Z ∪ w) − |Z ∪ w|.

Thus {Z ∪ w, W − w} is a j-separation of H for some j in {1, 2}. Again, since N is 3-connected, we have min{|(Z ∪ w) ∩ E(N)|, |(W − w) ∩ E(N)|} ≤ 1. It follows by (2) that |(Z ∪ w) ∩ E(N)| ≤ 1. Therefore {Z ∪ w, W − w} contradicts the choice of {Z, W } and we conclude that (4.3.5) holds.

4.3.6. If T^{∗} is a triad of M such that e ∈ T^{∗} − cl(A) and T^{∗} − e ⊆ cl(A), then T^{∗} − e ⊆ A.

To see this, note that T^{∗} ∩ cl(A) = T^{∗} − e. Hence |T^{∗} ∩ cl(A)| = 2 and (4.3.6) follows by hypothesis (b).

4.3.7. If T is a triangle of M such that T − cl(A) is non-empty, then T ∩ cl(A) contains exactly one element, a_{T}, and a_{T} ∈ A.

As T − cl(A) is non-empty but M\cl(A) has no triangles, it follows that 1 ≤ |T − cl(A)| ≤ 2. But cl(A) does not span T, so |T − cl(A)| = 2. Let e be an element of T − cl(A). By (xi) of Lemma 4.1, there is a triad T^{∗} of M such that e ∈ T^{∗} and T^{∗} − e ⊆ cl(A). By (4.3.6), T^{∗} − e ⊆ A. By orthogonality, T^{∗} ∩ T ≠ {e}. Thus the unique element a_{T} of T ∩ (T^{∗} − e) must belong to A, and (4.3.7) holds.

Recall that N = (M/a)\X/Y. To establish Lemma 4.3, we shall show that both X and Y must be small. We begin by considering X.

4.4. Lemma. (i) If x ∈ X, then there is a triad T_{x}^{∗} of M such that T_{x}^{∗} =

{x, a, b} for some b ∈ A. (ii) |X| ≤ 1.

Proof. The proof of Lemma 4.4(i) is long and will be divided into a number of steps. We shall argue by contradiction. Thus suppose that (i) fails, that is, T_{x}^{∗} does not exist for some x in X. Let H = M\x and observe that H is not 3-connected since (M, A) is a minimal pair. Therefore H has a 2-separation {Z, W } satisfying (4.3.5). Hence Z ∩ E(N) has at most one element. Moreover, when this element exists, we shall denote it by n. It is not difficult to see that

4.4.1. Z ∩ A ⊆ {a, n}, where n may not exist.

Next we show that 4.4.2. A ∪ W is a spanning set of M.

Suppose that W ∪ A does not span M. Then there is a cocircuit D of M that avoids cl(A ∪ W). Since D must also avoid cl(A), Lemma 4.1(ii) implies that every element of D is essential. Thus, by Theorem 2.7, M has two distinct triangles T_{1} and T_{2} meeting D. By (4.3.7), each T_{i} contains a unique element a_{T_{i}} of cl(A) and a_{T_{i}} ∈ A. Moreover, by Lemma 4.1(ix), a_{T_{1}} ≠ a_{T_{2}}. But, for each i, we have T_{i} − a_{T_{i}} ⊆ D. Moreover, D ⊆ Z since D avoids cl(W). Since, by (4.3.5), Z is closed in M\x, it follows that a_{T_{i}} ∈ Z for each i. Hence, by (4.4.1), {a_{T_{1}}, a_{T_{2}}} ⊆ Z ∩ A ⊆ {a, n}. Therefore a = a_{T_{j}} for some j, so a is in a triangle; a contradiction to the hypothesis.

4.4.3. 2 ≤ r(Z) ≤ 3. Moreover, if r(Z) = 3, then n exists and is in A, and both a and n belong to Z and are coloops of M|(W ∪ {a, n}); and if a ∈ W and r(Z) = 2, then n exists and is in A and n is a coloop of M|(W ∪ n).

By (4.4.1), W ∪ A ⊆ W ∪ {a, n} where n may not exist. As {Z, W } is a 2separation of M\x, we have min{|Z|, |W |} ≥ 2 and r(Z) + r(W) = r(M) + 1. But M\x is simple, so

2 ≤ r(Z) = r(M) − r(W) + 1.  (3)

Moreover, by (4.4.2),

r(M) = r(W ∪ A) = r(W ∪ (A − W)) ≤ r(W) + |A − W |.

Hence

r(W ∪ A) − r(W) = r(M) − r(W) ≤ |A − W |.  (4)

Substituting for r(M) − r(W) into (3), we get

2 ≤ r(Z) ≤ |A − W | + 1.  (5)

Since A − W ⊆ {a, n}, where n may not exist, we deduce that 2 ≤ r(Z) ≤ 3. Moreover, if r(Z) = 3, then |A − W | = 2 and equality holds in (4). Hence n exists, both a and n are in Z, and both are coloops of M|(W ∪{a, n}). On the other hand, if a ∈ W, then |A − W | = 1, so n exists and equality holds throughout both (5) and (4). Thus r(Z) = 2, and n is a coloop of M|(W ∪ n).

4.4.4. If |Z| ≥ r(Z) + 1, then (Z − A) ∩ cl(A) is empty, and n exists and is in A.

Suppose first that r(Z) = 2. Then M|Z is isomorphic to U_{2,|Z|}. As a does not belong to a triangle, it follows that a ∈ W. Hence, by (4.4.3), n exists and is in A. Thus, by (4.4.1), Z − A = Z − n. Now suppose that A spans an element z of Z − n. Then {n, z} ⊆ cl(A) and A spans Z because {n, z} is a basis for Z. As cl(A)∩Y = ∅ by (4.3.1), Z ∩ Y = ∅. But Z − n avoids E(N). Hence Z − n ⊆ X. Thus N is a minor of M\(Z − n) which equals M|(W ∪ n). But n is a coloop of the last matroid by (4.4.3), so n is a coloop of the 3-connected matroid N; a contradiction. We conclude that A cannot span any element of Z − A, and so (Z − A) ∩ cl(A) = ∅ when r(Z) = 2.

We may now assume that r(Z) ≥ 3. Then, by (4.4.3), r(Z) = 3, n exists, and a and n both belong to Z ∩ A. Thus, by (4.4.1), Z − A = Z − {a, n}. Suppose that A spans an element z of Z − {a, n}. Then {a, n, z} ⊆ cl(A) and A spans Z because {a, n, z} is a basis for Z, since, by hypothesis, a does not belong to a triangle of M. As cl(A) ∩ Y = ∅ by (4.3.1), Z ∩ Y = ∅. But Z − {a, n} avoids E(N) so Z−{a, n} ⊆ X. Thus N is a minor of M\(Z−{a, n}), which equals M|(W ∪{a, n}). Since n is a coloop in the last matroid by (4.4.3), n is a coloop of N; a contradiction. Hence A cannot span any element of Z − A and so (Z − A) ∩ cl(A) = ∅.

4.4.5. r(Z) = |Z|.

Suppose that |Z| ≥ r(Z) + 1. Then M|Z has a circuit, C. Observe that C − A = C −{a, n} since, by (4.4.4), n exists and belongs to A and by (4.4.1), Z ∩A ⊆ {a, n}. Now |C − {a, n}| ≥ 2, otherwise {a, n} ⊆ C and |C| = 3 which is contrary to the fact that a does not belong to a triangle. Let z_{1} and z_{2} be distinct elements of C − A, and suppose that z ∈ {z_{1}, z_{2}}. Then z ∈ Z − A, so, by (4.4.4), z ∉ cl(A). Moreover, by (xi) of Lemma 4.1, M has a triad T^{∗} that contains z and meets cl(A) in two elements. By (4.3.6), T^{∗} must meet A in two elements. By orthogonality, |T^{∗} ∩ C| ≥ 2. Hence |T^{∗} − C| ≤ 1 and so T^{∗} ⊆ Z by (4.3.5). Thus T^{∗} ∩ A ⊆ Z ∩ A ⊆ {a, n} by (4.4.1). Hence T^{∗} = {z, a, n}. In particular, the triads {z_{1}, a, n} and {z_{2}, a, n} contradict (vi) of Lemma 4.1.

Next we complete the proof of the first part of Lemma 4.4 by showing that T_{x}^{∗} exists, thereby obtaining a contradiction since we have assumed that T_{x}^{∗} does not exist.

4.4.6. T_{x}^{∗} exists.

Suppose first that x ∈ X − cl(A). Then, by (xi) of Lemma 4.1, there is a triad T^{∗} of M such that T^{∗} − x ⊆ cl(A) and hence, by (4.3.6), T^{∗} − x ⊆ A. If a ∈ T^{∗}, we can take T^{∗} = T_{x}^{∗} and (4.4.6) holds. Thus we may assume that a ∉ T^{∗}. Then T^{∗} −x is a 2-cocircuit of M\x/a. As N is a minor of M\x/a and T^{∗} −x ⊆ cl(A)−a, the cocircuit T^{∗} − x contradicts (4.3.4). We conclude that, for every element x of X − cl(A), the triad T_{x}^{∗} exists.

Now suppose that x ∈ cl(A) − A. By (4.4.5), r(Z) = |Z|. As {Z, W } is a 2separation for M\x, we have, by Lemma 2.4, that if z and z′ are distinct elements of Z, then {x, z, z′} is a cocircuit of M. But x ∈ {x, z, z′} ∩ (cl(A) − A), so, by Lemma 2.5, |{x, z, z′} ∩ cl(A)| ≥ 2. Hence, by hypothesis (b), |{x, z, z′} ∩ A| ≥ 2. As x ∉ A, it follows that both z and z′ belong to A. Since these two elements were arbitrarily chosen in Z, it follows that Z ⊆ A. Thus Z ∩ A = Z. By (4.4.1), Z ∩ A ⊆ {a, n} and hence Z = {a, n} since |Z| ≥ 2. In this case, we can take T_{x}^{∗} = {x, a, n} thereby completing the proof of (4.4.6) and hence that of Lemma 4.4(i).

To prove the second part of the lemma, we shall argue by contradiction. Suppose that x and x′ are different elements of X. By (i), the triads T_{x}^{∗} and T_{x′}^{∗} both exist. Let T_{x}^{∗} = {a, x, b} and T_{x′}^{∗} = {a, x′, b′} be as in Lemma 4.4. Thus {b, b′} ⊆ A.

We prove next that b ≠ b′. Assume the contrary. Then, by (vi) of Lemma 4.1, both x and x′ belong to cl(A). Moreover, M^{∗}|{a, x, x′, b} is isomorphic to U_{2,4}. Hence {x, x′, b} is a triad of M containing two elements of cl(A) but just one element of A; a contradiction to hypothesis (b). Thus b ≠ b′.

Observe that {b, b′, a} is contained in a series class or is a set of coloops of M\{x, x′}. Thus {b, b′} contains a cocircuit of (M/a)\{x, x′} which is contrary to (4.3.4).

Recall that N = (M/a)\X/Y. We have just shown that |X| ≤ 1. Next we consider |Y |.

4.5. Lemma. If y ∈ Y, then y belongs to a triangle of M.

Proof. Suppose that y is in no triangles of M. By (4.3.1), y ∉ cl(A). Thus, if H = M/y, then H has a 2-separation {Z, W }. By (4.3.5), we may assume that {Z, W } is chosen such that |Z ∩ E(N)| ≤ 1 and Z is closed in both H and H^{∗}. As before, if Z ∩ E(N) is non-empty, its unique element will be denoted by n. Thus

Z ∩ A ⊆ {a, n}.  (6)

As M is 3-connected and {Z, W } is a 2-separation for M/y, it follows that

y ∈ cl(Z) ∩ cl(W)  (7)

We shall prove next that

4.5.1. Z − X is independent in M/y\X.

We argue by contradiction. Thus assume that M/y has a circuit C that is contained in Z − X. By (4.3.2), it follows that C − (Y ∪ a) ≠ ∅. Hence

∅ ≠ C − (Y ∪ a) ⊆ Z − (X ∪ Y ∪ a) ⊆ Z ∩ E(N) ⊆ {n}.

Thus n exists and is in C, and C−(Y ∪a) = {n}. Hence n is a loop of (M/y)/(C−n) and y ∪ (C − n) ⊆ Y ∪ a so N is a minor of (M/y)/(C − n). Therefore n is a loop of N; a contradiction. We conclude that (4.5.1) holds.

Now, we shall prove that

4.5.2. |Z| ≥ 3 and X contains a unique element x. Moreover, x ∈ Z and, for every 2-element subset Z_{0} of Z − X, the set Z_{0} ∪ x is a triad of M.

The fact that |Z| ≥ 3 follows because Z spans y in M by (7), and y does not belong to a triangle. Now, by Lemma 4.4, |X| ≤ 1. Moreover, since |Z ∩ E(N)| ≤ 1 and |E(N)| ≥ 4, we have

|W | ≥ |E(N) − Z| ≥ |E(N)| − 1 ≥ 3.

Thus |W − X| ≥ 2 and, since |Z| ≥ 3, we also have that |Z − X| ≥ 2. Hence {Z − X, W − X} is a 2-separation for M/y\X. Therefore, by (4.5.1) and Lemma 2.4, if Z_{0} is a 2-element subset of Z − X, then Z_{0} contains a cocircuit of M/y\X. Thus Z_{0} ∪ X contains a cocircuit of M/y and hence of M. But every cocircuit of M has at least three elements, so Z_{0} ∪ X is a cocircuit of M and |X| = 1 since, by Lemma 4.4, |X| ≤ 1. Moreover, X ⊆ Z since Z is closed in H^{∗}.

Now, we shall show that

4.5.3. |Z| = 3.

Suppose that |Z| ≥ 4. By (4.5.2), there is a unique element x in X, and M^{∗}|Z is isomorphic to U_{2,|Z|}. If x ∉ cl(A), it follows that M has two triads that contradict (vi) of Lemma 4.1. Thus x ∈ cl(A). Now let Z_{0} be a 2-element subset of Z − x. By (4.5.2), x ∪ Z_{0} is a triad of M. Since x ∈ cl(A) − A, it follows by Lemma 2.5 that |(x ∪ Z_{0}) ∩ cl(A)| ≥ 2. Thus, by hypothesis (b), |(x ∪ Z_{0}) ∩ A| ≥ 2. As x ∉ A, it follows that Z_{0} ⊆ A. As Z_{0} was chosen arbitrarily, we deduce that Z − x ⊆ A. Thus Z − x = Z ∩ A. But, by (6), Z ∩ A ⊆ {a, n}. Thus 3 ≤ |Z − x| = |Z ∩ A| ≤ 2; a contradiction. Hence (4.5.3) holds.

Next we prove the following.

4.5.4. Z ∪ y is a circuit of M, the element n exists and is in A, and Z equals {x, a, n} and is a triad of M.

As Z spans y by (7), it follows that Z ∪y is a circuit of M, since y does not belong to a triangle and |Z| = 3. By Lemma 4.4, there is a triad T_{x}^{∗} of M such that x ∈ T_{x}^{∗} and T_{x}^{∗} − x ⊆ A. By orthogonality, since x ∈ Z, it follows that |T_{x}^{∗} ∩ (Z ∪ y)| ≥ 2. As y ∉ A, it follows that T_{x}^{∗} is a triad of H, which equals M/y. Since Z is closed in H^{∗}, we deduce that T_{x}^{∗} ⊆ Z because 1 ≥ |T_{x}^{∗} − (Z ∪ y)| = |T_{x}^{∗} − Z|. Hence T_{x}^{∗} = Z. Thus T_{x}^{∗} − x = T_{x}^{∗} ∩ A = Z ∩ A ⊆ {a, n}, by (6). Hence n exists and is in A, and T_{x}^{∗} = {a, n, x}. We conclude that (4.5.4) holds.

Now y ∉ cl(A) by (4.3.1). Thus, by (xi) of Lemma 4.1, there is a triad T^{∗} of M such that y ∈ T^{∗} and T^{∗} − y ⊆ cl(A). By (4.5.4), Z is also a triad of M and Z ∪ y is a circuit of M. By (vi) of Lemma 4.1, |Z ∩ T^{∗}| = 1. Moreover, M/x is not 3-connected since x ∉ cl(A) otherwise (Z ∪ y) − cl(A) = {y}, which is contrary to (4.3.1). Thus we may apply the dual of Lemma 2.6 to M to deduce that x is in some triangle T of M. By orthogonality, |T ∩ Z| ≥ 2 and hence |T − Z| ≤ 1. As Z is closed in M/y, it follows that T ⊆ Z. Hence T = Z and Z is both a triangle and a triad of the 3-connected matroid M. This contradiction implies that Lemma 4.5 holds.

4.6. Lemma. |Y | ≤ 1 and if |Y | = 1, then |X| = 1. Moreover, if Y = {y} and X = {x}, then there is an element a′ of A − a such that {x, a′, a} is a triad of M and {x, y, a′} is a triangle of M.

Proof. Suppose that y ∈ Y. By Lemma 4.5, M has a triangle T_{y} containing y. Now, by (4.3.1), y ∉ cl(A). Thus, by (4.3.7), T_{y} contains a unique element a′ of A. Moreover, a′ ≠ a since, by hypothesis, a is in no triangles. Hence a′ ∈ E(N). Let T_{y} = {y, a′, d} where d is some element of E(M). Then a′ and d are parallel in M/y. But N is a 3–connected minor of M/y and has no circuits of size less than three. Hence d ∉ E(N). Now d ∉ Y, otherwise a′ is a loop of N. Therefore d ∈ X. Thus, by Lemma 4.4, d is the unique element x of X, and M has a triad T_{x}^{∗} where T_{x}^{∗} = {x, a, b} for some b in A. Since x ∈ T_{x}^{∗} ∩ T_{y}, orthogonality implies that a′ = b as a is in no triangles. Thus T_{y} = {y, x, b}. But y was arbitrarily chosen in Y. Hence if y′ ∈ Y − y, then M|{y, y′, x, b} ≅ U_{2,4} and so {y, y′, x} is a triangle of M meeting the triad {x, a, b} in a single element, x; a contradiction. We conclude that Y − y is empty. Hence |Y | ≤ 1. Moreover, if |Y | = 1, say Y = {y}, then X = {x} and the required triangle and triad of M exist.

We are now ready to finish the proof of Lemma 4.3. We have N = (M/a)\X/Y. By Lemma 4.4, |X| ≤ 1, and, by Lemma 4.6, |Y | ≤ 1 with equality in the latter implying equality in the former. Hence we have three possibilities:

(i) |Y | = 0 = |X|; (ii) |Y | = 0 and |X| = 1; and (iii) |Y | = 1 = |X|.

The first possibility means that (i) of Lemma 4.3 holds. Moreover, by Lemma 4.4, the second possibility implies that (ii) of Lemma 4.3 holds. Thus it remains only to consider when the third possibility holds. Hence let Y = {y} and X = {x}. By Lemma 4.6, for some a′ in A−a, the matroid M has a triad T_{1}^{∗} and a triangle T such that T_{1}^{∗} = {a, x, a′} and T = {x, y, a′}. Since y ∉ cl(A), the triangle T implies that x ∉ cl(A). Moreover, by (xi) of Lemma 4.1 and (4.3.6), there is a triad T_{2}^{∗} of M containing y such that T_{2}^{∗} − y ⊆ A. Thus, by orthogonality with the triangle {x, y, a′}, it follows that T_{2}^{∗} = {a′, y, a′′} for some a′′ in A. Hence either T_{1}^{∗}, T, T_{2}^{∗} is a fan of M and (iii) of Lemma 4.3 holds, or T_{1}^{∗}, T, T_{2}^{∗} is not a fan of M. We may therefore assume that the latter possibility holds. Then, as |E(N)| ≥ 4 and so |E(M)| ≥ 7, there is a triangle T′ of M such that T′, T_{1}^{∗}, T, T_{2}^{∗} or T_{1}^{∗}, T, T_{2}^{∗}, T′ is a chain of M. The first case implies that a ∈ T′ and the second that a′′ ∈ T′. But M has no triangle containing a so a′′ ∈ T′. Hence T′ ∩ (T_{1}^{∗} ∪ T ∪ T_{2}^{∗}) = {y, a′′}. But N = M/a, y\x and so N has a circuit of size at most two containing a′′; a contradiction. This completes the proof of Lemma 4.3.

4.7. Lemma. Suppose that (M, A) is a minimal pair in which |A| ≥ 7. Let e be an element of E(M) − cl(A) that is in exactly h triads, T_{1}^{∗}, T_{2}^{∗}, …, T_{h}^{∗}, for some h ≥ 2. Suppose that T_{i}^{∗} ∩ A = {a_{i}, b_{i}} for all i. Then (M′, A′) is a minimal pair where M′ = M\e/{a_{1}, a_{2}, …, a_{h}} and A′ = A − {a_{1}, a_{2}, …, a_{h}}.

Proof. We note first that, by (vi) of Lemma 4.1, if i ≠ j, then T_{i}^{∗} ∩ T_{j}^{∗} = {e}. Moreover, by (i) of Lemma 4.1, M′ is 3-connected. Now M′ has a 3-connected minor N′ such that (N′, A′) is a minimal pair and N′|A′ = M′|A′. Then N′ = M′\X/Y for some independent set Y and coindependent set X. Clearly

4.7.1. X ∪ e is coindependent in M.

We shall complete the proof of the lemma by showing that both X and Y are empty. First we show that

4.7.2. r(A) + r(Y) = r(A ∪ Y).

By orthogonality, {a_{1}, a_{2}, …, a_{h}} is independent in M\e and hence in M. As Y is independent in M/{a_{1}, a_{2}, …, a_{h}}, it follows that {a_{1}, a_{2}, …, a_{h}} ∪ Y is independent in M. Thus, as N′|A′ = M′|A′, we have

r_{M/{a_{1},a_{2},... ,a_{h}}/Y} (A − {a_{1}, a_{2}, …, a_{h}}) = r_{M/{a_{1},a_{2},... ,a_{h}}}(A − {a_{1}, a_{2}, …, a_{h}}).

Therefore

r(A ∪ Y) − r({a_{1}, a_{2}, …, a_{h}} ∪ Y) = r(A) − r({a_{1}, a_{2}, …, a_{h}}),

so r(A ∪ Y) − h − |Y | = r(A) − h, and (4.7.2) follows.

Next we observe that

4.7.3. |E(N′)| ≥ 4.

To see this, we note that, since |A| ≥ 7 and

E(N′) ⊇ A − {a_{1}, a_{2}, …, a_{h}} ⊇ {b_{1}, b_{2}, …, b_{h}},

it follows that |A| − h ≥ h. Thus, if h ≤ 3, then |A| − h ≥ 4, and (4.7.3) holds; and if h ≥ 4, then |E(N′)| ≥ h ≥ 4, and again (4.7.3) holds.

Now M\(X ∪ e)/Y is obtained from the 3-connected matroid N′ by adding a_{i} in series with b_{i} for all i. Hence M\(X ∪ e)/Y is connected. Moreover, the following is an easy consequence of the fact that |E(N′)| ≥ 4.

4.7.4. Every 2-separation of M\(X ∪ e)/Y has some {a_{i}, b_{i}} as a part.

We show next that

4.7.5. T_{i}^{∗} is a triad of M\X/Y for every i.

Suppose that this fails for some i. Then, since T_{i}^{∗} is a triad of M and T_{i}^{∗} − e is a cocircuit of (M\X/Y)\e, it follows that either (i) T_{i}^{∗} is contained in a series class of M\X/Y; or (ii) e is a coloop of M\X/Y. But, since X ∪ e is coindependent in M, (ii) cannot occur. Likewise, (i) cannot occur, otherwise {b_{i}, e} is a cocircuit of M\X/Y, so b_{i} is a coloop of (M\X/Y)\e and hence of N′; a contradiction. We conclude that (4.7.5) holds.

Next we shall prove that

4.7.6. M\X/Y is 3-connected.

Since (M\X/Y)\e is connected and e is in a triad of M\X/Y, the last matroid is certainly connected. Assume that (4.7.6) fails and let {Z, W } be a partition of E((M\X/Y)\e) such that {Z ∪e, W } is a 2-separation of M\X/Y. Then {Z, W } is a 2-separation of (M\X/Y)\e unless |Z| = 1. But, in the exceptional case, Z ∪ e is either (i) a 2-element cocircuit, or (ii) a 2-element circuit of M\X/Y. The first case implies the contradiction that Z is a 1-element cocircuit of the connected matroid (M\X/Y)\e. In the second case, orthogonality and (4.7.5) imply that Z meets the h disjoint sets of the form T_{i}^{∗} − e. This is a contradiction since |Z| = 1 and h ≥ 2. We conclude that {Z, W } is indeed a 2-separation of (M\X/Y)\e.

By (4.7.4), one of Z and W is {a_{i}, b_{i}} for some i. Suppose first that Z = {a_{i}, b_{i}}. Then Z ∪ e = T_{i}^{∗} and, in M\X/Y, we have

1 = r(Z ∪e)+r(W)−r(M\X/Y) = r(Z ∪e)+r^{∗}(Z ∪e)−|Z ∪e| = r(Z ∪e)+2−3.

Hence r(Z ∪ e) = 2. But r(Z) = r({a_{i}, b_{i}}) = 2 since a_{i} and b_{i} are in series in (M\X/Y)\e. Thus e is in a circuit C of M\X/Y contained in T_{i}^{∗}. This contradicts orthogonality since, for j ≠ i, the triad T_{j}^{∗} of M\X/Y meets C in a single element. We conclude that Z ≠ {a_{i}, b_{i}}.

We may now assume that W = {a_{i}, b_{i}}. Since {Z ∪ e, W } is a 2-separation of M\X/Y, it follows that {a_{i}, b_{i}} is a circuit or a cocircuit of M\X/Y. But {a_{i}, b_{i}} is a proper subset of the triad T_{i}^{∗} of M\X/Y, so {a_{i}, b_{i}} is certainly not a cocircuit of M\X/Y. Moreover, if {a_{i}, b_{i}} is a circuit of M\X/Y, then b_{i} is a loop of (M\X/Y)\e/{a_{1}, a_{2}, …, a_{h}}, that is, of N′. This contradiction completes the proof of (4.7.6).

By (4.7.2), r(A ∪ Y) = r(A) + r(Y), so (M\X/Y)|A = M|A. Since (M, A) is a minimal pair, it follows that X = Y = ∅. Hence N′ = M′ and so (M′, A′) is a minimal pair.

5. Proofs of the main theorems

Theorems 1.5 and 1.6 can be combined into the following result.

5.1. Theorem. If (M, A) is a minimal pair, then

|E(M)| ≤ |A| + λ_{1}(A, M) + λ_{2}(A, M) + min{λ_{3}(A, M), r(M) − r_{M}(A)} − α(A, M),

where

α(A, M) = \{ \begin{matrix}0, & when A is a circuit of M \\ 1, & when A is not a circuit \end{matrix}

This theorem will be derived from two propositions. The first of these, which is stated and proved below, gives the structure of a minimal counterexample to the theorem; the second, which was proved in an earlier paper [6], will be stated following the proof of the first.

5.2. Proposition. Let (M, A) be a minimal pair that is a counterexample to Theorem 5.1 and is chosen so that

(|E(M)|, −|A|)

is lexicographically minimal among such counterexamples. Then every element of E(M)−cl(A) belongs to some type-2 fan of length three in which the rim is contained in a 4-circuit of M|A and the spokes are contained in E(M) − cl(A).

Proof. Suppose that (M, A) does not satisfy the proposition. Then, clearly,

E(M) − cl(A) ≠ ∅.  (8)

Moreover, by (iii) of Lemma 4.1,

|A| ≥ 3.  (9)

The rest of the proof of the proposition will be broken up into a sequence of lemmas, the first of which is as follows.

5.3. Lemma. M is neither a wheel having rim cl(A) nor a whirl having rim A.

Proof. Suppose that M is the rank-n whirl having rim A. Then A is independent and

\begin{matrix}|A| + λ_{1}(A, M) + λ_{2}(A, M) \\ + min\{λ_{3}(A, M), r(M) − r_{M}(A)\} − α(A, M) = 3|A| − 1 = 3n − 1. \end{matrix}

But (M, A) is a counterexample to Theorem 5.1 and |E(M)| = 2n, so 2n > 3n − 1; a contradiction.

Next suppose that M is the rank-n wheel having rim cl(A) but A ≠ cl(A). Then A = cl(A) − a for some element a, so A is independent. Again, we have that

\begin{matrix}|A| + λ_{1}(A, M) + λ_{2}(A, M) \\ + min\{λ_{3}(A, M), r(M) − r_{M}(A)\} − α(A, M) = 3|A| − 1 = 3n − 4. \end{matrix}

But |E(M)| = 2n and (M, A) is a counterexample to Theorem 5.1. Thus 2n > 3n−4 so n ≤ 3. Hence |A| = n − 1 ≤ 2; a contradiction to (9).

Finally, suppose that M is the rank-n wheel and A is its rim. In this case, n ≥ 4, otherwise n = 3 and A is a 3-element circuit so (M|A, A) is a minimal pair; a contradiction. Now λ_{1}(A, M) = 1, λ_{2}(A, M) = n − 2, λ_{3}(A, M) = n − 3, r(M) − r(A) = 1, and α(A, M) = 0. Thus

2n = |E(M)| > n + 1 + (n − 2) + 1 − 0.

This contradiction completes the proof of Lemma 5.3.

In several of the lemmas below, we shall replace the minimal pair (M, A) by another minimal pair (M′, A′) such that (|E(M′)|, −|A′|) is lexicographically less than (|E(M)|, −|A|). Thus (M′, A′) must satisfy the conclusion of Theorem 5.1 although (M, A) does not. Hence

\begin{matrix}|A| + λ_{1}(A, M) + λ_{2}(A, M) \\ + min\{λ_{3}(A, M), r(M) − r_{M}(A)\} − α(A, M) − |E(M)| < 0 \end{matrix}

and

\begin{matrix}|A′| + λ_{1}(A′, M′) + λ_{2}(A′, M′) \\ + min\{λ_{3}(A′, M′), r(M′) − r_{M′}(A′)\} − α(A′, M′) − |E(M′)| ≥ 0. \end{matrix}

On taking the difference of these two inequalities, we get

δ_{A} + δ_{1} + δ_{2} + δ_{m} − δ_{α} − δ_{E} < 0,  (10)

where

δ_{A} = |A| − |A′|,
δ_{1} = λ_{1}(A, M) − λ_{1}(A′, M′),
δ_{2} = λ_{2}(A, M) − λ_{2}(A′, M′),
δ_{m} = min{λ_{3}(A, M), r(M) − r_{M}(A)} − min{λ_{3}(A′, M′), r(M′) − r_{M′}(A′)},
δ_{α} = α(A, M) − α(A′, M′),
δ_{E} = |E(M)| − |E(M′)|.

Hence we shall arrive at a contradiction whenever (10) is not satisfied. To deal with δ_{m}, we define two other differences:

δ_{3} = λ_{3}(A, M) − λ_{3}(A′, M′),
δ_{r} = [r(M) − r_{M}(A)] − [r(M′) − r_{M′}(A′)].

The elementary proof of the next lemma is omitted.

5.4. Lemma. (i) If δ_{r} or δ_{3} is zero, then δ_{m} ≥ min{δ_{r}, δ_{3}}. (ii) If δ_{r} = δ_{3}, then δ_{m} = δ_{r} = δ_{3}.

5.5. Lemma. Every triangle of M that meets E(M) − cl(A) contains an element of cl(A).

Proof. Suppose that T is a triangle of M that avoids cl(A). By (viii) of Lemma 4.1, there is a triad that meets T in exactly two elements and contains some element a of A. Then, by Lemma 4.2, if M′ = M/T and A′ = A − a, then (M′, A′) is a minimal pair and

(M/T)|(A − a) = M|(A − a).

As |E(M′)| < |E(M)|, the minimal pair (M′, A′) satisfies Theorem 5.1. Hence (10) holds. We shall now consider each individual difference in (10). Clearly

δ_{A} = 1 and δ_{E} = 3.

Next we note that, since (M/T)|(A − a) = M|(A − a) and a is a coloop of M|A, we have

δ_{1} = δ_{2} = 1 and δ_{3} = 0.

Now r(M′) = r(M) − 2 and r_{M′}(A′) = r_{M}(A − a) = r_{M}(A) − 1. It follows that δ_{r} = 1 and hence, by Lemma 5.4,

δ_{m} ≥ 0.

Finally, (viii) of Lemma 4.1 implies that M|A has at least three coloops including a, and therefore

δ_{α} = 0.

On combining the above differences, we have

δ_{A} + δ_{1} + δ_{2} + δ_{m} − δ_{α} − δ_{E} ≥ 1 + 1 + 1 + 0 − 0 − 3 = 0.

This contradiction to (10) completes the proof of the lemma.

5.6. Lemma. If T^{∗} is a triad of M such that |T^{∗} ∩ cl(A)| ≥ 2, then |T^{∗} ∩ A| ≥ 2.

Proof. Suppose that |T^{∗} ∩A| ≤ 1. By Lemma 2.5, T^{∗} ∩A = {a} for some a. Choose e in (T^{∗} ∩ cl(A)) − A. Let M′ = M and A′ = A ∪ e. Clearly (M′, A′) is a minimal pair. Observe that the connected component N_{e} of M|(A ∪ e) that contains e must also contain a. Moreover, a is a coloop of N_{e}\e. Let l be the number of coloops of N_{e}\e that are not coloops of N_{e}. Then l ≥ 1. By Lemma 2.9(i) of [6], we have that

δ_{1} + δ_{2} ≥ l.

Observe also that

δ_{A} = −1, δ_{E} = 0, and δ_{r} = 0,

where the last of these holds because A spans e.

Now consider a series class S of M|A. Its contribution to λ_{3}(A, M) is max{0, |S|− 3}. In M|(A ∪ e), there is a partition {S_{1}, S_{2}, …, S_{k}} of S such that each S_{i} is a series class of M|(A∪e). The total contribution of these series classes to λ_{3}(A∪e, M) is

∑_{i=1}^{k} max{0, |S_{i}| − 3},

which clearly does not exceed max{0, |S| − 3}. The only non-trivial series class of M|(A ∪ e) that is not contained in a non-trivial series class of M|A is the one that contains e and the set of l elements that are coloops of N_{e}\e but not of N_{e}. Its contribution to λ_{3}(A ∪ e, M) is max{0, l − 2}. We conclude that

δ_{3} ≥ − max{0, l − 2} = min{0, 2 − l}

and, since δ_{r} = 0, Lemma 5.4 implies that

δ_{m} ≥ min{0, 2 − l}.

Thus

δ_{A} + (δ_{1} + δ_{2}) + δ_{m} − δ_{E} ≥ −1 + l + min{0, 2 − l} − 0.

By (10), we must have that δ_{α} > l − 1 + min{0, 2 − l}. Hence

δ_{α} > min{l − 1, 1}.

But δ_{α} ≤ 1 and l ≥ 1, so δ_{α} = 1 and l − 1 = 0. The first of these implies that A ∪ e is a circuit of M. Hence N_{e} = M|(A ∪ e) and A equals the set of coloops of N_{e}\e that are not coloops of N_{e}. Thus l = |A| ≥ 3, by (9); a contradiction.

The proof of Lemma 5.8 will use the following result of Oxley and Wu [11, Lemma 2.4].

5.7. Lemma. For some n ≥ 2, let {e_{1}, e_{2}, …, e_{n}} and {f_{1}, f_{2}, …, f_{n}} be disjoint subsets of the ground set of a 3-connected matroid N. Suppose that, for all i in {1, 2, …, n − 1} and all j in {1, 2, …, n}, {e_{i}, f_{i}, e_{i+1}} is a triangle and {f_{j}, e_{j+1}, f_{j+1}} is a triad, where all subscripts are read modulo n. Then N is isomorphic to a wheel or whirl of rank n.

5.8. Lemma. Let f be an element of E(M) − cl(A). Suppose that either

(i) f is in a chain with at least three links such that all the spokes of this chain are in E(M) − cl(A) and the rim of this chain is contained in cl(A); or

(ii) f is in a unique triad of M but is in no triangles. Then f is in a type-2 fan of length three in which the rim is a series class of M|A and the spokes are contained in E(M) − cl(A).

Proof. We shall show first that, in each case, there are elements a of A and e of E(M) − cl(A) such that M/a\e has a minimal 3-connected minor M′ for which M′|A′ = (M/a)|A′ where A′ = A − a and either

(a) M′ = M/a\e where {a, e} is contained in a triad of M; or

(b) M′ = M/a\e/e′ for some element e′ of E(M) − cl(A) such that f ∈ {e, e′}. Moreover, for some elements a_{1} and a_{2} of A, the set {e, a_{1}, e′} is a triangle, and {a, e, a_{1}}, {e, a_{1}, e′}, {a_{1}, e′, a_{2}} is a fan of M.

Suppose that (ii) occurs and let T^{∗} be a triad containing f. Then T^{∗} − f meets A, otherwise, by Lemma 4.1(v), |T^{∗} − cl(A)| ≤ 1 in which case, by Lemma 5.6, |T^{∗} ∩ A| ≥ 2; a contradiction. Let T^{∗} − f = {a, g} where a ∈ A. Now suppose that a is in a triangle of M. Then, since this triangle cannot contain f, it must contain g. But, in that case, the cosimplification of M\f is not 3-connected, contradicting Lemma 4.1(i). We conclude that a is in no triangles of M.

We are aiming to apply Lemma 4.3 to M. We know, by Lemmas 5.5 and 5.6, that hypotheses (a) and (b) of that lemma hold and that a is in no triangles of M. Now consider M/a. It must be 3-connected otherwise neither M/a nor M/f is 3-connected and the dual of Tutte’s triangle lemma [9, Lemma 8.4.9] implies that a is in a triangle; a contradiction. Next consider M\f. Since f is in no triangles, the simplification of M/f equals M/f and so is not 3-connected. Thus the cosimplification of M\f is 3-connected. Since T is the unique triad of M containing f, this cosimplification is M\f/a. Thus M/a\f is 3-connected. Therefore there is a minimal 3-connected minor M′ of M/a for which M′|(A − a) = (M/a)|(A − a) such that M′ is a minor of M/a\f. Then Lemma 4.3 and the fact that f is in no triangles imply that M′ = (M/a)\f. We conclude that if (ii) occurs, then (a) holds with e = f.

Next suppose that (i) holds, and take a maximal such chain T_{1}, T_{2}, …, T_{k} of M. Then k ≥ 3. Assume that there is a set T_{k+1} such that T_{2}, T_{3}, …, T_{k+1} is a chain. Let T_{i} = {e_{i}, e_{i+1}, e_{i+2}} for all i. Suppose first that T_{1}, T_{2}, …, T_{k+1} is a chain. By the choice of T_{1}, T_{2}, …, T_{k} , we deduce that either e_{k+3} is a spoke of T_{1}, T_{2}, …, T_{k+1} that is in cl(A), or e_{k+3} is a rim element of T_{1}, T_{2}, …, T_{k+1} that is not in cl(A). In the first case, T_{k+1} is a triangle containing two elements of cl(A), so e_{k+1} ∈ cl(A); a contradiction. In the second case, by Lemmas 5.5 and 4.1(xi), e_{k+2} belongs to a triad T_{0}^{∗} that meets cl(A) in two elements. By orthogonality with T_{k}, we must have that e_{k+1} ∈ T_{0}^{∗}, so, by Lemma 2.8, T_{0}^{∗} = T_{k+1}; a contradiction. We conclude that T_{1}, T_{2}, …, T_{k+1} is not a chain. Then e_{k+3} ∈ T_{1} ∪ T_{2} ∪ … ∪ T_{k} and it follows, by orthogonality, that e_{k+3} = e_{1} and that T_{1} and T_{k+1} are either both triangles or are both triads. Then, by Lemma 5.7, it follows that M is isomorphic to a wheel or whirl of rank k+2. Moreover, clearly this wheel or whirl has rim cl(A) and so we have a contradiction to Lemma 5.3. We conclude that there is no set T_{k+1} such that T_{2}, T_{3}, …, T_{k+1} is a chain. Similarly, there is no set T_{0} such that T_{0}, T_{1}, …, T_{k−1} is a chain. We conclude that T_{1}, T_{2}, …, T_{k} is a fan F. Moreover, since e_{1} and e_{k+2} are non-essential, it follows by Lemma 4.1(ix) that both T_{1} and T_{k} are triads of M.

Let {a, e, a_{1}} be the first link T^{∗} of F where a is the rim element of T^{∗} that is in no triangles, and e is the spoke of T^{∗}, the first spoke of F. By Lemma 5.6, {a, a_{1}} ⊆ A. By Lemma 4.1(i), the cosimplification of M\e is 3-connected. Suppose that this cosimplification is isomorphic to M\e/a, and let M′ be a minimal 3-connected minor of M\e/a for which M′|(A − a) = (M/a)|(A − a). Then Lemma 4.3 implies that (a) or (b) holds provided that, as we now show, f ∈ {e, e′}. Clearly e is in both the fan F and the fan {a, e, a_{1}}, {e, a_{1}, e′}, {a_{1}, e′, a_{2}} whose existence is asserted in Lemma 4.3(iii). By Theorem 2.2, if these fans are distinct, then F has five elements and has e as a rim element; a contradiction. Hence these two fans are the same, so f ∈ {e, e′}. We conclude that if the cosimplification of M\e is isomorphic to M\e/a, then (a) or (b) holds.

Now assume that the cosimplification of M\e is not isomorphic to M\e/a. Then M has a triad T_{1}^{∗} that contains e and is different from T^{∗}. It follows, using orthogonality, that T_{1}^{∗} must contain the first two spokes, e and e′, of F. Moreover, by Lemma 4.1(v), the other element a′ of T_{1}^{∗} is in A. By orthogonality again, F cannot have a third spoke. Hence e and e′ are the only two spokes of F, so f ∈ {e, e′}. Moreover, T^{∗} and T_{1}^{∗} are the only triads of M containing e, and the cosimplification of M\e is isomorphic to M\e/a/e′. We show next that

(M\e/a/e′)|(A − a) = (M/a)|(A − a).

This follows if (M/a)|[(A−a)∪e′] has e′ as a coloop. Assume the contrary. Then e′ is in the closure of A − a in M/a, so e′ is in the closure of A in M; a contradiction. Clearly M\e/a/e′ has a minimal 3-connected minor M′ for which M′|(A − a) = (M/a)|(A − a). Thus, by Lemma 4.3, we have that (a) or (b), and hence (b), holds.

We now know that (a) or (b) holds, and we examine the minimal pair (M′, A′). Since |E(M′)| < |E(M)|, Theorem 5.1 holds for (M′, A′). Clearly

δ_{A} = 1.

Moreover,

δ_{r} = \{ \begin{matrix}0, & when M′ = M/a\e; and \\ 1, & when M′ = M/a\e/e′. \end{matrix}

The rest of the argument will be broken into the following cases.

(I) a is a coloop of M|A; (II) a is in a series class of M|A. In case (I), since M′|A′ = (M/a)|A′,

δ_{1} = 1, δ_{2} = 1, and δ_{3} = 0.

Thus, by Lemma 5.4, δ_{m} ≥ 0. Hence, by (10),

1 + 1 + 1 + 0 ≤ δ_{A} + δ_{1} + δ_{2} + δ_{m} < δ_{α} + δ_{E}.

Thus, as δ_{α} ≤ 1 and δ_{E} ≤ 3, we deduce that δ_{α} = 1 and δ_{E} = 3. The first of these implies that A is not a circuit of M but A − a is a circuit of M′; and the second implies that (b) holds. By (b), M\e has {a, a_{1}} as a cocircuit. Thus M|A has {a, a_{1}} as a union of cocircuits. But a is a coloop of M|A. Hence so is a_{1}. This contradicts the fact that A − a is a circuit of (M|A)/a. Thus (I) cannot occur.

Now consider (II). In this case, M|A is obtained from M′|A′ by adding a in series to some element of A′. Thus M|A is isomorphic to the 2-sum of M′|A′ and a copy of U_{2,3}. Hence

δ_{1} = 0, δ_{2} = 1, and δ_{α} = 0.

Moreover, if S_{a} is the series class of M|A containing a, then

δ_{3} = \{ \begin{matrix}0, & when |S_{a}| ≤ 3; \\ 1, & when |S_{a}| ≥ 4. \end{matrix}

Since δ_{r} ∈ {0, 1}, it follows, by Lemma 5.4, that

δ_{m} ≥ 0.

Thus, by (10),

1 + 0 + 1 + 0 − 0 ≤ 1 + 0 + 1 + δ_{m} − 0 = δ_{A} + δ_{1} + δ_{2} + δ_{m} − δ_{α} < δ_{E}.

Since δ_{E} ≤ 3, we deduce that δ_{E} = 3 and δ_{m} = 0. Hence (b) holds, that is, M′ = M/a\e/e′, so δ_{r} = 1. Thus, by Lemma 5.4, δ_{3} ≠ 1 otherwise δ_{m} = 1. Hence δ_{3} = 0 so |S_{a}| ≤ 3. Therefore, by (b), S_{a} = {a, a_{1}, a_{2}} and the fan {a, e, a_{1}}, {e, a_{1}, e′}, {a_{1}, e′, a_{2}} satisfies all the conditions asserted in the lemma.

5.9. Lemma. |A| ≥ 7.

Proof. As E(M) − cl(A) ≠ ∅, there is a cocircuit D of M that avoids cl(A). Moreover, since (M, A) is a minimal pair, for all elements e of D, the matroid M/e is not 3-connected. Thus, by Theorem 2.7, M has two triangles T_{1} and T_{2} meeting D in distinct subsets. By Lemma 5.5, each T_{i} meets cl(A). Hence, by Lemma 4.1(ix), there is a unique element a_{T_{i}} in T_{i} ∩ cl(A) and there is a chain T_{1T_{i}}^{∗}, T_{i}, T_{2T_{i}}^{∗} whose rim A_{T_{i}} is contained in cl(A). Take an element f_{1} of (T_{1} − T_{2}) − cl(A). By Lemma 5.8, f_{1} is in a 5-element fan F′_{1} whose rim is a series class of M|A and all of whose spokes are in E(M) − cl(A). Clearly T_{2} − cl(A) has an element f_{2} that is not in F′_{1} and, by Lemma 5.8 again, f_{2} is in a 5-element fan F′_{2} whose rim is a series class of M|A.

The rims R_{1} and R_{2} of F′_{1} and F′_{2} are both series classes of M|A and, by Theorem 2.2, these rims are not equal. Hence R_{1} and R_{2} are disjoint and so |A| ≥ 6. We may now assume that |A| = 6 otherwise the lemma holds. But, in that case, M|A is the union of the two series classes R_{1} and R_{2}. Hence each R_{i} is a triangle of M|A. This is a contradiction as F′_{i} is a fan.

5.10. Lemma. An element e of E(M) − cl(A) that does not belong to a triangle of M belongs to exactly one triad.

Proof. The element e certainly belongs to at least one triad, otherwise, by Lemma 2.3, either M\e or M/e is 3-connected; a contradiction to the fact that (M, A) is a minimal pair. Now let T_{1}^{∗}, T_{2}^{∗}, …, T_{n}^{∗} be the triads of M that contain e and suppose that n ≥ 2. For all i, we must have that |T_{i}^{∗} −cl(A)| < 2, otherwise Tutte’s triangle lemma implies that e is in a triangle. Hence |T_{i}^{∗} ∩ cl(A)| ≥ 2 for all i and it follows, by Lemma 5.5, that |T_{i}^{∗} ∩ A| = 2. Let T_{i}^{∗} ∩ A = {a_{i}, b_{i}} for all i. Then, by Lemma 4.7, (M′, A′) is a minimal pair where M′ = M\e/{a_{1}, a_{2}, …, a_{n}} and A′ = A − {a_{1}, a_{2}, …, a_{n}}.

Clearly

δ_{A} = n and δ_{E} = n + 1.

Moreover, for each i, either a_{i} is in series with b_{i} in M|A, or a_{i} is a coloop of M|A. Without loss of generality, assume that the set of coloops of M|A in {a_{1}, a_{2}, …, a_{n}} is {a_{1}, a_{2}, …, a_{k}}. Then a matroid isomorphic to M|A can be obtained from M′|A′ in two stages: first take the direct sum of M′|A′ with the k coloops a_{1}, a_{2}, …, a_{k}; and then take the 2-sum of the resulting matroid with n − k copies of U_{2,3} using b_{k+1}, b_{k+2}, …, b_{n} as basepoints. Thus

δ_{1} = k ≥ 0 and δ_{2} = n.

As each series class of M′|A′ is contained in a series class of M|A, we have δ_{3} ≥ 0. Moreover, as δ_{r} is clearly zero, Lemma 5.4 implies that

δ_{m} ≥ 0.

Therefore, by (10), we obtain a contradiction unless

n + 0 + n + 0 ≤ δ_{A} + δ_{1} + δ_{2} + δ_{m} < δ_{E} + δ_{α} = (n + 1) + δ_{α}.

Thus 1 ≤ n − 1 < δ_{α} ≤ 1; a contradiction.

On combining Lemmas 5.8 and 5.10, we obtain the following.

5.11. Corollary. If f ∈ E(M) − cl(A), then f is in a type-2 fan of length three in which the rim is a series class of M|A and the spokes are contained in E(M)−cl(A). Moreover, two distinct such fans are disjoint.

Proof. Either f is in a triangle of M or not. In the first case, by Lemma 5.10, f is in a unique triad but no triangle and the first part of the corollary follows by Lemma 5.8. In the second case, by Lemma 5.5, f is in a triangle with some element of cl(A). Then, by Lemma 4.1(ix), f satisfies (i) of Lemma 5.8 and again the first part of the corollary follows by that lemma.

Now observe that the intersection of two distinct fans F_{1} and F_{2} satisfying the specified conditions is a subset of the intersection of their rims or the intersection of their sets of spokes. But each rim is a series class of M|A so the rims are either equal or disjoint. Thus if F_{1} meets F_{2}, then F_{1} and F_{2} have a common element that is essential in M. But this violates Theorem 2.2.

Now let T_{0}, T_{1}, T_{2} be a type-2 fan F of M where T_{0} = {a_{0}, e_{1}, a_{1}}, T_{1} = {e_{1}, a_{1}, e_{2}}, and T_{2} = {a_{1}, e_{2}, a_{2}} where {a_{0}, a_{1}, a_{2}} ⊆ cl(A) and {e_{1}, e_{2}}∩cl(A) = ∅. A chord of F is an element y such that R∪y is a circuit of M where R is the rim {a_{0}, a_{1}, a_{2}} of F. In view of the last corollary, to complete the proof of Proposition 5.2, it suffices to show that F has a chord that is contained in A.

5.12. Lemma. If y is a chord of F, then y is unique and y ∈ A.

Proof. If {y, a_{0}, a_{1}, a_{2}} and {y′, a_{0}, a_{1}, a_{2}} are circuits of M, then {y, y′, a_{0}, a_{2}} contains a circuit, which, by orthogonality, must be {y, y′}; a contradiction. Thus y is unique. Now assume that y ∉ A. Then M\y is not 3-connected. Let {X, Y } be a 2-separation of M\y and suppose, without loss of generality, that |X ∩ T_{1}| ≥ 2. Subject to this restriction, choose the 2-separation {X, Y } such that |X ∩ F | is maximum.

We now show that |Y | ≥ 3. Assume that |Y | = 2. As M is simple, Y must be a cocircuit of M\y, and so Y ∪ y is a triad T^{∗} of M. By orthogonality, T^{∗} ∩ R ≠ ∅. By Lemma 2.8, a_{1} ∉ T^{∗}. Hence we may assume that a_{0} ∈ T^{∗}. Because R is a series class of M|A, the unique element, z say, of T^{∗} − {y, a_{0}} must belong to A otherwise a_{0} is a coloop of M|A. Thus z and a_{0} are in series in M|A so z = a_{2}, and T^{∗} = {y, a_{0}, a_{2}}. By elimination and orthogonality, {a_{0}, e_{1}, e_{2}, a_{2}} is a cocircuit of M. Hence ({a_{0}, e_{1}, e_{2}, a_{2}} ∪ {y, a_{0}, a_{2}}) − a_{0} contains a cocircuit D of M. But M|A has a circuit containing {a_{0}, a_{1}, a_{2}} so, by orthogonality, D = {e_{1}, e_{2}, y}. This is a contradiction since |D ∩ (R ∪ y)| = 1. We conclude that |Y | ≥ 3.

Next we observe that, since X spans T_{1}, it follows that {X ∪ T_{1}, Y − T_{1}} is a 2-separation of M\y. By the choice of {X, Y }, we deduce that X ∪ T_{1} = X, so T_{1} ⊆ X. Thus X spans T_{0} in M^{∗}, so {X ∪ T_{0}, Y − T_{0}} is a 2-separation of M\y, which, as above, must equal {X, Y }. Thus T_{0} ⊆ X and, by symmetry, T_{2} ⊆ X. We conclude that F ⊆ X, so X spans y. This contradiction completes the proof that y ∈ A.

We may now assume that F has no chord otherwise the result follows.

5.13. Lemma. M/{a_{0}, a_{2}} is 3-connected.

Proof. As a_{0} ∈ T_{0} − T_{1} and T_{0}, T_{1}, T_{2} is a type-2 fan, a_{0} is non-essential so M/a_{0} is 3-connected. We show next that M/a_{0} has no triangle containing a_{2}. Assume that such a triangle T′ exists.

Suppose first that e_{2} ∈ T′. Then T′ = {a_{2}, e_{2}, e_{3}} for some e_{3}, which, since e_{2} ∉ cl(A), is not in cl(A). Thus either T′ or T′ ∪ a_{0} is a circuit of M. The first possibility contradicts the fact that T_{0}, T_{1}, T_{2} is a fan; the second contradicts orthogonality with the triad T_{0} since e_{3} ≠ e_{1} otherwise M/a_{0} has a line containing {a_{1}, a_{2}, e_{1}, e_{2}}.

We may now assume that e_{2} ∉ T′. Then, by orthogonality with T_{2}, we have T′ = {a_{2}, a_{1}, g} for some element g. By Lemma 2.8, T′ is not a triangle of M so T′ ∪ a_{0} is a circuit of M and hence g is a chord of M; a contradiction.

We conclude that there is indeed no triangle of M/a_{0} containing a_{2}. But the cosimplification of M/a_{0}\a_{2} is not 3-connected, so the simplification of M/a_{0}/a_{2}, which equals M/{a_{0}, a_{2}}, is 3-connected.

Now let A′ = A−{a_{0}, a_{2}} and let M′ be a 3-connected matroid such that M′|A′ = (M/{a_{0}, a_{2}})|A′ and (M′, A′) is a minimal pair. Then M′ = (M/{a_{0}, a_{2}})\X/Y for some sets X and Y.

5.14. Lemma. Y ∪ (X − cl(A)) ⊆ {e_{1}, e_{2}}.

Proof. Suppose that there is an element z in [Y ∪ (X − cl(A))] − {e_{1}, e_{2}}. We shall show that z ∉ cl(A). If not, then z ∈ Y ∩ cl(A) and

r(M′|A′) ≤ r((M/{a_{0}, a_{2}, z})|A′) = r((M/{a_{0}, a_{2}})|A′) − 1;

a contradiction. We conclude that we do indeed have that z ∉ cl(A). Thus z ∈ E(M) − (cl(A) ∪ F). Then, by Corollary 5.11, z is in a type-2 fan F′ of M of length three whose rim is a series class of M|A and such that F′ ⊆ E(M) − F. But M\z has a 2-cocircuit contained in A − {a_{0}, a_{2}} that remains a 2-cocircuit of M/{a_{0}, a_{2}}\X/Y. Now the last matroid is 3-connected of size at least five since |A| ≥ 7. Hence z ∉ X. On the other hand, if z ∈ Y, then M/z has a 2-circuit containing a spoke z′ of F′. Thus M′ is a minor of M/z\z′ and hence of M\z′. Again we obtain a contradiction.

5.15. Lemma. X ∩ cl(A) = ∅.

Proof. Suppose that X ∩ cl(A) ≠ ∅. Let H = M\(X ∩ cl(A)). Then H|A = M|A. As (M, A) is a minimal pair, it follows that H is not 3-connected. For some k in {1, 2}, let {Z, W } be a k-separation of H for which |Z ∩ T_{1}| ≥ 2 and |Z ∩ F | is maximum subject to this condition.

5.15.1. F ⊈ Z.

Assume the contrary. Then |Z| ≥ 5. But, by Lemma 5.14, E(H) − E(M′) ⊆ {a_{0}, a_{2}, e_{1}, e_{2}} ⊆ F. Thus Z ∩ E(M′) ⊇ Z − {a_{0}, a_{2}, e_{1}, e_{2}} ⊇ {a_{1}}. Since {Z ∩ E(M′), W } is not a 2-separation of M′, it follows that |Z ∩ E(M′)| ≤ 1. Hence Z − {a_{0}, a_{2}, e_{1}, e_{2}} = {a_{1}}, so Z = F.

Now a_{0}, a_{1}, and a_{2} are in series on M\{e_{1}, e_{2}} because F is a fan. These elements are also in series in M|A. Thus they are also in series in M|cl(A). Hence cl(A) is spanned by A − a_{0}, so cl(A) − a_{0} is spanned by A − a_{0}. But a_{1} and a_{2} are coloops of M|(cl(A) − a_{0}). Thus A − R spans cl(A) − R. Since F = Z, it follows that A − R ⊆ W. Hence W spans cl(A) − R. But cl(A) − R ⊇ cl(A) ∩ X, so W spans cl(A) ∩ X and hence {Z, W ∪ (X ∩ cl(A))} is a k-separation of M, a contradiction. Thus (5.15.1) holds.

5.15.2. |W | = 2 and W is a cocircuit of H.

Suppose that |W | ≥ 3. Then a minor modification of the argument given in the last paragraph of the proof of Lemma 5.12 establishes that F ⊆ Z. This contradiction to (5.15.1) implies that |W | ≤ 2. Then W consists of either one or two coloops of H, or a 2-cocircuit of H.

Suppose that W is a set of coloops of H. Then W ⊆ cl(A) since every element in E(M) − cl(A) belongs to a triangle of H. Orthogonality now implies that W ⊆ A. As W is a set of coloops of H, it is a set of coloops of M|A, so W ∩ R = ∅. Hence W is a set of coloops of M′. This contradiction completes the proof of (5.15.2).

5.15.3. W = {a_{0}, a_{2}}.

Since W is a cocircuit of M\(X ∩ cl(A)), it follows that M has a cocircuit D that contains W and is contained in W ∪ (X ∩ cl(A)). Hence D ⊆ W ∪ (cl(A) − A). As |D| ≥ 3, there is certainly an element of cl(A) − A in D.

Now W does not contain a cocircuit of M′, so W ∩ (Y ∪ {a_{0}, a_{2}}) ≠ ∅. Suppose that Y ∩ W ≠ ∅. Then, by Lemma 5.14, we may assume that {e_{1}} ⊆ Y ⊆ {e_{1}, e_{2}}. But Y ≠ {e_{1}, e_{2}} otherwise a_{1} is a loop of M/Y and hence of M′. Thus Y = {e_{1}}. Now, by orthogonality, since D meets cl(A) − A, it must also meet A. But the only element of D that can be in A is the unique element of of W − Y. Then, by orthogonality with T_{1}, this element must be a_{1}. Thus |W ∩T_{1}| = 2; a contradiction. We conclude that Y ∩ W = ∅.

We may now assume that a_{0} ∈ W. As D ∩ A ⊆ D ∩ W and D ∩ A contains a cocircuit of M|A, we deduce, since R is a series class of M|A, that D∩W = {a_{0}, a_{2}} and so (5.15.3) holds.

5.15.4. {e_{1}, e_{2}} is a cocircuit of H.

Since F is a fan of the 3-connected matroid M, the set {a_{0}, e_{1}, e_{2}, a_{2}} is a cocircuit of M. Therefore this set is a union of cocircuits of H. By (5.15.2) and (5.15.3), {a_{0}, a_{2}} is a cocircuit of H. Moreover, {e_{1}, a_{1}, e_{2}} is a triangle of H. Assume that {e_{1}, e_{2}} is not a cocircuit of H. Then, by orthogonality, {a_{0}, e_{1}, e_{2}} or {a_{2}, e_{1}, e_{2}} is a cocircuit of H. Thus H|A, which equals M|A, has {a_{0}} or {a_{2}} as a cocircuit. This contradiction finishes the proof of (5.15.4).

By (5.15.4), {{e_{1}, e_{2}}, E(H) − {e_{1}, e_{2}}} is a 2-separation of H and |{e_{1}, e_{2}} ∩ T_{1}| ≥ 2. Thus the triangle T_{1} implies that {{e_{1}, e_{2}, a_{1}}, E(H) − {e_{1}, e_{2}, a_{1}}} is a 2-separation of H. Moreover, for each i in {0, 2}, the triad T_{i} of M implies that {{e_{1}, e_{2}, a_{1}, a_{i}}, E(H)−{e_{1}, e_{2}, a_{1}, a_{i}}} is also a 2-separation of H unless E(H) = F. Assume that E(H) ≠ F. Then H has a 2-separation {Z, W } such that Z ⊇ {e_{1}, e_{2}, a_{1}, a_{0}} and |Z ∩ F | is maximum subject to this. Then Lemma 5.14 implies that W = {a_{0}, a_{2}}; a contradiction. We conclude that E(H) = F. Then, since T_{1} is a triangle of H, and {a_{0}, a_{2}} and {e_{1}, e_{2}} are cocircuits of H, we deduce that {a_{0}, a_{1}, a_{2}} is a triangle of H; a contradiction. We conclude that Lemma 5.15 holds.

Now, for the minimal pair (M′, A′), since X ∪ Y ⊆ {e_{1}, e_{2}}, we have δ_{E} ≤ 4. Clearly δ_{A} = 2. As M′|A′ = (M/{a_{0}, a_{2}})|A′ and {a_{0}, a_{1}, a_{2}} is a series class of M|A, we can obtain M|A by taking the 2-sum of M|A′ and a 4-circuit. Thus δ_{1} = 0, δ_{2} = 2, δ_{3} = 0, and δ_{α} = 0. Finally, it is clear that δ_{r} ≥ 0. Thus, by Lemma 5.4, δ_{m} ≥ 0. Hence, by (10),

2 + 0 + 2 + 0 ≤ δ_{A} + δ_{1} + δ_{2} + δ_{m} < δ_{α} + δ_{E} ≤ 0 + 4.

This contradiction completes the proof of Proposition 5.2.

Theorem 5.1 is quite straightforward to prove by combining Proposition 5.2 and the following technical proposition that was proved in [6].

5.16. Proposition. Let (M, A) be a minimal pair such that (i) M is not isomorphic to U_{1,3}; and (ii) every element of E(M) − cl(A) belongs to some type-2 fan of length three in

which the rim is contained in a 4-circuit of M|A and the spokes are contained in E(M) − cl(A).

Then

|E(M)| ≤ |A| + λ_{1}(A, M) + λ_{2}(A, M) − β(A, M),

where

β(A, M) = \{ \begin{matrix}1, & when A is a circuit of M or r(A) ≠ r(M); \\ 2, & when A is not a circuit of M and r(A) = r(M). \end{matrix}

Proof of Theorem 5.1. Assume that the theorem fails and choose a minimal pair (M, A) that is a counterexample and is chosen so that (|E(M)|, −|A|) is lexicographically minimal. Suppose first that M ≅ U_{1,3}. Then |A| = 3 and it is straightforward to check that (M, A) is not a counterexample to the theorem. Thus we may assume that M ≅ U̸_{1,3}. Moreover, by Proposition 5.2, (M, A) satisfies hypothesis (ii) of Proposition 5.16. Thus the latter proposition implies that

|E(M)| ≤ |A| + λ_{1}(A, M) + λ_{2}(A, M) − β(A, M).

As −α(A, M) ≥ −β(A, M) and min{λ_{3}(A, M), r(M) − r_{M}(A)} ≥ 0, it follows that

|E(M)| ≤ |A| + λ_{1}(A, M) + λ_{2}(A, M) + min{λ_{3}(A, M), r(M) − r_{M}(A)} − α(A, M).

But this is a contradiction since (M, A) was chosen to be a counterexample to Theorem 5.1. □

To conclude the paper, we now prove Theorem 1.4. Proof of Theorem 1.4. We shall prove that A is spanning. The theorem will then follow from [6, Theorem 1.1]. Suppose that E(M) − cl(A) is non-empty. Then it contains a cocircuit D of M. By Theorem 2.7, D must meet a triangle T of M. If T ∩ cl(A) is empty, then, by Lemma 4.1(viii), M has a triad that contains two elements of T and one of A, so M|A has a coloop; a contradiction. Thus T meets cl(A) so, by Lemma 4.1(ix), there is a chain T_{1T}^{∗} , T, T_{2T}^{∗} whose rim is contained in cl(A). Since M|A has no coloops, this rim is contained in a series class S of M|A. Since r(S) ≤ 2, it follows that S is a triangle of M. Thus if X = T_{1T}^{∗} ∪ T ∪ T_{2T}^{∗}, then

r(X) + r^{∗}(X) − |X| ≤ 3 + 3 − 5 = 1.

But M is 3-connected so |E(M) − X| ≤ 1 and it follows without difficulty that M is a rank-3 wheel having cl(A) as a triangle. Thus (M, A) is not a minimal pair; a contradiction. □

Acknowledgements The first author was partially supported by CNPq, CAPES, FINEP and PRONEX 107/97. The second author was partially supported by the National Security Agency.

References

[1] Bixby, R.E., A simple theorem on 3-connectivity, Linear Algebra Appl. 45 (1982), 123–126.

[2] Brylawski, T.H., Modular constructions for combinatorial geometries, Trans. Amer. Math. Soc. 203 (1975), 1–44.

[3] Cunningham, W.H., A combinatorial decomposition theory, Ph. D. thesis, University of Waterloo, 1973.

[4] Ding, G., Oporowski, B., Oxley, J. and Vertigan, D., Unavoidable minors of large 3-connected matroids, J. Combin. Theory Ser. B 71(1997), 244–293.

[5] Lemos, M., On 3-connected matroids, Discrete Math. 73 (1989), 273–283.

[6] Lemos, M. and Oxley, J., On the 3-connected matroids that are minimal having a fixed spanning restriction, submitted.

[7] Lemos, M. and Oxley, J., On size, circumference and circuit removal in 3-connected matroids, submitted.

[8] Oxley, J.G., On matroid connectivity, Quart. J. Math. Oxford Ser. (2) 32 (1981), 193–208.

[9] Oxley, J.G., Matroid theory, Oxford University Press, New York, 1992.

[10] Oxley, J. and Wu, H., A note on matroid connectivity, Discrete Math. 146 (1995), 321–324.

[11] Oxley, J. and Wu, H., On the structure of 3-connected matroids and graphs, submitted.

[12] Truemper, K., Partial matroid representations, Europ. J. Combin. 3 (1984), 377–394.

[13] Tutte, W.T., Connectivity in matroids, Canad. J. Math. 18 (1966), 1301–1324.

Departamento de Matemática, Universidade Federal de Pernambuco, Recife, Pernambuco 50740-540, Brazil

  E-mail address: manoel@dmat.ufpe.br

Department of Mathematics, Louisiana State University, Baton Rouge, Louisiana 70803–4918, USA

  E-mail address: oxley@math.lsu.edu

Department of Mathematics, University of Mississippi, University, Mississippi 38677, USA

  E-mail address: mmreid@hilbert.math.olemiss.edu