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

MANOEL LEMOS AND JAMES OXLEY

Abstract. Let N be a minor of a 3-connected matroid M and let M′ be a 3-connected minor of M that is minimal having N as a minor. This paper commences the study of the problem of finding a best-possible upper bound on |E(M′) − E(N)|. The main result solves this problem in the case that N and M have the same rank.

1. Introduction

Let C be a circuit of a 3-connected matroid M. What can be said about the size of a minimal 3-connected minor of M that maintains C as a circuit? Alternatively, if I is an independent set of M, can we give a sharp bound on the size of a minimal 3-connected minor of M that maintains I as an independent set? Both these questions are special cases of 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)|.

This paper solves this problem in the case that E(N) spans M. By building on the results in this paper and using some additional results, we solve the problem in general in [8]. We note here that, in our problem, M′ must have N itself as a restriction, that is, M′|E(N) = N; it does not suffice for M′ to have an isomorphic copy of N as a restriction. An obvious, and perhaps more natural, variant of the original problem is the following:

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

If N is 3-connected and we also insist that M′ ≠ N, then Truemper [13] showed that |E(M′) − E(N)| ≤ 3. Moreover, again when N is 3-connected, if M′ is also required to contain some fixed element e of E(M′) − E(N), Bixby and Coullard [2] showed that |E(M′) − E(N)| ≤ 4. If “3-connected” is replaced by “2-connected” throughout Problem 1.2, the resulting problem was solved by Lemos and Oxley [6]. They proved that if N has k components, then |E(M′) − E(N)| ≤ 2k − 2 unless N or its dual is free, in which case, |E(M′) − E(N)| ≤ k − 1.

In general, Problem 1.2 seems to be much more difficult than Problem 1.1 and we hope to return to the former in future work. We remark, however, that in certain special cases, such as when N is a circuit or a free matroid, or when N has the same rank as M, the problems coincide. Hence the solution to the special case of Problem 1.1 given here is also a solution to the corresponding case of Problem 1.2.

1991 Mathematics Subject Classification. 05B35.

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 [5]) 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 following theorem, the main result of the paper, solves both Problems 1.1 and 1.2 in the case that N and M have the same rank.

1.3. 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,

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

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

The cases when A spans M that are not covered by this theorem are easily solved: if A is empty and spanning, then M is the empty matroid; and if M ≅ U_{1,3}, then E(M) = A. It is natural to question the sharpness of the bounds in Theorem 1.3. When A is an n-circuit, if n ≤ 3, then E(M) = A and the appropriate bound holds; if n ≥ 4, then the bound in the theorem is attained by taking M to be a whirl of rank n − 1 and A to be any circuit containing the rim. When A is an independent set of size at least two, we shall show in [7] that the bound in Theorem 1.3 can be sharpened slightly; otherwise Theorem 1.3 is best-possible in the following strong sense.

1.4. Theorem. Let N be a simple matroid other than a circuit or an independent set and let E(N) = A. Then there is a 3-connected matroid M that is spanned by A such that M|A = N,

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

and M has no proper 3–connected minor M′ such that M′|A = N.

Theorems 1.3 and 1.4 will be proved in Sections 3 and 4, respectively. Whereas the proof of the latter is relatively straightforward, that of the former is long and complicated. Indeed, Theorem 1.3 will be deduced as a consequence of a more technical result, Proposition 3.1. This proposition actually proves more than is needed to obtain Theorem 1.3. The extra strength of the proposition will be used in [8] where Theorem 1.3 will be extended to the case in which the set A need not be spanning. The proof of Proposition 3.1 will require a number of preliminaries. These will be proved in Section 2.

2. Preliminaries

MINIMAL 3–CONNECTED MATROIDS HAVING A FIXED SPANNING RESTRICTION 3

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 notation and terminology. Although we will not repeat here most of the basic connectivity results from [9] that we will use, we do note the following important result of Bixby [1] (see also [9, Proposition 8.4.6]).

2.1. 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, this cosimplification of M\e is 3-connected, while, in the second case, the simplification of M/e is 3-connected.

For a matroid M, we shall use Λ_{2}(M), λ_{2}(M), and λ_{1}(M) as abbreviations for Λ_{2}(E(M), M), λ_{2}(E(M), M), and λ_{1}(E(M), M), respectively. It was noted in the introduction that Cunningham and Edmonds established that Λ_{2}(M) is unique up to isomorphism. More explicitly, Cunningham and Edmonds [5] proved the following result.

2.2. Theorem. Let M be a connected matroid. Then, for some positive integer k, there is a collection M_{1}, M_{2}, …, M_{k} of 3-connected matroids and a k-vertex tree T with edges labelled e_{1}, e_{2}, …, e_{k−1} and vertices labelled M_{1}, M_{2}, …, M_{k} such that

(i) each M_{i} is 3-connected or is a circuit or cocircuit; (ii) E(M_{1}) ∪ E(M_{2}) ∪ … ∪ E(M_{k}) = E(M) ∪ {e_{1}, e_{2}, …, e_{k}}; (iii) if the edge e_{i} joins the vertices M_{j_{1}} and M_{j_{2}}, then E(M_{j_{1}}) ∩ E(M_{j_{2}}) is {e_{i}}; (iv) if no edge joins the vertices M_{j_{1}} and M_{j_{2}}, then E(M_{j_{1}}) ∩ E(M_{j_{i}}) is empty;

(v) T does not have two adjacent vertices that are both labelled by circuits or that are both labelled by cocircuits.

Moreover, M is the matroid that labels the single vertex of the tree T/e_{1}, e_{2}, …, e_{k−1} at the conclusion of the following process: contract the edges e_{1}, e_{2}, …, e_{k−1} of T one by one in order; when e_{i} is contracted, its ends are identified and the vertex formed by this identification is labelled by the 2-sum of the matroids that previously labelled the ends of e_{i}. Furthermore, the tree T is unique to within relabelling of its edges.

We construct Λ_{2}(M) as follows. First let Λ_{2}(M) consist of all of the connected components of M. Then, for each such component, M′, find the unique tree T′ whose existence is guaranteed by the last theorem, and replace M′ in Λ_{2}(M) by the matroids that label the vertices of T′. Finally, observe that if a vertex M′′ of T′ corresponds to a circuit or cocircuit with n elements for some n ≥ 4, then M′′ can be obtained by a sequence of n − 3 2-sums from n − 2 copies of either U_{2,3} or U_{1,3}, respectively. The final step in the construction of Λ_{2}(M) is, for each n ≥ 4, to replace each M′′ that is an n-circuit or n-cocircuit by the n − 2 triangles or triads from which M′′ can be constructed by 2-sums.

When we refer to Λ_{2}(M), we note that not only do we know the distribution of isomorphism types in this set, but we also know the isomorphism type of the matroid M′_{e} containing an element e of M together with, if |E(M′_{e})| ≥ 4, the isomorphism types of the matroids that share elements with M′_{e}.

The proof of Proposition 3.1 will be an induction argument. In particular, we shall require detailed information about the behaviour of the functions λ_{1} and λ_{2} under single-element deletions and contractions. Much of this section will be devoted to obtaining such results. We begin with an elementary lemma on small values of λ_{2} whose straightforward proof is omitted.

2.3. Lemma. (i) If λ_{2}(N) = 0, then every connected component of N is isomorphic to a rank-one uniform matroid with at least three elements.

(ii) If λ_{2}(N) ≤ 1 and N has no parallel elements, then N is 3-connected.

2.4. Lemma. Let M be a connected matroid that is not isomorphic to U_{1,3} and suppose that M/f is disconnected. Then, up to isomorphism, Λ_{2}(M) can be obtained from Λ_{2}(M\f) by adjoining a copy of U_{1,3} whose ground set contains f. In particular,

λ_{2}(M) = λ_{2}(M\f).

Proof. Let {X, Y } be a 1-separation for M/f. Suppose first that min{|X|, |Y |} ≥ 2. Then M can be decomposed as the 2-sum of matroids N_{0}, N_{1}, and N_{2} such that E(N_{1}) = X ∪{e_{1}}, E(N_{2}) = Y ∪{e_{2}}, and N_{0} is isomorphic to U_{1,3} and has ground set {e_{1}, e_{2}, f}. But M\f is the 2-sum of matroids isomorphic to N_{1} and N_{2}, and, since N_{0} is not counted in λ_{2}(M), the result follows in this case.

We may now suppose that |X| = 1, say X = {x}. Note that we may also suppose that |Y | ≥ 2, otherwise M is isomorphic to U_{1,3}. Evidently f and x are parallel in M so M is the 2-sum of a copy of U_{1,3} having ground set containing {f, x} and a matroid isomorphic to M\f. Again we conclude that the result holds.

The next lemma follows immediately from the last lemma by duality.

2.5. Lemma. Let M be a connected matroid M that is not a triangle and f be an element of M such that M\f is disconnected. Then

λ_{2}(M/f) = λ_{2}(M) − 1.

Two 2-separations {X′, Y′} and {X′′, Y′′} of a connected matroid cross if all four of the sets X′ ∩ X′′, X′ ∩ Y′′, Y′ ∩ X′′, and X′′ ∩ Y′′ are non-empty. The next lemma describes the structure of a matroid that has such a pair of 2-separations.

2.6. Lemma. Let {X′, Y′} and {X′′, Y′′} be crossing 2-separations of a connected matroid K and let F(K) = {X′ ∩ X′′, X′ ∩ Y′′, X′′ ∩ Y′, X′′ ∩ Y′′}. Then, for each Z in F(K) with at least two elements, {Z, E(K) − Z} is a 2-separation of K, and K is the 2-sum with basepoint e_{Z} of two matroids, one of which, K_{Z}, has ground set Z ∪ e_{Z}. Moreover, there is a 4-element circuit or cocircuit J(K) with ground set {e_{Z} : Z ∈ F(K)}, where Z = {e_{z}} when |Z| = 1, and K can be obtained from J(K) by attaching, via 2-sums, all the matroids K_{Z} for which Z is a member of F(K) with more than one element.

Proof. As K is connected, we must have that

r(X′) + r(Y′) − r(K) − 1 = 0 and r(X′′) + r(Y′′) − r(K) − 1 = 0.

Adding these equations and using submodularity, we get that

[r(X′ ∩ X′′) + r(Y′ ∪ Y′′) − r(K) − 1] + [r(X′ ∪ X′′) + r(Y′ ∩ Y′′) − r(K) − 1] ≤ 0.

Therefore

r(X′ ∩ X′′) + r(Y′ ∪ Y′′) − r(K) − 1 = r(X′ ∪ X′′) + r(Y′ ∩ Y′′) − r(K) − 1 = 0,

since K does not have a 1-separation and both X′ ∩X′′ and Y′ ∩Y′′ are non-empty. Thus if Z ∈ {X′ ∩ X′′, Y′ ∩ Y′′} and |Z| > 1, then {Z, E(K) − Z} is a 2-separation of K. By interchanging the roles of X′ and Y′ in the above, we conclude that {Z, E(K) − Z} is a 2-separation for K for all Z in F(K) with |Z| > 1.

To prove the second part of the lemma, we argue by induction on the number n of members of F(K) that contain more than one element. If n = 0, then K has exactly four elements and {X′, Y′} and {X′′, Y′′} are distinct 2-separations of it. It follows that K is a 4-circuit or a 4-cocircuit, so the desired conclusion holds when n = 0. We may now assume that the result holds when n < k and let n = k ≥ 1. Then, for some X ∈ F(K), we have |X| > 1. Then K is the 2-sum of K_{X} and another matroid K_{1} with ground set (E(K) − X) ∪ e_{X}. For all W in {X′, Y′, X′′, Y′′}, let W_{1} = (W − X) ∪ e_{X} if X ⊆ W, and W_{1} = W otherwise. Then it is straightforward to check that both {X′_{1}, Y′_{1}} and {X′′_{1}, Y′′_{1}} are 2-separations of K_{1}. Moreover, if F(K_{1}) = {X′_{1}∩X′′_{1}, X′_{1}∩Y′′_{1}, X′′_{1}∩Y′_{1}, X′′_{1}∩Y′′_{1}}, then F(K_{1}) = (F(K)−{X})∪{e_{X}} and so F(K_{1}) has fewer members of size exceeding one than F(K). It follows, by the induction assumption, that K_{1} is the 2-sum of a 4-element circuit or cocircuit and all the matroids K_{X_{1}} for which X_{1} is a member of F(K_{1}) with more than one element. But K is the 2-sum of K_{1} and K_{X}, and F(K_{1}) = (F(K) − {X}) ∪ {e_{X}}. The required result now follows without difficulty.

The next lemma deals with a connected matroid having an element whose deletion disconnects it.

2.7. Lemma. Let H be a connected matroid without parallel elements and suppose that H\e is not connected. Then H has at most one triangle containing e. Moreover, when such a triangle T exists,

(i) the elements of T − e are in different components of H\e; and (ii) if |E(H)| ≠ 3, then there is an element x of T −e such that H\x is connected.

Proof. Since H\e is not connected, H is the series connection, with basepoint e, of two connected matroids, H_{1} and H_{2}. A set T is a triangle of H containing e if and only if, for each i in {1, 2}, there is a 2-circuit of H_{i} containing e. It follows easily from the fact that H has no parallel elements that H has at most one triangle containing e. When such a triangle T exists, clearly (i) holds. Moreover, if |E(H)| ≠ 3, at least one of H_{1} and H_{2}, say H_{1}, has at least three elements. Let {x, e} be a circuit of H_{1}. Then H_{1}\x is connected having at least two elements and so H\x, the series connection of H_{1}\x and H_{2}, is also connected.

2.8. Lemma. Suppose that N and N\e are connected matroids, that {X′, Y′} and {X′′, Y′′} are crossing 2-separations of N\e, and that J(N\e) is a four-element circuit. Assume that N has no parallel elements and that N/e has (N/e)|X′ and (N/e)|Y′ as its connected components. Then

λ_{2}(N) = λ_{2}(N\e).

Moreover, either N has a 2-cocircuit whose union with e is a triangle, or λ_{2}(N\e) = λ_{2}(N/e) + 2 and e is in at most two triangles of N.

Proof. By Lemma 2.4, since N/e is disconnected and N ≅ U̸_{1,3}, we have that λ_{2}(N) = λ_{2}(N\e). Moreover, N is the parallel connection, with basepoint e, of the connected matroids N|(X′ ∪ e) and N|(Y′ ∪ e). The deletion of e from each of the last two matroids produces matroids for which {X′ ∩ X′′, X′ ∩ Y′′} and {Y′ ∩ X′′, Y′ ∩ Y′′}, respectively, are 1-separations. Hence, both deletions are disconnected. It follows, since N has no parallel elements by Lemma 2.7, that each of N|(X′ ∪ e) and N|(Y′ ∪ e) has at most one triangle containing e, so N has at most two triangles containing e.

Suppose that at least one of |X′| and |Y′| is 2, say the former. Then (N/e)|X′ ≅ U_{1,2}. It follows that X′ is a 2-cocircuit of N/e and hence of N, and X′ ∪ e is a triangle of N. Thus, in this case, the required result holds. Therefore we may assume that both |X′| and |Y′| exceed two.

By Lemma 2.5,

λ_{2}((N/e)|X′) = λ_{2}(N|(X′ ∪ e)) − 1

and

λ_{2}((N/e)|Y′) = λ_{2}(N|(Y′ ∪ e)) − 1.

Clearly, λ_{2}(N/e) = λ_{2}((N/e)|X′)+λ_{2}((N/e)|Y′). Thus, on combining the last three equations, we deduce that

λ_{2}(N/e) = λ_{2}(N|(X′ ∪ e)) + λ_{2}(N|(Y′ ∪ e)) − 2.

As N\e is the 2-sum of N|(X′ ∪ e) and N|(Y′ ∪ e), we have

λ_{2}(N\e) = λ_{2}(N|(X′ ∪ e)) + λ_{2}(N|(Y′ ∪ e)).

Finally, the combination of the last two equations gives λ_{2}(N/e) = λ_{2}(N\e) − 2, as required.

Let e be an element of a connected matroid H such that H\e is connected. We say that e destroys a 2-separation {X, Y } of H\e if neither X nor Y spans e.

2.9. Lemma. Let e be an element of a connected matroid N such that N\e is connected. Then

(i) λ_{2}(N) ≤ λ_{2}(N\e); and (ii) if e destroys some 2-separation of N\e and equality holds in (i), then either

(a) there is a matroid H in Λ_{2}(N) that is isomorphic to U_{1,3} such that e is in E(H) and N ≠ H; or

(b) there are matroids H_{1} and H_{2} in Λ_{2}(N) that are isomorphic to U_{2,4} and U_{2,3}, respectively, such that e ∈ E(H_{1}) and E(H_{1})∩E(H_{2}) is non-empty.

Proof. We prove (i) and (ii) simultaneously, arguing by induction on |E(N)|. We begin by showing that both parts of the lemma hold when N is 3-connected. In this case, either (a) λ_{2}(N) = 1, or (b) N ≅ U_{1,3} and λ_{2}(N) = 0. In the first case, either λ_{2}(N\e) ≥ 1, or λ_{2}(N\e) = 0. But the latter implies that N\e ≅ U_{1,m} for some m ≥ 3, so N ≅ U_{1,m+1}, contradicting the fact that N is 3-connected. Thus λ_{2}(N\e) ≥ 1. It follows that, in case (a), part (i) holds, and part (ii) must also hold vacuously since if λ_{2}(N\e) = λ_{2}(N) = 1, then N\e has no 2-separations. In case (b), N\e ≅ U_{1,2}, so λ_{2}(N\e) = 1 > λ_{2}(N). Hence (i) holds and again (ii) holds vacuously.

We may now assume that N is not 3-connected. Then there is a partition {X′′, Y′′} of E(N\e) such that {X′′ ∪ e, Y′′} is a 2-separation of N. If |X′′| = 1, say X′′ = {x}, then, since N\e is connected, e must be parallel to x. In that case, N is the 2-sum of two matroids, one isomorphic to U_{1,3} and the other to N\e. Thus λ_{2}(N) = λ_{2}(N\e) but, since e is parallel to x, it cannot destroy any 2-separations of N\e.

We may now suppose that |X′′| ≥ 2. Thus {X′′, Y′′} is a 2-separation of N\e. The 2-separation {X′′ ∪ e, Y′′} of N implies that N = N_{1} ⊕_{2} N_{2} where E(N_{1}) = X′′ ∪ {e, g} and E(N_{2}) = Y′′ ∪ g for some new element g. Since |X′′| ≥ 2, it follows that N\e = (N_{1}\e) ⊕_{2} N_{2}. Part (i) of the lemma will follow immediately from the following:

2.9.1. If N is the 2-sum of matroids N_{3} and N_{4} where e ∈ E(N_{3}) and |E(N_{3})| ≥ 4, then λ_{2}(N) ≤ λ_{2}(N\e). Moreover, if λ_{2}(N) = λ_{2}(N\e), then λ_{2}(N_{3}) = λ_{2}(N_{3}\e).

To see this, first note that

λ_{2}(N) = λ_{2}(N_{3}) + λ_{2}(N_{4})

and that N\e is the 2-sum of N_{3}\e and N_{4}. Thus

λ_{2}(N\e) = λ_{2}(N_{3}\e) + λ_{2}(N_{4}).

But, as N\e is connected, so too is N_{3}\e. Therefore, by the induction assumption, λ_{2}(N_{3}) ≤ λ_{2}(N_{3}\e) so λ_{2}(N) ≤ λ_{2}(N\e). Moreover, if equality holds in the first of these, it holds in the second. We conclude that (2.9.1) holds.

To prove (ii), suppose that λ_{2}(N) = λ_{2}(N\e) and let {X′, Y′} be a 2-separation of N\e that is destroyed by e. Suppose that N/e is not connected. Then, by Lemma 2.4, (ii)(a) holds.

We may now assume that N/e is connected. Next we establish the following:

2.9.2. If N has a 2-separation {Z, W } such that Z is a proper subset of X′ or Y′, then the lemma holds.

Suppose that such a 2-separation {Z, W } exists. Without loss of generality, we may assume that Z is properly contained in X′. Then, since e ∉ X′, we deduce that e ∈ W and W − e properly contains Y′. Thus {Z, W − e} is a 2-separation of N\e. Clearly N is the 2-sum of two connected matroids N_{Z} and N_{W} having ground sets Z ∪ f and W ∪ f, for some new element f. Thus N\e = N_{Z} ⊕_{2} (N_{W} \e) and, since N\e is connected, so is N_{W} \e. Moreover, since |W − e| > |Y′| ≥ 2, we have |E(N_{W})| ≥ 4. Therefore, by (2.9.1), since λ_{2}(N) = λ_{2}(N\e), we have that λ_{2}(N_{W}) = λ_{2}(N_{W} \e). Since N_{W} \e is isomorphic to a minor of N\e, it is not difficult to see that {[(W −e)∩X′]∪f, Y′} is a 2-separation of N_{W} \e. Moreover, we may assume that this 2-separation is not destroyed by e, otherwise, by the induction assumption, (ii)(a) or (ii)(b) holds for N_{W} and hence for N. As e is not spanned by Y′ in N_{W}, we must have that e is spanned by [(W − e) ∩ X′] ∪ f in N_{W}. But f is spanned by Z in N_{Z}. Hence e is spanned by Z ∪ [(W − e) ∩ X′] in N. Since Z ∪ [(W − e) ∩ X′] = X′, we have a contradiction. Hence (2.9.2) holds.

Recall that {X′′, Y′′} and {X′, Y′} are 2-separations of N\e, that {X′′ ∪ e, Y′′} is a 2-separation of N, and that {X′, Y′} is destroyed by e. We shall show next that

|{X′′ ∩ X′, X′′ ∩ Y′, Y′′ ∩ X′, Y′′ ∩ Y′} − {∅}| = 4.

To see this, note that, as neither X′ nor Y′ spans e, neither X′ nor Y′ contains X′′, that is, both Y′ ∩ X′′ and X′ ∩ X′′ are non-empty. Moreover, by (2.9.2), neither X′ nor Y′ contains Y′′, so both Y′ ∩ Y′′ and X′ ∩ Y′′ are non-empty.

Recall that N\e is the 2-sum, with basepoint g, of N_{1}\e and N_{2}. Suppose next that both |X′′ ∩ X′| and |X′′ ∩ Y′| are one. Then |X′′| = 2. Thus N_{1}\e has exactly three elements and so is isomorphic to U_{1,3} or U_{2,3}. But, since N/e is connected, it follows that N_{1}\e ≅ U_{2,3} and N_{1} ≅ U_{2,4}. Moreover, by Lemma 2.6, the matroid J(N\e) is a 4-element circuit, two of its elements being the elements of X′′. It follows that N_{2} is the 2-sum of a triangle, whose ground set contains g, and two other matroids. Since N is the 2-sum, with basepoint g, of N_{1} and N_{2}, it follows that (ii)(b) holds.

We may now assume that |X′′ ∩ X′| ≥ 2 or |X′′ ∩ Y′| ≥ 2. Without loss of generality, assume the former. Then, by Lemma 2.6, {X′′∩X′, E(N\e)−(X′′∩X′)} is a 2-separation of N\e. It follows that {X′′ ∩ X′, (X′′ ∩ Y′) ∪ g} is a 2-separation of N_{1}\e. Since, by (2.9.1), λ_{2}(N_{1}) = λ_{2}(N_{1}\e), if e destroys the last 2-separation, then the result follows by induction. Hence e does not destroy this 2-separation, so (X′′ ∩ Y′) ∪ g spans e in N_{1}. Thus {X′′ ∩ X′, (X′′ ∩ Y′) ∪ {g, e}} is a 2-separation of N_{1}. Hence {X′′ ∩ X′, E(N) − (X′′ ∩ X′)} is a 2-separation of N. Since X′′ ∩ X′ is a proper subset of X′, it follows by (2.9.2) that the lemma holds.

The next lemma bounds λ_{2}(N) when N is a connected matroid having an element e for which N\e is disconnected. In the subsequent lemma, we compare the values of λ_{1} + λ_{2} for N, N\e, and N/e.

2.10. Lemma. Let e be an element of a connected matroid N and suppose that, for some s ≥ 2, the connected components of N\e are N_{1}, N_{2}, …, N_{s}. For all i in {1, 2, …, s}, if |E(N_{i})| > 1, let N′_{i} be obtained from N/[E(N) − (E(N_{i}) ∪ e)] by relabelling e as e_{i}; if |E(N_{i})| = 1, let E(N_{i}) = {e_{i}} and N′_{i} = N_{i}. Let N_{0} be an (s+1)-element circuit with ground set {e, e_{1}, …, e_{s}}. Then N can be obtained from N_{0} by sequentially attaching, via 2-sums, all the matroids N′_{i} for which |E(N_{i})| has more than one element. Moreover, if N is simple, then

λ_{2}(N) ≤ s − 1 − l + ∑_{i=1}^{s} λ_{2}(N_{i}),

where l equals the number of coloops of N\e.

Proof. The fact that N is a 2-sum as described follows by a straightforward induction argument on s the details of which are omitted. For the second part, note first that, for each i such that N_{i} is not a coloop of N\e, both N′_{i} and N_{i} are connected, so, by Lemma 2.9, λ_{2}(N′_{i}) ≤ λ_{2}(N_{i}). Now an (s+1)-element circuit can be obtained from s − 1 copies of U_{2,3} by a sequence of 2-sums. Thus λ_{2}(N_{0}) = s − 1. Moreover, if N_{j} is a coloop, then N′_{j} = N_{j} and so λ_{2}(N′_{j}) = 1. Hence

λ_{2}(N) = s − 1 + ∑{λ_{2}(N′_{i}) : |E(N′_{i})| > 1}
= s − 1 + ∑_{i=1}^{s} λ_{2}(N′_{i}) − l

≤ s − 1 − l + ∑_{i=1}^{s} λ_{2}(N_{i}).

2.11. Lemma. Let N be a simple matroid such that λ_{1}(N) < λ_{1}(N\e) for some e. If l is the number of the coloops of N\e that are not coloops of N, then

(i) λ_{1}(N\e) − λ_{1}(N) + λ_{2}(N\e) − λ_{2}(N) ≥ l. (ii) Moreover, when the connected component of N containing e is not a triangle,

λ_{1}(N\e) − λ_{1}(N/e) + λ_{2}(N\e) − λ_{2}(N/e) ≥ l + 1.

Proof. (i) Let N_{1}, N_{2}, …, N_{k} be the connected components of N. Suppose that e ∈ E(N_{1}). As λ_{1}(N) < λ_{1}(N\e), it follows that N_{1}\e is not a connected matroid. Let H_{1}, H_{2}, …, H_{s} be the connected components of N_{1}\e. Then the connected components of N\e are H_{1}, H_{2}, …, H_{s}, N_{2}, N_{3}, …, N_{k}. Hence

λ_{1}(N\e) − λ_{1}(N) = (s + k − 1) − k = s − 1.  (1)

Observe that

λ_{2}(N\e) − λ_{2}(N) = (∑_{i=1}^{s} λ_{2}(H_{i}) + ∑_{i=2}^{k} λ_{2}(N_{i})) − ∑_{i=1}^{k} λ_{2}(N_{i}).

Thus

λ_{2}(N\e) − λ_{2}(N) = ∑_{i=1}^{s} λ_{2}(H_{i}) − λ_{2}(N_{1}).  (2)

By Lemma 2.10, since the number of coloops of N_{1}\e equals the number of coloops of N\e that are not coloops of N,

λ_{2}(N_{1}) ≤ s − 1 − l + ∑_{i=1}^{s} λ_{2}(H_{i}).  (3)

On combining (2) and (3), we get that

λ_{2}(N\e) − λ_{2}(N) ≥ l + 1 − s,

and (i) follows by combining this inequality with (1).

To prove (ii), suppose that N_{1} is not a triangle. Then, by Lemma 2.5,

λ_{2}(N_{1}/e) = λ_{2}(N_{1}) − 1.  (4)

Moreover, since N_{1}\e is disconnected, N_{1}/e is connected and so the connected components of N/e are N_{1}/e, N_{2}, …, N_{k}. Therefore

λ_{1}(N/e) = λ_{1}(N) and λ_{2}(N/e) = λ_{2}(N) − 1,  (5)

where the second equation follows by (4). On substituting (5) into (i), we immediately obtain (ii).

The next lemma deals with a 3-connected matroid having an element whose deletion reduces the connectivity.

2.12. Lemma. Suppose that M is a 3-connected matroid and that M\e is not 3connected. If N is a connected restriction of M such that e ∈ E(N), then N/e has at most two connected components.

Proof. Let {X, Y } be a 2-separation of M\e. Suppose that N/e has t components for some t ≥ 3. Then N is the parallel connection of t matroids across a common basepoint e [3]. Thus N has circuits C_{1} ∪ e, C_{2} ∪ e, and C_{3} ∪ e such that C_{1}, C_{2}, and C_{3} are disjoint circuits of N/e. For each i in {1, 2, 3}, let X_{i} = C_{i} ∩ X and Y_{i} = C_{i} ∩ Y. Then, since neither X nor Y spans e in M, both X_{i} and Y_{i} are non-empty. Thus both X_{1} ∪ X_{2} ∪ X_{3} and Y_{1} ∪ Y_{2} ∪ Y_{3} are independent in N/e and hence in M. Therefore X and Y have bases B_{X} and B_{Y} that contain X_{1} ∪ X_{2} ∪ X_{3} and Y_{1} ∪ Y_{2} ∪ Y_{3}, respectively. Thus

r(X) + r(Y) = r(B_{X}) + r(B_{Y}) = |B_{X}| + |B_{Y} | = |B_{X} ∪ B_{Y} |.

But B_{X} ∪ B_{Y} contains C_{1} ∪ C_{2} and C_{1} ∪ C_{3}, each of which is a circuit of M. Since B_{X} ∪ B_{Y} spans M, it follows that (B_{X} ∪ B_{Y}) − {a_{2}, a_{3}} spans M, where a_{i} is an arbitrary element of C_{i} for each i. Hence

|B_{X} ∪ B_{Y} | − 2 ≥ r(B_{X} ∪ B_{Y}) = r(M\e),

so r(X) + r(Y) ≥ r(M\e) + 2, contradicting the fact that {X, Y } is a 2-separation of M\e.

We conclude this section by introducing a construction to assist in deciding when a certain matroid is 3-connected. This will be used at the very end of the proof of Proposition 3.1. For a matroid M and a subset A of E(M), we define a graph G(A, M) to have vertex set A and edge set a subset of cl(A) − A defined as follows: arbitrarily order the elements of A; if f is an element of E(M) − A that is in a triangle with two elements of A that are in series in M|A, we let f label the edge ab of G(A, M) for which (a, b) is lexicographically minimal among such pairs. Although G(A, M) strictly depends on the ordering imposed on A, this ordering will not be important to the properties of the graph that we shall need and so will not be mentioned further.

2.13. Lemma. Suppose that A is a circuit of a simple matroid M such that |A| ≥ 4 and that every element of E(M) − A is in a triangle with two elements in A. Then, for X ⊆ E(M) − A, the matroid M|(A ∪ X) is 3-connected if and only if G(A, M|(A ∪ X)) has either a single component or two components one of which consists of an isolated vertex.

Proof. We abbreviate G(A, M|(A∪X)) to G. The lemma will be proved by showing that the following assertions are equivalent:

(i) M|(A ∪ X) is not 3-connected; (ii) there is a partition {Y_{1}, Y_{2}} of A ∪ X such that min{|Y_{1}|, |Y_{2}|}| ≥ 2 and

r(Y_{1}) + r(Y_{2}) = r(M) + 1;

(iii) there are partitions {A_{1}, A_{2}} of A and {X_{1}, X_{2}} of X such that min{|A_{1}|,

|A_{2}|} ≥ 2 and X_{i} ⊆ E(G[A_{i}]) for each i. It is immediate that (i) and (ii) are equivalent. Moreover, by the definition of

G, (iii) implies (ii). We now show that (ii) implies (iii) thereby establishing the equivalence of the three statements and finishing the proof of the lemma. Thus assume that (ii) holds. For each i in {1, 2}, let A_{i} = A ∩ Y_{i}. If A_{i} is empty for some i, then A ⊆ Y_{j} where {i, j} = {1, 2} and, since A spans M, it follows that r(Y_{j}) = r(M). Hence r(Y_{i}) = 1. But |Y_{i}| ≥ 2, and we have a contradiction to the fact that M is simple. We conclude that A_{i} is non-empty for each i. Thus, as A_{1} ∪ A_{2} is A, a spanning circuit of M, we have

r(M) + 1 = r(Y_{1}) + r(Y_{2}) ≥ r(A_{1}) + r(A_{2}) = |A_{1}| + |A_{2}| = |A| = r(M) + 1.

Hence A_{1} and A_{2} span Y_{1} and Y_{2}, respectively, and min{|A_{1}|, |A_{2}|} ≥ 2.

Now suppose that G has an edge x joining a vertex a_{1} in A_{1} to a vertex a_{2} in A_{2}. Then {x, a_{1}, a_{2}} is a triangle of M. Without loss of generality, we may suppose that x ∈ cl(A_{1}). Then M has a circuit C such that x ∈ C ⊆ A_{1} ∪ x. Using the circuits C and {x, a_{1}, a_{2}}, we deduce that (C −x)∪{a_{1}, a_{2}} contains a circuit of M. But this set is contained in and therefore equals the circuit A. Thus A_{2} = {a_{2}}; a contradiction since min{|A_{1}|, |A_{2}|} ≥ 2. We conclude that no edge in G joins a vertex in A_{1} to a vertex in A_{2}. By letting X_{i} be the elements of X that join two vertices of A_{i}, we obtain that (iii) holds.

3. The core of the proof

In this section, we prove a technical proposition from which we shall deduce Theorem 1.3 without difficulty. We shall say that (M, A) is a minimal pair when A is a subset of the ground set of a 3-connected matroid M and M has no proper 3-connected minor M′ for which M′|A = M|A.

In the next proposition, we use the notion of a fan. Such objects were defined in general in [12]. In this paper, we shall only consider certain very special fans. Specifically, if a_{1}, a_{2}, a_{3}, a_{4}, a_{5} are distinct elements of a 3-connected matroid, then {a_{1}, a_{2}, a_{3}}, {a_{2}, a_{3}, a_{4}}, {a_{3}, a_{4}, a_{5}} is a type-2 fan of length three if {a_{1}, a_{2}, a_{3}} and {a_{3}, a_{4}, a_{5}} are triads, and {a_{2}, a_{3}, a_{4}} is a triangle, indeed the unique triangle meeting {a_{1}, a_{2}, a_{3}, a_{4}, a_{5}}. Such a fan, like all fans, can be viewed as a partial wheel. The spokes of this type-2 fan are a_{2} and a_{4}, and its rim is {a_{1}, a_{3}, a_{5}}.

3.1. 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}

Because the proof of Proposition 3.1 is quite long, we now give a brief outline of the strategy of the proof. The two values of β(A, M), while they enable one to obtain a best-possible bound in every case, do add technical problems to the proof. We shall ignore these in this brief discussion by describing only how to prove the slightly weaker bound

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

Moreover, we focus on the case when A spans M for the fans that arise when E(M) − cl(A) is non-empty are not relevant to the main part of the argument. Indeed, Lemma 3.4 shows that the structure of these fans is preserved in every 3-connected minor of M that contains the rims of all these fans. This means that these fans only need to be considered at the very end of the proof, in Lemma 3.16, and so the core of the argument can be described assuming that A spans M.

The proof of Proposition 3.1 is by contradiction. We begin with a minimal counterexample M chosen so that |A| is maximal. Then

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

Now, for each e in cl(A) − A, since (M, A ∪ e) is not a minimal pair,

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

To obtain a contradiction, we aim to show that

λ_{1}(A ∪ e, M) + λ_{2}(A ∪ e, M) ≤ λ_{1}(A, M) + λ_{2}(A, M) − 1.

Certainly λ_{1}(A∪e, M) ≤ λ_{1}(A, M). Hence we shall obtain the desired contradiction unless λ_{2}(A ∪ e, M) ≤ λ_{2}(A, M).

Attention now turns to the minimal set S_{e} of connected components of M|A whose union spans e and we distinguish the cases (i) when |S_{e}| ≥ 2, and (ii) when |S_{e}| = 1. In case (i), the subcase in which S_{e} includes a coloop is quite straightforward and is handled in Lemma 3.7 using Lemma 2.11(i). For the remaining subcase of (i) and for (ii), we turn to consideration of the simplification of M/e. This matroid is shown to be 3-connected in Lemma 3.4, and the structure of this simplification, M/e\(A − A_{e}), is considered in Lemma 3.10 where it is shown that (M/e\(A − A_{e}), A_{e}) is a minimal pair. By focussing on this minimal pair and using Lemma 2.11(ii), the remaining subcase of case (i) is completed in Lemma 3.11. Lemmas 3.12 and 3.13 use Lemmas 2.6 – 2.9 to complete the argument in case (ii) unless e is in a triangle with two elements of A that are in series in M|A. But, in that case, we are able to assume that every element of cl(A) − A obeys this exceptional condition. Then Lemma 3.14 shows that A is a circuit. Finally, Lemma 3.15, using Lemma 2.13, shows that A is non-spanning and this contradiction completes the proof.

Proof of Proposition 3.1. Suppose that the proposition fails and choose a minimal counterexample M for which |E(M)| − |A| is minimal. Equivalently, the counterexample (M, A) is chosen so that the pair (|E(M)|, −|A|) is lexicographically minimal.

We show first that M|A is not 3-connected. Assume the contrary. Then E(M) = A and λ_{1}(A, M) = 1. Since M is a counterexample to the proposition, it follows that λ_{2}(A, M) = λ_{2}(M) = 0. Thus, by Lemma 2.3(i), M must be isomorphic to U_{1,3}; a contradiction to (i). We conclude that, as asserted, M|A is not 3-connected. An easy consequence of this is that M must be simple.

3.2. Lemma. r(A) ≥ 3.

Proof. Since M|A is not 3-connected but is simple, r(A) ≥ 2. Suppose that r(A) = 2. Then, as M|A is simple but not 3-connected, M|A ≅ U_{2,2}. Thus M has a circuit C that properly contains A. Choose an element e of C−A and let M′ = (M|C).(A∪ e). Then M′ is a triangle and so is 3-connected. Moreover, M′|A = M|A. By the minimality of M, it follows that M = M′ and we arrive at a contradiction because λ_{1}(A, M) = λ_{2}(A, M) = β(A, M) = 2.

Let F_{1}, F_{2}, …, F_{n} be the fans of M that satisfy condition (ii) of the proposition. We shall use F_{i} to denote both the fan itself and its ground set. Observe that if A is a spanning set of M, then n = 0. For each i in {1, 2, …, n}, let R_{i} and Q_{i} be, respectively, the rim {a_{i0}, a_{i1}, a_{i2}} of F_{i} and a 4-circuit of M|A containing R_{i}. It is straightforward to show, using circuit elimination and orthogonality, that Q_{i} is unique. Suppose that the triads of F_{i} are T_{i0} = {a_{i0}, f_{i0}, a_{i1}} and T_{i2} = {a_{i1}, f_{i2}, a_{i2}}, and let T_{i1} be the triangle {f_{i0}, a_{i1}, f_{i2}} of F_{i}.

Next we observe that

n ≠ 1.  (6)

To see this, note, from the last paragraph, that (6) certainly holds if A is spanning. Now suppose that A is not spanning. Then E(M) − cl(A) contains a cocircuit D of M. Since M is 3-connected of rank at least three, |D| ≥ 3. Thus |E(M) − cl(A)| ≥ 3 and (6) follows by (ii).

By Oxley and Wu [12], if i ≠ j, then F_{i} and F_{j} have no common spokes. We now show that F_{i} and F_{j} are disjoint by proving that their rims are disjoint.

3.3. Lemma. If i ≠ j, then R_{i} ∩ R_{j} = ∅.

Proof. Suppose that R_{i} ∩ R_{j} ≠ ∅. Then there is an element of R_{i} in Q_{j}. It follows, by orthogonality with the triads of F_{i}, that Q_{j} contains two, and hence all three, elements of R_{i}. Similarly, R_{j} ⊆ Q_{i}. Then, since {f_{i0}, f_{i2}} and {f_{j0}, f_{j2}} are disjoint, orthogonality implies that a_{i1} ∉ R_{j} and a_{j1} ∉ R_{i}. Thus Q_{i} = R_{i} ∪ a_{j1} and Q_{j} = R_{j} ∪ a_{i1}. Moreover, Q_{i} = R_{i} ∪ R_{j} = Q_{j}. Without loss of generality, we may assume that a_{j0} = a_{i0} and a_{j2} = a_{i2}. Then M^{∗} has {a_{i0}, f_{i0}, a_{i1}}, {a_{i1}, f_{i2}, a_{i2}}, {a_{i2}, f_{j2}, a_{j1}}, and {a_{j1}, f_{j0}, a_{i0}} as triangles.

Let X = F_{i} ∪ F_{j}. Then |X| = 8. Moreover, R_{i} ∪ {f_{i0}, f_{j0}} spans X in M, and Q_{i} spans X in M^{∗}. Hence

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

As M is 3-connected, it follows that either X = E(M), or E(M) − X = {e} for some element e. By orthogonality, Q_{i} is a series class of M|cl(A). Suppose that e exists. Then r(M) = 5 and e ∉ cl(A) − A. Moreover, e is either a coloop of M|A, or a member of E(M) − cl(A). In the latter case, e is a spoke of a type-2 fan whose set of spokes is disjoint from F_{i} ∪ F_{j}; a contradiction to the fact that |E(M)| = 9. In the former case, λ_{1}(A, M) = 2, λ_{2}(A, M) = 3, and β(A, M) = 1. Hence (M, A) is not a counterexample to Proposition 3.1; a contradiction. We conclude that e does not exist and so Q_{i} = A and E(M) − cl(A) = {f_{i0}, f_{i2}, f_{j0}, f_{j2}}. Moreover, X = E(M) and A spans M^{∗}. The cocircuits {f_{i0}, a_{i1}, f_{i2}} and {f_{j0}, a_{j1}, f_{j2}} of M^{∗} imply that A does not contain a circuit of M^{∗}. Thus A is a basis of M^{∗}. Hence {a_{i1}, a_{i2}, a_{j1}} spans a hyperplane of M^{∗}, the complement of which is {f_{j0}, a_{i0}, f_{i0}}. The last set is a triangle of M meeting F_{i} that is different from T_{i1}, a contradiction to the definition of a type-2 fan of length three.

The proof of Proposition 3.1 will involve constructing minimal pairs in minors of M. The next result will be helpful in dealing with such minimal pairs.

3.4. Lemma. If (M\X/Y, A − (X ∪ Y)) is a minimal pair such that (X ∪ Y) ∩ (R_{1} ∪ R_{2} ∪ … ∪ R_{n}) = ∅, then F_{1} ∪ F_{2} ∪ … ∪ F_{n} ⊆ E(M\X/Y). Moreover, if each element of X ∩ A is parallel with some element of A − (X ∪ Y) in M/Y, then R_{i} is contained in a 4-circuit of (M\X/Y)|[A − (X ∪ Y)].

Proof. Lemma 3.4 is trivial when n = 0. Thus, by (6), we may suppose that n ≥ 2. By Lemma 3.3, R_{1} ∩ R_{2} = ∅. Thus |E(M\X/Y)| ≥ 6 since, by hypothesis, (R_{1} ∪ R_{2}) ∩ (X ∪ Y) = ∅. It follows, since M\X/Y is 3-connected, that it is simple and cosimple.

We now prove that X ∩ (F_{1} ∪ F_{2} ∪ … ∪ F_{n}) = ∅. If not, then X ∩ F_{i} ≠ ∅ for some i, say i = 1. Then, as X avoids R_{1}, we may assume that f_{10} ∈ X. Hence a_{10} and a_{11} are in series in M\f_{10} and hence are coloops or are in series in M\X/Y because (X ∪ Y) ∩ R_{1} = ∅. This contradiction to the fact that M\X/Y is cosimple implies that X ∩ (F_{1} ∪ F_{2} ∪ … ∪ F_{n}) = ∅.

Next suppose that Y ∩ F_{i} ≠ ∅ for some i, say i = 1. Then we may assume that f_{10} belongs to Y ∩ F_{i}. In M/f_{10}, the elements f_{12} and a_{11} are in parallel. But M\X/Y is simple and has a_{11} as an element. Thus f_{12} ∈ X ∪ Y. As f_{12} ∉ X, by the previous paragraph, it follows that f_{12} ∈ Y. Hence a_{11} is a loop of M\X/Y; a contradiction.

To prove the last part of the lemma, we show first that each Q_{i} is a circuit of M/Y. Assume that some Q_{i}, say Q_{1}, is not a circuit of M/Y. Since M\X/Y is 3-connected and both T_{10} and T_{12} contain cocircuits of this matroid, both T_{10} and T_{12} are cocircuits of M\X/Y. As these sets are also cocircuits of M, they must be cocircuits of M/Y. Since M/Y has a circuit properly contained in Q_{1} and meeting R_{1}, it follows by orthogonality that this circuit must be R_{1}. Therefore, in M\X/Y, the set R_{1} is a triangle. It follows that M\X/Y must be isomorphic to a rank-3 wheel or whirl. This is a contradiction since n ≠ 1. We conclude that each Q_{i} is indeed a circuit of M/Y. Now either Q_{i} avoids X, or Q_{i} contains exactly one element of X. In the first case, Q_{i} is a 4-circuit of (M\X/Y)|[A − (X ∪ Y)] containing R_{i}. In the second case, if Q_{i} ∩X = {x}, then {x, a_{i}} is a circuit of M/Y for some a_{i} in A−(X∪Y). Thus (Q_{i}−x)∪a_{i} is a 4-circuit of (M\X/Y)|[A−(X∪Y)] containing R_{i}.

The proof of Proposition 3.1 will have several steps. In each step, we shall replace the minimal pair (M, A) by a minimal pair (M′, A′) that satisfies the hypotheses of the proposition but for which (|E(M′)|, −|A′|) is lexicographically less than (|E(M)|, −|A|). Then Proposition 3.1 fails for (M, A) but holds for (M′, A′). Therefore,

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

and

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

On taking the difference of the last two inequalities, we get

δ_{A} + δ_{1} + δ_{2} − δ_{β} − δ_{E} < 0,

where

δ_{E} = |E(M)| − |E(M′)|,
δ_{β} = β(A, M) − β(A′, M′),
δ_{A} = |A| − |A′|,
δ_{1} = λ_{1}(A, M) − λ_{1}(A′, M′),
δ_{2} = λ_{2}(A, M) − λ_{2}(A′, M′).

Hence, we shall get a contradiction whenever we can show that

δ_{E} + δ_{β} ≤ δ_{A} + δ_{1} + δ_{2}.  (7)

The elementary proof of the next lemma is omitted.

3.5. Lemma. Suppose δ_{β} ≥ 1. Then δ_{β} = 1. Moreover, if r(M)−r(A) = r(M′)− r(A′), then A′ is a circuit of M′ but A is not a circuit of M.

Next we introduce some more notation. For every element e of cl(A) − A, let N_{e} be the connected component of M|(A ∪ e) that contains e. Let S_{e} be the set of connected components of N_{e}\e. The minimal pair (M′, A′) that will replace (M, A) will depend on some properties of S_{e}. In particular, the proof will use the following lemma whose proof is straightforward.

3.6. Lemma. If e ∈ cl(A) − A, then Proposition 3.1 holds for the minimal pair (M, A ∪ e).

3.7. Lemma. If e ∈ cl(A) − A, then S_{e} does not contain a coloop of M|A and hence M|(A ∪ e) has no 2-cocircuits containing e.

Proof. If M|(A∪e) has a 2-cocircuit, say {a, e}, containing e, then {a, e} is contained in the component, N_{e}, of M|(A ∪ e) containing e and therefore {a} is in S_{e}. Hence it suffices to show that S_{e} contains no coloops of M|A. Assume the contrary. Let (M′, A′) = (M, A ∪ e). By Lemma 3.6, Proposition 3.1 holds for the minimal pair (M′, A′). Let l be the number of coloops of M|A that are not coloops of M|(A ∪ e). Clearly all these coloops must belong to S_{e}. Applying Lemma 2.11(i) for N = M|(A ∪ e), we get that

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

Thus, as δ_{A} = −1 and δ_{E} = 0, we have

δ_{A} + δ_{1} + δ_{2} ≥ δ_{E} + (l − 1).

By (7), when δ_{β} ≤ l − 1, we arrive at a contradiction. Thus we may assume that δ_{β} ≥ l. But l ≥ 1, and so, by Lemma 3.5, δ_{β} = 1 and so 1 ≤ l ≤ δ_{β} = 1. Therefore

l = 1.  (8)

Moreover, since r(A∪e) = r(A), we have r(M)−r(A∪e) = r(M)−r(A), and Lemma 3.5 implies that A ∪ e is a circuit of M. Therefore all the connected components of M|A are coloops and belong to S_{e}. Thus l = r(A) and so, by Lemma 3.2, l ≥ 3; a contradiction to (8).

The next part of the argument uses Bixby’s result, Lemma 2.1. In particular, if e ∈ cl(A) − A and the simplification of M/e is not 3-connected, then the cosimplification of M\e is 3-connected. Lemma 3.9 uses a minimal pair (M′, A′), where M′ is this cosimplification, to yield the contradiction that Proposition 3.1 holds for (M, A). The proof of this lemma relies on having |A| sufficiently large, and the next lemma ensures that this condition is met.

3.8. Lemma. |A| ≥ 5.

Proof. Suppose that |A| ≤ 4. By Lemma 3.2, |A| ≥ r(A) ≥ 3. Thus |A| ∈ {3, 4}. It follows, by (6) and Lemma 3.3, that A is a spanning set of M. Moreover, if M|A has a coloop, a say, then cl(A − a) is a hyperplane of M. Hence if e ∈ cl(A) − A, then {a, e} is a cocircuit of M|(A ∪ e). This contradiction to Lemma 3.7 implies that M|A has no coloops. It follows from this, since M is simple and |A| ≤ 4, that M|A is connected. Moreover, since M|A is not 3-connected, M|A must be a 4-circuit. Thus λ_{1}(A, M) + λ_{2}(A, M) − β(A, M) = 2. Therefore, as (M, A) is a counterexample to the proposition, |E(M)| > |A| + 2 = 6. Hence M is a rank-3 matroid that has at least seven elements and has A as a spanning circuit. For all e in E(M) − A, the matroid M\e is not 3-connected and so its ground set is the union of two lines. If one of these lines has more than three points, then it contains a point f not in A, and M\f is 3-connected; a contradiction. Thus both lines have exactly three points and, since |E(M)| ≥ 7, they are disjoint. Hence each must contain two points of A and one point of E(M) − A. For a point g of the latter type, M\g is not the union of two 3-point lines; a contradiction.

3.9. Lemma. Suppose that e ∈ cl(A) − A. Then every 2-separation of M/e is minimal.

Proof. We begin by showing that

|E(M)| ≥ 7.  (9)

Suppose that (9) fails. Then, since |A| ≥ 5 by Lemma 3.8, it follows that |A| = 5 and E(M) = A ∪ e. Thus |A| − |E(M)| = −1 and so, as

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

we have λ_{1}(A, M)+λ_{2}(A, M) ≤ β(A, M) ≤ 2. Since, by Lemma 2.3(i), λ_{2}(A, M) ≥ 1, we deduce that λ_{1}(A, M) = λ_{2}(A, M) = 1. Thus M|A is 3-connected. This contradiction completes the proof of (9).

Assume that M/e has a non-minimal 2-separation. Then, by Lemma 2.1, every 2-separation of M\e is minimal and the cosimplification of M\e is 3-connected. It follows, since |E(M)| ≥ 7, that if T_{1}^{∗}, T_{2}^{∗}, …, T_{m}^{∗} are the triads of M that contain e and T_{i}^{∗} = {e, a_{i}, b_{i}}, then a_{1}, a_{2}, …, a_{m}, b_{1}, b_{2}, …, b_{m} are distinct.

Next, we shall prove the following:

3.9.1. {a_{i}, b_{i}} is a 2-cocircuit of M|A for all i in {1, 2, … m}.

As e ∈ cl(A) − A, orthogonality implies that {a_{i}, b_{i}} meets the component N_{e} of M|(A ∪ e) containing e. Clearly {a_{i}, b_{i}} ∩ E(N_{e}\e) is a union of cocircuits of M|A. Thus (3.9.1) holds, otherwise a_{i} and b_{i} are coloops of M|A so S_{e} contains a coloop of M|A and we have a contradiction to Lemma 3.7.

We shall prove next that

3.9.2. |T_{i}^{∗} ∩ (R_{1} ∪ R_{2} ∪ … ∪ R_{n})| ≤ 1 for all i. Moreover, if T_{i}^{∗} meets R_{1} ∪ R_{2} ∪ … ∪ R_{n}, then we may assume that b_{i} ∈ R_{1} ∪ R_{2} ∪ … ∪ R_{n}.

Assume that this assertion fails. Then we may suppose that b_{i} ∈ R_{j} and that i = j = 1. Then, by orthogonality, a_{1} ∈ Q_{1}. Hence a_{1} ∈ R_{1}. Thus T_{1}^{∗} = (R_{1} − a_{1k}) ∪ e for some k in {0, 1, 2}. But, by orthogonality with the triangle T_{11}, it follows that a_{11} ∉ T_{1}^{∗}. Thus T_{1}^{∗} = {e, a_{10}, a_{12}}.

Let D be a cocircuit of M such that

f_{10} ∈ D ⊆ (T_{10} ∪ T_{12}) − {a_{11}} = {f_{10}, f_{12}, a_{10}, a_{12}}.

Observe that f_{12} ∈ D, by orthogonality with T_{11}, and that |D ∩ {a_{10}, a_{12}}| ≠ 1, by orthogonality with Q_{1}. As |D| ≥ 3, it follows that D = {f_{10}, f_{12}, a_{10}, a_{12}}. Since T_{1}^{∗} = {e, a_{10}, a_{12}}, there is a cocircuit D′ of M such that

e ∈ D′ ⊆ (D ∪ T_{1}^{∗}) − a_{10} = {e, f_{10}, f_{12}, a_{12}}.

By orthogonality with Q_{1}, it follows that a_{12} ∉ D′. But |D′| ≥ 3, so D′ = {e, f_{10}, f_{12}}. Hence D′ is a triad of M containing e, so D′ = T_{i}^{∗} for some i. But D′ ∩ A = ∅ contradicting (3.9.1). We conclude that |T_{i}^{∗} ∩ (R_{1} ∪ R_{2} ∪ … ∪ R_{n})| ≤ 1 for all i. Finally, if T_{i}^{∗} meets R_{1} ∪ R_{2} ∪ … ∪ R_{n}, then we may relabel if necessary to ensure that b_{i} ∈ R_{1} ∪ R_{2} ∪ … ∪ R_{n}. Thus (3.9.2) holds.

Now let M′ = M\e/{a_{1}, a_{2}, …, a_{m}} and let A′ = A − {a_{1}, a_{2}, …, a_{m}}. Then M′ is the cosimplification of M\e and so is 3-connected. Thus there is a minor N′ of M′ such that N′|A′ = M′|A′ and (N′, A′) is a minimal pair. Let N′ = M′\X/Y. By (3.9.2), R_{1} ∪ R_{2} ∪ … ∪ R_{n} ⊆ E(M′) ∩ A = E(N′) ∩ A. Thus, by Lemma 3.4, F_{1} ∪ F_{2} ∪ … ∪ F_{n} ⊆ E(N′). Hence, by (ii) of the proposition, X ∪ Y ⊆ cl(A) − A. As r_{M′}(A′) = r_{N′}(A′), we must have that Y = ∅. Hence, for some set X,

N′ = M′\X.

Next we observe that

3.9.3. |E(N′)| ≥ 3 with equality only if E(N′) = {b_{1}, b_{2}, b} where b = b_{3}, or m = 2 and b ∈ A.

Clearly E(N′) ⊇ A′ ⊇ {b_{1}, b_{2}, …, b_{m}} and |A| = |A′| + m ≤ 2|A′|. But, by Lemma 3.8, |A| ≥ 5, so |E(N′)| ≥ |A′| ≥ 3. Moreover, if |E(N′)| = 3, then A′ = E(N′). Thus 5 ≤ |A| = 3+m, so m ≥ 2 and E(N′) = {b_{1}, b_{2}, b} where b = b_{3}, or m = 2 and b ∈ A.

We show next that

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

Assume that this fails. Then, by (3.9.3), |E(N′)| = 3, so N′ is isomorphic to U_{1,3} or U_{2,3}. Moreover, A′ spans N′ and so spans M′. Thus A spans M. First, suppose that N′ is isomorphic to U_{1,3}. Now M|A is obtained from N′ by inserting at most one element in series with each element of the latter. Thus the only 2separations of M|A are those of the form {{a_{i}, b_{i}}, A − {a_{i}, b_{i}}} for some i. Hence, as e ∈ cl(A) and M is simple and 3-connected, M|(A ∪ e) is 3-connected unless, for some i, either (i) e ∈ cl({a_{i}, b_{i}}), or (ii) e ∈ cl(A − {a_{i}, b_{i}}). But, in the first case, {e, a_{i}, b_{i}} is both a triangle and a triad of M; a contradiction. The second case contradicts orthogonality since {e, a_{i}, b_{i}} is a triad of M. Hence M|(A ∪ e) is indeed 3-connected. Thus E(M) = A ∪ e and we have a contradiction to the fact that M is a counterexample to the proposition since λ_{1}(A, M) = 1, λ_{2}(A, M) ≥ 2, and β(A, M) = 2.

We may now suppose that N′ is isomorphic to U_{2,3}. In this case, since A′ is a spanning circuit of N′, it follows that A is a 5- or 6-circuit spanning M. Therefore λ_{2}(A, M) = |A| − 2 and λ_{1}(A, M) = β(A, M) = 1. Thus, as M is a counterexample to the proposition,

|E(M)| ≥ 2|A| − 1.  (10)

For all g in E(M) − (A ∪ e), the matroid [M|(A ∪ g)]^{∗} has rank 2 and has {g} as a parallel class. Let P_{g} be the partition of A induced by the other parallel classes of this matroid. Then the series classes of M|(A ∪ g) are {g} and the members of P_{g}. Thus, for all i, the set {a_{i}, b_{i}} is contained in some member of P_{g}. When every member of P_{g} has at most two elements, it follows that each member must be equal to some {a_{i}, b_{i}} or to {b}. In this case, the only 2-separations of M|(A ∪ g) are those of the form {{a_{i}, b_{i}}, (A ∪ g) − {a_{i}, b_{i}}} for some i, and we argue as in the preceding paragraph to deduce that M|(A∪{e, g}) is 3-connected. This contradicts (10). Therefore, we may assume that, for every g, there is a set in P_{g} with at least three elements. Then either (i) b = b_{3}, |A| = 6, and, for all g, the partition P_{g} is {{a_{i}, b_{i}, a_{j}, b_{j}}, {a_{k}, b_{k}}} for some choice of {i, j, k} = {1, 2, 3} depending on g; or (ii) b ≠ b_{3}, |A| = 5, and, for all g, the partition P_{g} is {{a_{i}, b_{i}, b}, {a_{k}, b_{k}}} for some choice of {i, k} = {1, 2} depending on g. In each case, since, by (10), |E(M) − (A ∪ e)| ≥ |A| − 2, we deduce that P_{g} = P_{g′} for some distinct g and g′. Thus, for some k, both {g, a_{k}, b_{k}} and {g′, a_{k}, b_{k}} are circuits of M. Hence {g, g′, a_{k}} contains a circuit of M which, by orthogonality, must be contained in {g, g′}. This contradiction to the fact that M is simple completes the proof of (3.9.4).

Recall that M′ = M\e/{a_{1}, a_{2}, …, a_{m}}, that A′ = A − {a_{1}, a_{2}, …, a_{n}}, and that N′ = M′\X. We shall prove next that X = ∅ and hence that

3.9.5. (M\e/{a_{1}, a_{2}, …, a_{m}}, A − {a_{1}, a_{2}, …, a_{n}}) is a minimal pair for which Proposition 3.1 holds.

Recall that N′ is 3-connected, |E(N′)| ≥ 4, and M\(X ∪ e) is obtained from N′ by adding a_{i} in series with b_{i} for each i. Thus the only 2-separations of M\(X ∪ e) are those of the form {{a_{i}, b_{i}}, E(M)−(X∪{a_{i}, b_{i}})} for some i. Hence, as e ∈ cl(A) and M is simple, M\X is 3-connected unless, for some i, either e ∈ cl({a_{i}, b_{i}}), or e ∈ cl(E(M) − (X ∪ {a_{i}, b_{i}})). But each of these possibilities contradicts the fact that {a_{i}, b_{i}, e} is a triad of the simple 3-connected matroid M. Thus M\X is 3-connected so X = ∅. Hence (M′, A′) is a minimal pair. Moreover, by Lemma 3.4, (M′, A′) satisfies the hypotheses, and hence the conclusion, of Proposition 3.1.

We shall now complete the proof of Lemma 3.9 by proving (7). Certainly δ_{E} = m + 1 and δ_{A} = m. Now

M′|A′ = [(M\e)/{a_{1}, a_{2}, …, a_{m}}]|[A − {a_{1}, a_{2}, …, a_{m}}]
= (M|A)/{a_{1}, a_{2}, …, a_{m}}.

But, in M|A, for each i, the set {a_{i}, b_{i}} is a cocircuit by (3.9.1). Thus an isomorphic copy of M|A can be obtained from M′|A′ by 2-summing on a copy of U_{2,3} at each b_{i}. Hence δ_{2} = m and δ_{1} = 0. Hence, by (7), we may assume that δ_{β} ≥ m. Since m ≥ 1, it follows by Lemma 3.5 that M′|A′ is a circuit but M|A is not. This contradicts the construction of M|A from M′|A′, and thereby completes the proof of Lemma 3.9.

By Lemma 3.9 and Bixby’s lemma (2.1), if e ∈ cl(A) − A, then the simplification of M/e is 3-connected. We now seek to construct a minimal pair (M′, A′) in which M′ is this simplification.

3.10. Lemma. Suppose that e ∈ cl(A) − A and let A_{e} be a maximal subset of A such that (M/e)|A_{e} has no parallel elements. Suppose also that

(i) A = A_{e}; or (ii) |A − A_{e}| = 1 and |S_{e}| ≥ 2; or (iii) M|A_{e} has a circuit that spans e.

Then (M/e\(A − A_{e}), A_{e}) is a minimal pair for which Proposition 3.1 holds.

Proof. By Lemma 3.9, the simplification M′ of M/e is 3-connected. Let the ground set of this simplification be chosen to contain A_{e}. Then M′ = M/e\(X̃ ∪ (A − A_{e})) for some subset X̃ of cl(A) − A. Let N′ be a minimal 3-connected minor of M′ such that N′|A_{e} = M′|A_{e}.

We show next that

3.10.1. R_{1} ∪ R_{2} ∪ … ∪ R_{n} ⊆ E(N′).

Assume the contrary. Then A − A_{e} contains an element a that is in R_{i} for some i. We arrive at a contradiction because a belongs to a triangle that is contained in cl(A) but must be different from T_{i1}, yet F_{i} is a type-2 fan of length three. Hence (3.10.1) holds.

By (3.10.1) and Lemma 3.4, F_{1} ∪ F_{2} ∪ … ∪ F_{n} ⊆ E(N′). Hence, by (ii) of the proposition, if N′ = M′\X/Y, then Y ⊆ cl(A) − A. As r_{N′}(A_{e}) = r_{M′}(A_{e}) = r_{M/e}(A), it is not difficult to check that Y = ∅. Hence

N′ = M′\X.

Let H = M\(X ∪ X̃). Then one easily checks that E(H) ⊇ A. Moreover, by the hypotheses, we have

(i) A_{e} = A and N′ = H/e; or (ii) |S_{e}| ≥ 2, the set A_{e} = A − a for some element a of A, and N′ = H/e\a; or (iii) M|A_{e} has a circuit that spans e, and N′ = H/e\(A − A_{e}).

We shall prove next that, in all cases,

3.10.2. H is 3-connected.

First, suppose that A_{e} = A and H/e = N′. Assume that H is not 3-connected. As N′ is 3-connected, it follows that e is a coloop or an element in series in H. Thus e is a coloop or an element in series in H|(A ∪ e), which equals M|(A ∪ e). It cannot be a coloop because A spans e, and it cannot be in series by Lemma 3.7. Hence (3.10.2) holds in case (i).

Now suppose that (ii) holds. Since H is a restriction of M, if H\a is 3-connected, then so is H unless it has a as a coloop. But a is in a triangle of H with e and some other element of A, so a is certainly not a coloop of H. Thus we may assume that H\a is not 3-connected. But H\a/e is 3-connected, so either e is a coloop of H\a, or e is in series with some element b of H\a. In the first case, e is a coloop of H|[(A − a) ∪ e]. Since this matroid equals M|[(A − a) ∪ e] and A spans e, it follows that {a, e} is a cocircuit of M|(A ∪ e) and we have a contradiction to Lemma 3.7. Thus we may assume that {e, b} is a cocircuit of H\a. Moreover {e, b} is a cocircuit of H|[(A−a)∪e], otherwise e would be a coloop of H|[(A−a)∪e], that is, of M|[(A − a) ∪ e], and we arrive at a contradiction as before. Thus b and e are in series in M|[(A−a)∪e]. By Lemma 3.7, b and e cannot be in series in M|(A∪e). Therefore {e, a, b} is a triad of M|(A ∪ e), that is, of H|(A ∪ e). Since {e, b} is a cocircuit of H\a, it follows that {e, a, b} is a triad of H. As {a, b} is a cocircuit of M|A, it follows that a and b are in the same connected component of M|A. The matroid H\a/e is 3-connected and, by Lemma 3.8, |E(H\a/e)| ≥ |A − a| ≥ 4, it follows that the only 2-separation of H\a is {{e, b}, E(H) − {e, b, a}}. Now {e, b} cannot span a, otherwise {e, b, a} is a triangle of M|(A ∪ e) having both a and b in the same connected component of M|A which is contrary to Lemma 2.7 since, by assumption, |S_{e}| ≥ 2. Moreover, E(H) − {e, b, a} cannot span a because {e, b, a} is a triad of H. As a is spanned by E(H) − a, it follows that H is 3-connected. Thus (3.10.2) holds in case (ii).

It remains to consider case (iii). In that case, since H/e\(A−A_{e}) is 3-connected, H\(A − A_{e}) is also 3-connected unless e is a coloop or in series in H\(A − A_{e}). But the exceptional cases cannot arise because H|A_{e} = M|A_{e} and this matroid has a circuit spanning e. We conclude that H\(A − A_{e}) is indeed 3-connected. As A_{e} ∪ e spans A − A_{e} in H, it follows that H is 3-connected. Thus (3.10.2) holds in case (iii).

By (3.10.2) and the choice of M, it follows that X ∪ X̃ = ∅. Thus N′ = M′ so M′ = M/e\(A − A_{e}) and we deduce that, (M/e\(A − A_{e}), A_{e}) is a minimal pair. Moreover, by Lemmas 3.8 and 3.4, this minimal pair satisfies the hypotheses, and hence the conclusion, of Proposition 3.1.

With a view to using the minimal pair (M, A∪e), the next result establishes that λ_{1}(A, M) = λ_{1}(A ∪ e, M) for all e ∈ cl(A) − A. Recall that N_{e} is the component of M|(A ∪ e) that contains e, and S_{e} is the set of components of N_{e}\e.

3.11. Lemma. If e ∈ cl(A) − A, then |S_{e}| = 1, that is, N_{e}\e is connected.

Proof. Assume that |S_{e}| ≥ 2. Then N_{e}\e is disconnected. Thus, by Lemma 2.7, N_{e} has at most one triangle containing e. If there is no such triangle, then A_{e} = A. If there is one such triangle {a, a′, e}, then {a, a′} ⊆ A and we may assume that A_{e} = A − a. Thus, by Lemma 3.10, either (M/e, A) or (M/e\a, A − a) is a minimal pair (M′, A′) satisfying Proposition 3.1.

Clearly δ_{A} = k for some k in {0, 1} and δ_{E} = k + 1. Consider N_{e} again. Since |S_{e}| ≥ 2, we have λ_{1}(M|(A ∪ e)) < λ_{1}(M|A). By Lemma 3.7, N_{e} is not a triangle.

Hence r(N_{e}/e) ≥ 2. Thus, by Lemma 2.11(ii),

λ_{1}(M|A) − λ_{1}([M|(A ∪ e)]/e) + λ_{2}(M|A) − λ_{2}([M|(A ∪ e)]/e) ≥ 1.  (11)

But M′|A′ is either (M/e)|A or (M/e)|(A − a), that is, [M|(A ∪ e)]/e or [M|(A ∪ e)]/e\a. In the first case, we have, by (11), that

δ_{1} + δ_{2} ≥ 1.  (12)

In the second case, [M|(A ∪ e)]/e is obtained from [M|(A ∪ e)]/e\a by adding a in parallel to a′. As r(N_{e}/e) ≥ 2, it follows by Lemma 2.4 that λ_{2}([M|(A ∪ e)]/e) = λ_{2}([M|(A ∪ e)]/e\a). Thus

λ_{1}([M|(A ∪ e)]/e) + λ_{2}([M|(A ∪ e)]/e) = λ_{1}([M|(A ∪ e)]/e\a) + λ_{2}([M|(A ∪ e)]/e\a)

and so (12) holds when M′|A′ = [M|(A ∪ e)]/e\a. It now follows that δ_{β} ≥ 1 otherwise we obtain a contradiction by (7). Thus Lemma 3.5 implies that δ_{β} = 1. From the same lemma, since r(M) − r(A) = r(M′) − r(A′), we deduce that A′ is a circuit of M′, but A is not a circuit of M. Thus one of A − a, (A − a) ∪ e, or A ∪ e is a circuit of M. The last possibility leads to a contradiction to Lemma 3.7. If A − a is a circuit of M, then it follows, since |S_{e}| ≥ 2, that {a, e} is a cocircuit of M|(A ∪ e) and again we have a contradiction to Lemma 3.7. We may now assume that (A − a) ∪ e is a circuit of M and M|(A ∪ e) has no 2-cocircuit containing e. Then [M|(A ∪ e)]^{∗} has rank two and has {e} as a parallel class. Therefore this matroid has A as a cocircuit, so A is a circuit of M. This contradiction completes the proof of Lemma 3.11.

3.12. Lemma. For each e in cl(A) − A,

λ_{2}(A, M) = λ_{2}(A ∪ e, M).

Moreover, either

(i) there is a matroid H in Λ_{2}(N_{e}) that is isomorphic to U_{1,3} such that e ∈ E(H) and N_{e} ≠ H; or

(ii) there are matroids H_{1} and H_{2} in Λ_{2}(N_{e}) that are isomorphic to U_{2,4} and U_{2,3}, respectively, such that e ∈ E(H_{1}) and E(H_{1}) ∩ E(H_{2}) is non-empty.

Proof. Let (M′, A′) = (M, A ∪ e). Then, by Lemma 3.6, the proposition holds for the minimal pair (M′, A′). Let M_{1}, M_{2}, …, M_{k} be the components of M|(A ∪ e) where M_{k} = N_{e}. Then the components of M|A are M_{1}, M_{2}, …, M_{k−1}, M_{k}\e since, by Lemma 3.11, N_{e}\e is connected. Hence δ_{1} = 0. Moreover, it is not difficult to see that

δ_{2} = λ_{2}(A, M) − λ_{2}(A ∪ e, M) = λ_{2}(N_{e}\e) − λ_{2}(N_{e}).

Now suppose that λ_{2}(A, M) > λ_{2}(A ∪ e, M). Then δ_{2} ≥ 1. We also have that δ_{E} = 0 and δ_{A} = −1. It follows by (7) that δ_{β} = 1 otherwise we get a contradiction. Thus, by Lemma 3.5, A ∪ e is a circuit of M and so M|(A ∪ e) has a 2-cocircuit containing e; a contradiction to Lemma 3.7. We conclude that λ_{2}(A, M) ≤ λ_{2}(A ∪ e, M) and so

λ_{2}(N_{e}\e) ≤ λ_{2}(N_{e}).

Lemma 2.9(i) now implies that λ_{2}(N_{e}) = λ_{2}(N_{e}\e). Hence λ_{2}(A, M) = λ_{2}(A ∪ e, M). Furthermore, it follows by Lemma 2.9(ii) that to complete the proof that (i) or (ii) holds, it suffices to show that e destroys some 2-separation of N_{e}\e. Since (M, A) is a minimal pair, M\e has a 2-separation {X, Y }, say, and this 2-separation is destroyed by e. Thus {X ∩E(N_{e}\e), Y ∩E(N_{e}\e)} is a 2-separation of N_{e}\e that is destroyed by e provided that both |X ∩ E(N_{e}\e)| and |Y ∩ E(N_{e}\e)| exceed one. But if |X ∩ E(N_{e}\e)| ≤ 1, then Y ∩ E(N_{e}\e) spans e, so Y spans e in M; a contradiction. Hence |X ∩ E(N_{e}\e)| ≥ 2 and, similarly, |Y ∩ E(N_{e}\e)| ≥ 2. We conclude that {X ∩ E(N_{e}\e), Y ∩ E(N_{e}\e)} is a 2-separation of N_{e}\e that is destroyed by e, and the lemma follows.

In the last part of the argument proving Proposition 3.1, we shall use Lemma 2.13, which constructs an auxiliary graph to determine when a certain restriction of M is 3-connected. The next lemma verifies that a crucial hypothesis of Lemma 2.13 holds.

3.13. Lemma. Every element e of cl(A) − A belongs to a triangle T_{e} of M such that T_{e} − e is contained in a series class of M|A.

Proof. Suppose that Lemma 3.13 fails for the element e. By Lemma 3.12, we have the following two cases to deal with.

(I) There is a matroid H in Λ_{2}(N_{e}) that is isomorphic to U_{1,3} such that e ∈ E(H). (II) There are matroids H_{1} and H_{2} in Λ_{2}(N_{e}) that are isomorphic to U_{2,4} and

U_{2,3}, respectively, such that e ∈ E(H_{1}) and E(H_{1}) ∩ E(H_{2}) is non-empty. In both cases, we shall prove that if A_{e} is a maximal subset of A for which (M/e)|A_{e} has no parallel elements, then A_{e} can be chosen so that it contains a circuit C spanning e. Thus, in both cases, by Lemma 3.10, (M/e\(A − A_{e}), A_{e}) is a minimal pair for which Proposition 3.1 holds. Since δ_{E} = δ_{A} + 1, it follows by (7) that it suffices to prove, in both cases, that

δ_{1} + δ_{2} ≥ 1  (13)

and

δ_{β} ≤ 0.  (14)

Assume that (I) occurs. Then N_{e}/e is disconnected and, by Lemma 2.12, it follows that N_{e}/e has exactly two connected components, say (N_{e}/e)|X and (N_{e}/e)|Y. Moreover, N_{e} is the parallel connection, with basepoint e of N_{e}|(X ∪ e) and N_{e}|(Y ∪ e). Let {V, W } be a 2-separation of M\e. As X and Y span e, but neither V nor W spans e, it follows that both V and W meet both X and Y. Let X′ = V ∩ E(N_{e}) and Y′ = W ∩ E(N_{e}). Then |X′| = |V ∩ X| + |V ∩ Y | ≥ 2, and, similarly, |Y′| ≥ 2. Hence {X′, Y′} is a 2-separation of N_{e}\e. Moreover, {X, Y } is also a 2-separation of N_{e}\e. Let

F(N_{e}\e) = {X ∩ X′, X ∩ Y′, Y ∩ X′, Y ∩ Y′}.

Clearly |F(N_{e}\e)| = 4. Next we observe that min{|X|, |Y |} ≥ 3. To see this, note that if, say, |X| = 2, then X ∪ {e} is a triangle of M and X is contained in a series class of M|A; a contradiction to the assumption that Lemma 3.13 fails for e.

Next we shall make our choice for A_{e} so that M|A_{e} contains a circuit that spans e. For each Z in {X, Y }, let N_{Z} = N_{e}|(Z ∪ e). Now |F(N_{e}\e)| = 4. Since N_{e}/e has exactly two components, it follows, by Lemma 2.6, that J(N_{e}\e) is a 4-circuit. Therefore, N_{Z}\e is disconnected for each Z. Since N_{Z} is connected, Lemma 2.7 implies that each N_{Z} has at most one triangle T_{Z} such that e ∈ T_{Z}, and T_{Z} −e ⊆ Z ∩A. As |Z| ≥ 3, at least one of Z ∩X′ and Z ∩Y′ has more than one element. By Lemma 2.7, when T_{Z} exists, it has an element a_{Z} such that N_{Z}\a_{Z} is connected. When T_{Z} does not exist, let a_{Z} = e. Now let A_{e} = A − {a_{X}, a_{Y} }. Then A_{e} is a maximal subset of A such that (M/e)|A_{e} has no parallel elements.

Moreover, N_{e}|[(A_{e} ∩ E(N_{e})) ∪ e] is the parallel connection, with basepoint e, of N_{X}|[(A_{e} ∩ E(N_{X})) ∪ e] and N_{Y} |[(A_{e} ∩ E(N_{Y})) ∪ e]. Since each of the last two matroids is connected, it follows that N_{e}|[A_{e} ∩ E(N_{e})] has a circuit spanning e. Hence, by Lemma 3.10, (M/e\(A − A_{e}), A_{e}) is a minimal pair, (M′, A′), for which Proposition 3.1 holds.

Observe that the sets of connected components of M|A and M′|A_{e} coincide except for those meeting E(N_{e}). Thus δ_{1} = −1 since N_{e} is a component of M|A whereas N_{e}/e\(A−A_{e}) has exactly two connected components. Next we note that, since Lemma 3.13 fails for e, Lemma 2.8 implies that

λ_{2}(N_{e}\e) = λ_{2}(N_{e}/e) + 2.

But the elements of A − A_{e} are parallel to elements of A_{e} in N_{e}/e. Since each component of N_{e}/e has at least three elements including at most one parallel pair, it follows that λ_{2}(N_{e}/e) = λ_{2}(N_{e}/e\(A − A_{e})). Thus λ_{2}(N_{e}\e) = λ_{2}(N_{e}/e\(A − A_{e})) + 2, so δ_{2} = 2 and (13) holds. Assume that (14) fails, that is, δ_{β} ≥ 1. Then, by Lemma 3.5, A_{e} is a circuit of M′. But this is a contradiction since M′|A_{e} has at least two connected components. Hence both (14) and (13) hold in case (I).

Now consider case (II). First, we shall make our choice of A_{e}. Let f be the element in both H_{1} and H_{2}. Then f is in no other member of Λ_{2}(N_{e}), and N_{e} is the 2-sum, with basepoint f, of two matroids K_{1} and K_{2}, where H_{i} ∈ Λ_{2}(K_{i}) for each i. Moreover, K_{1} and K_{2} are both simple, since H_{1} and H_{2} are the only members of Λ_{2}(N_{e}) containing f, and both H_{1} and H_{2} are simple. To determine A_{e}, we need to locate the non-trivial parallel classes of N_{e}/e. The last matroid is the 2-sum, with basepoint f, of K_{1}/e and K_{2}. Since K_{2} is simple, N_{e}/e has no non-trivial parallel classes meeting K_{2}. Consider K_{1}\f. Since H_{1} is a 4-point line containing e and f, we see that H_{1}\f is connected and H_{1}\f\e is disconnected. But K_{1} can be obtained from H_{1} by attaching matroids at one or both of the elements in E(H_{1}) − {e, f} using 2-sums. Thus K_{1}\f is connected and K_{1}\f\e is disconnected. Hence, by Lemma 2.7, K_{1}\f has at most one triangle containing e. Thus N_{e}/e has at most one non-trivial parallel class meeting E(K_{1}\f) and this class has at most two elements. Therefore, either (i) we can choose A_{e} = A, or (ii) K_{1}\f has a triangle T containing e and T − e ⊆ A. Consider the second case. We may assume that K_{1} ≠ H_{1} otherwise E(H_{1}) − f is a triangle containing e, and E(H_{1}) − {f, e} is contained in a series class of M|A; a contradiction. Thus |E(K_{1}\f)| ≠ 3. Therefore, by Lemma 2.7, T − e contains an element a of A such that K_{1}\f\a is connected. Since K_{1}\e\a is isomorphic to K_{1}\f\a under the map that takes f to e and fixes every other element, K_{1}\e\a is connected. Therefore N_{e}\{e, a} is connected since it is the 2-sum, with basepoint f, of K_{1}\e\a and K_{2}. Thus, in case (ii), we can choose A_{e} = A − a and check that N_{e}|(A_{e} ∩ E(N_{e})) has a circuit spanning e. We deduce that either

(i) A_{e} = A; or (ii) A_{e} = A − a and {a, e, a′} is a triangle of M for some a′ in A.

In both cases, by Lemma 3.10, (M/e\(A − A_{e}), A_{e}) is a minimal pair, (M′, A′), satisfying Proposition 3.1.

Now N_{e}/e is connected. Thus M|A and M′|A′ have the same number of connected components. Hence

δ_{1} = 0.

Next consider δ_{2}. Let M_{1}, M_{2}, …, M_{k} be the connected components of M|(A∪e) where N_{e} = M_{k}. As e ∈ E(H_{1}) and both H_{1}\e and H_{1}/e are 3-connected,

Λ_{2}(N_{e}\e) = (Λ_{2}(N_{e}) − {H_{1}}) ∪ {H_{1}\e}  (15)

and

Λ_{2}(N_{e}/e) = (Λ_{2}(N_{e}) − {H_{1}}) ∪ {H_{1}/e}.  (16)

Now the elements of A − A_{e} are parallel to elements of A_{e} in N_{e}/e and this matroid is connected of rank at least two. Thus λ_{2}(N_{e}/e) = λ_{2}(N_{e}/e\(A − A_{e})). As M_{1}, M_{2}, …, M_{k−1} are connected components of both M|A and M′|A′, it follows that

δ_{2} = λ_{2}(A, M) − λ_{2}(A_{e}, M′) = λ_{2}(N_{e}\e) − λ_{2}(N_{e}/e).

Thus,

δ_{2} = 1,

by (15) and (16), because H_{1}\e is isomorphic to U_{2,3}, and therefore contributes one to λ_{2}(N_{e}\e), and H_{1}/e is isomorphic to U_{1,3} and so does not contribute to λ_{2}(N_{e}/e).

We now know that δ_{1}+δ_{2} = 1, that is, (13) holds. Assume that (14) fails, that is, δ_{β} ≥ 1. Then, by Lemma 3.5, A_{e} is a circuit of M′ but A is not a circuit of M. Thus one of A − a, (A − a) ∪ e, or A ∪ e is a circuit of M. The third possibility contradicts Lemma 3.7. In the other two cases, {a, a′, e} is a triangle of M. If (A − a) ∪ e is a circuit of M, then, from considering [M|(A ∪ e)]^{∗}, it is not difficult to see that {a′, e} is a cocircuit of M|(A ∪ e), again contradicting Lemma 3.7. Hence we may assume that A − a is a circuit of M. Since it is also a circuit of M/e, it follows that e is a coloop of M|[(A − a) ∪ e]. But the circuit {a, a′, e} now implies that {a, e} is a cocircuit of M|(A ∪ e). This contradiction to Lemma 3.7 completes the proof that (14) holds in case (II) and thereby finishes the proof of Lemma 3.13.

We shall use the last lemma to show, in Lemma 3.15, that A is non-spanning. The next lemma proves a preliminary step towards this goal,

3.14. Lemma. If cl(A) = E(M), then A is a circuit.

Proof. As E(M) − A ≠ ∅, it follows from Lemma 3.13 that M|A has a non-trivial series class S. If S = A, then the result is immediate. Hence we may suppose that S ≠ A. Thus {S, A − S} is a 1- or 2-separation of M|A. Note that every element of M is spanned by S or A − S, because every series class of M|A is contained in one of these sets. Thus {cl(S), E(M) − cl(S)} is a 1- or 2-separation of M; a contradiction.

3.15. Lemma. E(M) − cl(A) ≠ ∅.

Proof. Suppose that A is spanning. Then, by Lemma 3.14, A is a circuit of M. Now consider the graph G(A, M) with edge set E(M) − A and vertex set A, which is defined just before Lemma 2.13. As M is 3-connected, Lemma 3.13 and Lemma 2.13 imply that, for the graph G(A, M), either (i) it is connected, or (ii) it is disconnected having exactly two components, one an isolated vertex. But (M, A) is a minimal pair. Hence, for all elements e of E(M) − A, the matroid M\e is not 3connected, so G(A, M\e), which equals G(A, M)\e, satisfies neither (i) nor (ii). We conclude that G has no cycles and has exactly two components. Thus the number of edges of G is two less than the number of vertices. Hence |E(M) − A| = |A| − 2. Now M|A is a circuit, so

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

and we obtain a contradiction since it follows that (M, A) does satisfy the proposition.

Let S_{1}, S_{2}, …, S_{m} be the non-trivial series classes of M|A. The following lemma, whose proof is heavily based on Lemma 2.13, will quickly yield a final contradiction, namely that (M, A) is not a counterexample to the proposition.

3.16. Lemma. There is a partition P_{1}, P_{2}, …, P_{m} of E(M) − A such that

|P_{i}| ≤ \{ \begin{matrix}|S_{i}| − 2, & when S_{i} is a circuit of M|A; \\ |S_{i}| − 1, & when S_{i} is not a circuit of M|A. \end{matrix}

Proof. For each non-trivial series class S_{i} that contains R_{j} for some j, we can take P_{i} = F_{j} − R_{j} = {f_{j0}, f_{j2}}. Then either S_{i} = R_{j}, or S_{i} = Q_{j}. In each case, the bound on |P_{i}| holds. Since every element of E(M) − cl(A) is contained in one of the fans, F_{t}, it only remains to partition cl(A) − A.

By Lemma 3.13, each element of cl(A) − A is in a triangle T_{e} such that T_{e} − e is contained in a series class of M|A. Thus, the graph G(A, M) defined prior to Lemma 2.13 has vertex set A and edge set cl(A) − A. Let G_{1}, G_{2}, …, G_{k} be the connected components of G(A, M) having at least one edge. By the definition of G(A, M), it follows that each V (G_{j}) is contained in a series class S_{i} of M|A. By orthogonality, such an S_{i} avoids R_{t} for all t. We define P_{i} to be the union of the sets E(G_{j}) for which V (G_{j}) ⊆ S_{i}. We now abbreviate V (G_{j}) and E(G_{j}) as V_{j} and E_{j}, respectively.

First we show the following:

3.16.1. For all j, the set V_{j} is not a circuit of M|A.

Suppose that V_{j} is a circuit of M|A for some j. Then |V_{j}| ≥ 3. Assume that |V_{j}| = 3. Then V_{j} is a triangle of M and so, if e ∈ E_{j}, then M|(V_{j} ∪ e) is a 4-element simple rank-2 matroid and so is isomorphic to U_{2,4}. Hence M\e is 3connected; a contradiction to the fact that (M, A) is a minimal pair. We may now assume that |V_{j}| ≥ 4. Consider the matroid M_{j} = M|(V_{j} ∪ E_{j}). The graph G(V_{j}, M_{j}) coincides with the connected graph G_{j} and so, by Lemma 2.13, M_{j} is 3-connected. Furthermore, either G_{j} is a tree or not. In each case, we show that M_{j} has an element e such that M_{j}\e is 3-connected. In the first case, we choose e to be an edge of G_{j} meeting a degree-one vertex. Then G_{j}\e has two components, one an isolated vertex. Since G_{j}\e = G(V_{j}, M_{j}\e), Lemma 2.13 implies that M_{j}\e is indeed 3-connected. Now suppose that G_{j} is not a tree. Then G_{j} has an edge e such that G_{j}\e is connected and Lemma 2.13 again implies that M_{j}\e is 3-connected.

Consider M\e. It has a 2-separation {X, Y }. Since {X ∩ E(M_{j}), Y ∩ E(M_{j})} is not a 2-separation of M_{j}, we may assume that |X ∩ E(M_{j})| ≤ 1. Now T_{e} − e must meet both X and Y since neither X nor Y spans e. Thus T_{e} − e meets both X ∩ E(M_{j}) and Y ∩ E(M_{j}). Thus X ∩ E(M_{j}) = {a} for some a in T_{e} − e. Hence V_{j} ∩ Y ∩ E(M_{j}) = V_{j} − a so this set spans a and hence spans e. Thus Y spans e. This contradiction completes the proof of (3.16.1).

Most of the rest of the proof of Lemma 3.16 will be devoted to proving the following:

3.16.2. For all j, the graph G_{j} is a tree.

If |E_{j}| = 1, then (3.16.2) certainly holds. Thus we may assume that |E_{j}| ≥ 2. Let C be a circuit of M|A that contains V_{j}. By (3.16.1), C ≠ V_{j}. As a step towards (3.16.2), we now prove that

3.16.3. C − V_{j} is contained in a series class of M|(C ∪ E_{j}).

To see this, note first that M|(C ∪ E_{j}) is connected since it has C as a spanning circuit. Hence r(M|(C ∪ E_{j})) = |C| − 1. Consider the partition {V_{j}, C − V_{j}} of C. Certainly |V_{j}| ≥ 2. Moreover, we may assume that |C − V_{j}| ≥ 2 otherwise (3.16.3) is immediate. Since V_{j} spans E_{j}, and both V_{j} and C − V_{j} are independent, we have

1+r(M|(C∪E_{j})) = |C| = |V_{j}|+|C−V_{j}| = r(V_{j})+r(C−V_{j}) = r(V_{j} ∪E_{j})+r(C−V_{j}).

Thus {V_{j} ∪ E_{j}, C − V_{j}} is a 2-separation of M|(C ∪ E_{j}) so

r(C − V_{j}) + r^{∗}(C − V_{j}) − |C − V_{j}| = 1.

As r(C − V_{j}) = |C − V_{j}|, it follows that r^{∗}(C − V_{j}) = 1. Since M|(C ∪ E_{j}) is connected, we conclude that (3.16.3) holds.

Now, for each c in C − V_{j}, define

H_{c} = [M|(C ∪ E_{j})]/[C − (c ∪ V_{j})],

noting that (3.16.3) implies that, up to isomorphism, H_{c} is independent of the choice of c. More specifically, if c and d are distinct elements of C − V_{j}, then there is an isomorphism from H_{c} to H_{d} that maps c to d and fixes every other element.

We show next that

3.16.4. H_{c} is 3-connected.

Consider G(V_{j} ∪ c, H_{c}). It is not difficult to see that this graph is the subgraph of G(A, M) induced by the set V_{j} ∪ c of vertices. As |E_{j}| ≥ 2, we have |V_{j}| ≥ 3, so |V_{j} ∪ c| ≥ 4. We show next that H_{c} is simple. This follows by (3.16.3) provided we can show that H_{c} has no 2-circuit containing c. Hence suppose that {c, z} is a 2-circuit of H_{c}. Then (C − V_{j}) ∪ z is a circuit of M. Since this circuit cannot properly be contained in C, it follows that z ∈ E_{j}. Let a and b be the end-vertices of z in G(V_{j} ∪c, H_{c}). Then {a, b, z} is a circuit of M. Hence, by circuit elimination, {a, b} ∪ (C − V_{j}) contains a circuit of M that, since |V_{j}| ≥ 3, is properly contained in C. This contradiction completes the proof that H_{c} is simple. But G(V_{j} ∪ c, H_{c}) has two components, one of which consists of the isolated vertex c. We may now apply Lemma 2.13 to deduce that (3.16.4) holds.

We now show that, for all e in E_{j},

3.16.5. H_{c}\e is not 3-connected.

Suppose that H_{c}\e is 3-connected for some e. Then, as M\e has a 2-separation {X, Y } but {X ∩ E(H_{c}), Y ∩ E(H_{c})} cannot be a 2-separation of H_{c}\e, we may assume that |X ∩ E(H_{c})| ≤ 1. Then, as T_{e} − e meets both X and Y, it follows that X ∩ E(H_{c}) = {a} for some a in T_{e} − e.

We observe next that

C − V_{j} ⊈ Y,

for, if C − V_{j} ⊆ Y, then, as X ∩ E(H_{c}) = {a}, it follows that C − a ⊆ Y. Hence Y spans C and so spans e; a contradiction. We conclude that (C − V_{j}) ∩ X contains an element d. Then, as X ∩ E(H_{c}) = {a}, we deduce that X ∩ E(H_{d}) = {d, a}.

Hence min{|X ∩ E(H_{d})|, |Y ∩ E(H_{d})|} ≥ 2 and so {X ∩ E(H_{d}), Y ∩ E(H_{d})} is a 2-separation of H_{d}\e. The isomorphism between H_{d}\e and H_{c}\e that maps d to c and fixes every other element implies that H_{c}\e is not 3-connected. Hence (3.16.5) holds.

The graph G(V_{j} ∪ c, H_{c}) is the disjoint union of G_{j} and the isolated vertex c. Moreover, since, by (3.16.5), H_{c}\e is not 3-connected, Lemma 2.13 implies that G(V_{j} ∪c, H_{c}\e) which equals G(V_{j} ∪c, H_{c})\e,must have more than two components. Thus G_{j}\e is disconnected for all e in E_{j}, and (3.16.2) follows.

To complete the proof of Lemma 3.16, we need to verify that the specified inequality holds for a series class S_{i} that contains no R_{t}. In this case, recall that P_{i} equals the union of the sets E_{j} for all G_{j} such that V_{j} ⊆ S_{i}. Thus

|P_{i}| = ∑_{V_{j}⊆S_{i}} |E_{j}|.

But

|S_{i}| = ∑_{V_{j}⊆S_{i}} |V_{j}| + |S′_{i}|

where S′_{i} is the set of isolated vertices of G(A, M) that are in S_{i}. Since each G_{j} is a tree, |E_{j}| = |V_{j}| − 1 for all j. Thus, if p is the number of components G_{j} of G(A, M) such that V_{j} ⊆ S_{i}, then

|P_{i}| = ∑_{V_{j}⊆S_{i}}(|V_{j}| − 1) = |S_{i}| − p − |S′_{i}|.

The inequality in Lemma 3.16 certainly holds if p + |S′_{i}| ≥ 2, so assume that p + |S′_{i}| ≤ 1. Then |S′_{i}| = 0 and S_{i} = V_{j} for some j. But, in this case, by (3.16.1), S_{i} is not a circuit of M|A and again the desired inequality holds.

We are now able to complete the proof of Proposition 3.1 and hence that of Theorem 1.3.

Clearly we may adjust the labelling so that S_{1}, S_{2}, …, S_{t} are circuits and S_{t+1}, S_{t+2}, …, S_{m} are not. Then M|A is the direct sum of M|S_{1}, M|S_{2}, …, M|S_{t}, and M|[A−(S_{1} ∪S_{2} ∪…∪S_{t})] where the last matroid is the 2-sum of a certain matroid M′ with m − t circuits of sizes |S_{t+1}| + 1, |S_{t+2}| + 1, …, |S_{m}| + 1. Thus, by Lemma 3.16, there is a partition P_{1}, P_{2}, …, P_{m} of E(M) − A such that

|P_{i}| ≤ \{ \begin{matrix}|S_{i}| − 2, & when 1 ≤ i ≤ t; \\ |S_{i}| − 1, & when t + 1 ≤ i ≤ m. \end{matrix}

Since, for every circuit C with at least three elements, we have λ_{2}(C) = |C| − 2, it follows that

λ_{1}(A, M) + λ_{2}(A, M) = ∑_{i=1}^{t} λ_{1}(S_{i}, M) + ∑_{i=1}^{t} λ_{2}(S_{i}, M) + λ_{1}(A − ⋃_{i=1}^{t} S_{i}, M)

+λ_{2}(A − ⋃_{i=1}^{t} S_{i}, M)

≥ t + ∑_{i=1}^{t}(|S_{i}| − 2) + 1 + ∑_{i=t+1}^{m}(|S_{i}| − 1)

≥ t + 1 + ∑_{i=1}^{m} |P_{i}|
= t + 1 + |E(M) − A|.

But, by Lemma 3.15, β(A, M) = 1. Since t ≥ 0, we obtain the contradiction that (M, A) is not a counterexample to the proposition thereby completing the proof of Proposition 3.1. □

Proof of Theorem 1.3. Observe that (M, A) is a minimal pair where M ≅ U̸_{1,3} and A is non-empty and spanning. Then (M, A) satisfies the hypotheses of Proposition 3.1. Hence if A is not a circuit, then

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

while, if A is a circuit, then

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

But, in the latter case, λ_{1}(A, M) = 1 and either |A| ≥ 4 and λ_{2}(A, M) = |A|−2, or |A| ∈ {1, 2, 3}. The first possibility implies that |E(M)| ≤ 2|A|−2 as required. The second possibility implies that M = M|A so |E(M)| ≤ |A|+λ_{1}(A, M)+λ_{2}(A, M)− 2. □

4. Proof of Theorem 5

In this section, we show that Theorem 1.3 is best-possible by proving Theorem 1.4. Proof of Theorem 1.4. Our proof will actually establish that the theorem holds as long as N is simple but not free, that is, we allow N to be a circuit. We shall assume that N is not 3-connected otherwise we take M = N and the result holds. Now N is constructed from the collection of matroids in Λ_{2}(N) by a certain sequence of direct sums and 2-sums of pairs of matroids. It will be more convenient to deal with a matroid that is constructed by a sequence of direct sums and parallel connections, and we first describe how to obtain this matroid. Each 2-sum can be obtained by taking the parallel connection of two matroids across some basepoint and then deleting the basepoint. Let N_{1} be the matroid that is constructed from Λ_{2}(N) by replacing each 2-sum operation by the corresponding parallel connection. Thus all the basepoints are retained rather than being deleted. Since Λ_{2}(N) may include copies of U_{1,3}, there may be some non-trivial parallel classes in N_{1}. Each such parallel class P contains at most one member of E(N). Moreover, P contains more than one member of some H in Λ_{2}(N) if and only if H ≅ U_{1,3}. Let P_{1}, P_{2}, …, P_{n} be the non-trivial parallel classes of N_{1}. For each i, let the element p_{i} be chosen as follows: if E(N) ∩ P_{i} is non-empty, pick p_{i} to be the unique member of this set; otherwise choose p_{i} arbitrarily in P_{i}. If H ∈ Λ_{2}(N) but H ≅ U̸_{1,3}, then, for each i such that E(H) ∩ P_{i} is non-empty, we relabel the unique element of E(H) ∩ P_{i} by p_{i}. Let the resulting matroid be H′ and let Λ′_{2} = {H′ : H ∈ Λ_{2}(N) and H ≅ U̸_{1,3}}.

Let N′ = N_{1}\(∪_{i=1}^{n}(P_{i} −p_{i})). Then N′ is simple and can be constructed from the members of Λ′_{2} by a sequence of direct sums and parallel connections, the basepoints of which are p_{1}, p_{2}, …, p_{n}. We remark that the operation of parallel connection [3] allows arbitrarily many matroids to be simultaneously joined across a common basepoint. Clearly N can be obtained from N′ by deleting those p_{i} that are not in E(N).

The next step in the construction of a matroid M for which (M, A) is a minimal pair uses a simple auxiliary graph G(N) that we now describe. The vertices of G(N) are the elements of Λ′_{2}, and two different such vertices H_{1} and H_{2} are joined by an edge in G(N) when E(H_{1}) ∩ E(H_{2}) ≠ ∅. If we label such an edge by the unique element of E(H_{1}) ∩ E(H_{2}), then we observe that all the edges with a common label induce a complete graph, which is a block of G(N). Now the graph constructed so far need not be connected. Let G_{1}, G_{2}, …, G_{k} be its connected components where we may assume, since N is not a free matroid, that G_{1} has a vertex H_{1} such that |E(H_{1})| ≥ 3. Let L_{1} be a vertex of an endblock of G_{1} where L_{1} is not a cut-vertex of G_{1}. We complete the construction of G(N) by adding, for each i in {2, 3, …, k}, a new edge f_{i} which joins L_{1} to a vertex L_{i} of an endblock of G_{i}, where L_{i} is not a cut-vertex of G_{i}. We observe that each block of G(N) is a complete graph in which all edges have a common label.

The structure of G(N) means that we can choose a spanning tree T of this graph such that, for each endblock Z of G(N)\{f_{1}, f_{2}, …, f_{k}}, the edges of T in Z form a path P (Z) for which (i) one end is the vertex of Z that is a cut-vertex of G(N), and (ii) when L_{i} is a vertex of Z, the other end of P (Z) is L_{i}. Observe that T must contain all of the edges f_{2}, f_{3}, …, f_{k}. We extend the matroid N′ as follows, noting that each added element is canonically associated with an edge of T.

(i) For each edge x of E(T) − {f_{2}, f_{3}, …, f_{k}}, if x has endpoints H_{1} and H_{2}, choose a_{H_{1}} and a_{H_{2}} in E(H_{1}) − E(H_{2}) and E(H_{2}) − E(H_{1}), respectively, and add e_{x} freely on the line spanned by {a_{H_{1}}, a_{H_{2}}}.

(ii) For each i in {1, 2, …, k}, let x_{i} and y_{i} be elements of E(L_{i}), neither of which is a basepoint of any of the parallel connections that formed N′. Choose x_{i} and y_{i} to be distinct subject to these conditions unless L_{i} is the unique vertex of G_{i} and |E(L_{i})| = 1. In the exceptional case, let x_{i} = y_{i}. Add elements x_{1,i} and y_{1,i} freely on the lines {x_{1}, x_{i}} and {y_{1}, y_{i}}, respectively.

Let M_{1} be the matroid that is obtained after all these elements have been added.

4.1. Lemma. M_{1} is 3-connected.

Proof. We argue by induction on |E(T)|. If |E(T)| = 0, then G(N) has just one vertex, so N is 3-connected and M_{1} = N. Thus the lemma holds when |E(T)| = 0. Assume it holds when |E(T)| < n and suppose that |E(T)| = n ≥ 1.

We show next that

4.1.1. E(T) = {f_{2}, f_{3}, …, f_{n}}.

Assume that T has an edge other than f_{2}, f_{3}, …, f_{n}. Choose such an edge x that is incident with a degree-one vertex of T but is not incident with any L_{i}. This can be done unless each G_{i} consists of either a single vertex or a single edge. In the exceptional case, choose x to be the unique edge of some G_{i}.

Suppose that x joins the vertices H_{1} and H_{2} of G(N). Let H = M_{1}|(E(H_{1}) ∪ E(H_{2}) ∪ e_{x}). Then H\e_{x} is the parallel connection of two simple 3-connected matroids H_{1} and H_{2}, and e_{x} is freely added on the line spanned by {a_{H_{1}}, a_{H_{2}}} where a_{H_{1}} and a_{H_{2}} are elements of E(H_{1})−E(H_{2}) and E(H_{2})−E(H_{1}), respectively. Thus H is certainly connected.

Next we prove that

4.1.2. H is 3-connected.

To see this, let {X, Y } be a 2-separation of H. Then min{|X ∩ E(H_{i})|, |Y ∩ E(H_{i})|} ≤ 1 for each i because H_{i} is 3-connected. As min{|E(H_{1})|, |E(H_{2})|} ≥ 3, we may assume that |X ∩ E(H_{2})| ≤ 1 and |Y ∩ E(H_{1})| ≤ 1. Then X and Y span H_{1} and H_{2}, respectively. Thus

r(H) + 1 ≥ r(X) + r(Y) ≥ r(H_{1}) + r(H_{2}) = r(H) + 1

and so equality holds throughout. Since neither E(H_{1}) nor E(H_{2}) spans e_{x}, we deduce that neither X nor Y contains e_{x}. This contradiction completes the proof of (4.1.2).

Let N′′ = M_{1}|(E(N′) ∪ e_{x}). Then Λ′_{2}(N′′) = (Λ′_{2}(N′) − {H_{1}, H_{2}}) ∪ {H}, and G(N′′) can be obtained from G(N) by contracting the edge x and simplifying the resulting graph. Moreover, T/x is a spanning tree of G(N′′). Thus M_{1} can be obtained from N′′ using T/x in just the same way that M_{1} was obtained from N′ using T. Since T/x has fewer edges than T, the induction assumption implies that M_{1} is 3-connected. We conclude that (4.1.1) holds otherwise the lemma holds.

By (4.1.1), every component of N is 3-connected. Then, arguing as in [10, (4.1)], we get that M_{1}|(E(L_{1}) ∪ E(L_{i}) ∪ {x_{1,i}, y_{1,i}}) is 3-connected for all i. It follows, by [11], that M_{1} is 3-connected.

We show next that

4.2. Lemma. (M_{1}, E(N′)) is a minimal pair.

Proof. Consider how N′ is extended to give M_{1}. First note that E(N′) spans M_{1}. Thus it suffices to prove that, for each element e of E(M_{1}) − E(N′), the matroid M_{1}\e is not 3-connected. Now, for such an element e, either (i) e = e_{x} for some edge x of E(T) − {f_{2}, f_{3}, …, f_{k}}; or (ii) e ∈ {x_{1,i}, y_{1,i}} for some i in {2, 3, …, k}. In each case, consider the graph T − x where x = f_{i} in case (ii). Let V_{X} and V_{Y} be the vertex sets of the components of T − x, and let X = ∪_{H∈V_{X}} E(H) and Y = E(N′) − X. For each Z in {X, Y }, let Z′ be obtained from Z by adjoining those elements that are associated with edges of T having both endpoints in Z. Evidently Z′ is spanned by Z.

Consider {X′, Y′}. In case (ii), it is a 1-separation of M_{1}\{x_{1,i}, y_{1,i}}. In case (i), the construction of M_{1} implies that {X′ − x, Y′ − x} is a 1-separation of M_{1}\e_{x}/x since x is the basepoint of a parallel connection in N′. Therefore, in each case, M_{1}\e is not 3-connected. We conclude that (4.2) holds.

To complete the proof of Theorem 1.4, let M be obtained from M_{1} by deleting a subset S of E(N′) − E(N) such that, for all e in E(N′) − (E(N) ∪ S), the matroid M\e is not 3-connected. Then, since E(N) spans M, it follows that (M, E(N)) is a minimal pair. Now, |V (T)| = |V (G(N))| = λ_{2}(N) and λ_{1}(N) = k. Moreover, by construction,

|E(M_{1})| − |E(N′)| = [|E(T)| − (k − 1)] + 2(k − 1)
= [(|V (T)| − 1) − (k − 1)] + 2(k − 1)
= [(λ_{2}(N) − 1) − (λ_{1}(N) − 1)] + 2(λ_{1}(N) − 1)
= λ_{1}(N) + λ_{2}(N) − 2.

But

|E(N′)| − |E(N)| ≥ |S| = |E(M_{1})| − |E(M)|.

Thus

0 ≤ (|E(N′)| − |E(N)|) − (|E(M_{1})| − |E(M)|)
= (|E(M)| − |E(N)|) − (|E(M_{1})| − |E(N′)|).

Hence |E(M)| − |E(N)| ≥ λ_{1}(N) + λ_{2}(N) − 2. But, by Theorem 1.3, the reverse inequality also holds. Hence equality holds and the theorem is proved. □

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] Bixby, R.E. and Coullard, C.R., Finding a smallest 3-connected minor maintaining a fixed minor and a fixed element, Combinatorica 7 (1987), 231–242.

[3] Brylawski, T.H., A combinatorial model for series–parallel networks, Trans. Amer. Math. Soc. 154 (1971), 1–22.

[4] Brylawski, T.H., A decomposition for combinatorial geometries, Trans. Amer. Math. Soc. 171 (1972), 235–282.

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

[6] Lemos, M. and Oxley, J., On packing minors into connected matroids, Discrete Math., to appear.

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

[8] Lemos, M., Oxley, J., and Reid, T.J., On the 3–connected matroids that are minimal having a fixed restriction, submitted.

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

[10] Oxley, J.G., On packing 3-connected restrictions into 3-connected matroids, Discrete Math. 178 (1998), 181–198.

[11] Oxley, J. and Wu, H., On matroid connectivity, Discrete Math. 146 (1995), 321–324.

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

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

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