%Latest revisions done 6/27/98
% This differs only from pap_1.rev.tex in that it has a 1-page outline 
%  of the proof of the main proposition.
\documentclass[10pt,reqno]{amsart}
%\usepackage[notcite]{show keys}
\usepackage{amssymb}
\swapnumbers
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{noname}[theorem]{}
\newtheorem{sublemma}{}[theorem]


\theoremstyle{problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{example}[theorem]{Example}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

%\numberwithin{equation}{section}

\newcommand{\de}{\backslash}
\newcommand{\ag}{AG(2,3)}
\newcommand{\ba}{\backslash}
\newcommand{\sixrt}{\sqrt[6]{1}}
\newcommand{\co}{{\rm co}}
\newcommand{\si}{{\rm si}}
\newcommand{\cl}{{\rm cl}}
\newcommand{\utf}{U_{2,4}}
\newcommand{\mkf}{M(K_4)}


\begin{document}

\title[Minimal $3$--connected matroids having a fixed spanning restriction]{On the $3$--connected matroids that are minimal having a fixed spanning restriction}

\author{Manoel Lemos}
\address{Departamento de Matem\'atica\\
        Universidade Federal de Pernambuco\\
        Recife\\
        Pernambuco 50740-540\\ 
	Brazil}
\email{manoel@dmat.ufpe.br}

\author{James Oxley}
\address{Department of Mathematics\\
	Louisiana State University\\
	Baton Rouge\\ 
	Louisiana 70803--4918\\
	USA}
\email{oxley@math.lsu.edu}




\subjclass{05B35}
\date{}

\begin{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.
\end{abstract}

\maketitle
\section{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:
\vspace{0.3cm}

\begin{problem}
\label{Problem 1}
 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)|$.
\end{problem}

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 \cite{Paper2}.  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:


\begin{problem}
\label{Problem 2}
 Let $N$ be a minor of a $3$-connected matroid $M$ and $M'$ be a $3$-connected minor of $M$ that is minimal having $N$ as a minor.  Give a sharp upper bound on $|E(M') - E(N)|$.
\end{problem}

If $N$ is 3-connected and we also insist that $M' \neq N$, then Truemper \cite{tru} showed that $|E(M') - E(N)| \le 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 \cite{bixco} showed that $|E(M') - E(N)| \le 4$.  If ``3-connected'' is replaced  by ``2-connected'' throughout Problem \ref{Problem 2}, the resulting problem was solved by Lemos and Oxley \cite{lemox}. They proved that if $N$ has $k$ components, then 
$|E(M') - E(N)| \le 2k-2$ unless $N$ or its dual is free, in which case, 
$|E(M') - E(N)| \le k -1$.

In general, Problem \ref{Problem 2} seems to be much more difficult than Problem \ref{Problem 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 \ref{Problem 1}   given here is also a solution to the corresponding case  of Problem \ref{Problem 2}.

 
Let $M$ be a matroid and $A$ be a subset of $E(M)$. We define $\lambda_1(A,M)$ to be the number of connected components of $M|A$. Now $M|A$ can be constructed from a collection  $\Lambda_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 \cite{cunn}) that $\Lambda_2(A,M)$ is unique up to isomorphism. We  denote by $\lambda_2(A,M)$ the number of matroids in $\Lambda_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 \ref{Problem 1} and \ref{Problem 2} in the case that $N$ and $M$ have the same rank.
\vspace{0.3cm}

\begin{theorem}
\label{Theorem 1}
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)|\le |A|+\lambda_1(A,M)+\lambda_2(A,M)-2,$$
unless $A$ is a circuit of $M$ of size at least four,  in which case,  
$$|E(M)|\le 2|A|-2.$$
\end{theorem}

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 \cong U_{1,3}$, then $E(M) = A$.  It is natural to question the sharpness of the bounds in Theorem \ref{Theorem 1}.  When $A$ is an $n$-circuit, if $n \le 3$, then $E(M) = A$ and the appropriate bound holds; if $n \ge 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 \cite{Paper3} that the bound in Theorem \ref{Theorem 1} can be sharpened slightly; otherwise Theorem \ref{Theorem 1} is best-possible in the following strong sense.


\begin{theorem}
\label{Theorem 5}
 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|+\lambda_1(A,M)+\lambda_2(A,M)-2,$$
and $M$ has no proper $3$--connected minor $M'$ such that $M'|A=N$.
\end{theorem}

Theorems \ref{Theorem 1} and \ref{Theorem 5} 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 \ref{Theorem 1} will be deduced  as a consequence of a more technical result, Proposition \ref{Proposition 2}.  This proposition actually proves more than is needed to obtain Theorem \ref{Theorem 1}.  The extra strength of the proposition will be used in  \cite{Paper2} where Theorem \ref{Theorem 1} will be extended to the case in which the set $A$ need not be spanning.
The proof of Proposition \ref{Proposition 2} will require a number of preliminaries.  These will be proved in Section 2.

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

\begin{lemma}
\label{bixby}
Let $e$ be an element of a $3$-connected matroid $M$.  Then either $M\de e$ or $M/e$  has no non-minimal $2$-separations.  Moreover, in the first case, this cosimplification of $M\de e$ is $3$-connected, while, in the second case, the simplification of $M/e$ is $3$-connected.
\end{lemma}

For a matroid $M$, we shall use $\Lambda_2(M)$, $\lambda_2(M)$, and $\lambda_1(M)$ as abbreviations for $\Lambda_2(E(M),M)$, $\lambda_2(E(M),M)$, and $\lambda_1(E(M),M)$, respectively. It was noted in the introduction that Cunningham and Edmonds established that $\Lambda_2(M)$ is unique up to isomorphism.  More explicitly, Cunningham and Edmonds~\cite{cunn} proved the following result.

\begin{theorem}  
\label{cunn_ed}
Let $M$ be a connected matroid. Then, for some positive  
integer $k$, there is a collection $M_1,M_2,\ldots,M_k$ of $3$-connected  
matroids and a $k$-vertex tree $T$ with edges labelled $e_1,e_2,\ldots,e_{k-1}$  
and vertices labelled $M_1,M_2,\ldots,M_k$ such that 
\begin{enumerate} 
\item[(i)] each $M_i$ is $3$-connected or is a circuit or cocircuit;
\item[(ii)] $E(M_1)\cup E(M_2) \cup \ldots \cup E(M_k) = E(M) \cup  
\{e_1,e_2,\ldots,e_k\}$; 
\item[(iii)] if the edge $e_i$ joins the vertices $M_{j_1}$ and $M_{j_2}$,  
  then $E(M_{j_1}) \cap E(M_{j_2})$ 
is $\{e_i\}$;  
\item[(iv)] if no edge joins the vertices  $M_{j_1}$ and $M_{j_2}$, then   
  $E(M_{j_1}) \cap E(M_{j_i})$ is empty;
\item[(v)]  $T$ does not have two adjacent vertices that are both labelled  
by circuits or that are both labelled by cocircuits. 
\end{enumerate} 
Moreover, $M$ is the matroid that labels the single vertex of the  
tree  
$T/ e_1,e_2,\ldots,e_{k-1}$ at the conclusion of the following process:  
contract the edges $e_1,e_2,\ldots,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. 
\end{theorem} 

We construct $\Lambda_2(M)$ as follows. First let  $\Lambda_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 $\Lambda_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 \ge 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 $\Lambda_2(M)$ is, for each $n \ge 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 $\Lambda_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)| \ge 4$, the isomorphism types of the matroids that share elements with $M'_e$.








The proof of Proposition \ref{Proposition 2} will be an induction argument.  In particular, we shall require detailed information about the behaviour of the functions $\lambda_1$ and $\lambda_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 $\lambda_2$ whose straightforward proof is omitted.

\begin{lemma}
\label{Lemma 15}
\begin{enumerate} 
\item[(i)] If $\lambda_2(N)=0$, then every connected component of $N$ is isomorphic to a rank-one uniform matroid with at least three elements.
\item[(ii)] If $\lambda_2(N)\le 1$ and $N$ has no parallel elements, 
then $N$ is $3$-connected.
\end{enumerate}
\end{lemma}



\begin{lemma}
\label{Lemma 1'} 
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, 
$\Lambda_2(M)$ can be obtained from $\Lambda_2(M\de f)$ by adjoining a copy of $U_{1,3}$ whose ground set contains $f$.  In particular, 
$$\lambda_2(M)=\lambda_2(M\backslash f).$$
\end{lemma}

\begin{proof} Let $\{X,Y\}$ be a 1-separation for $M/f$. Suppose first that  $\min\{|X|,|Y|\}\ge 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\cup\{e_1\}$, $E(N_2)=Y\cup\{e_2\}$, and $N_0$ is isomorphic to $U_{1,3}$ and has ground set $\{e_1,e_2,f\}$. But  $M\backslash f$ is the 2-sum of matroids isomorphic to $N_1$ and $N_2$, and, since $N_0$ is not counted in $\lambda_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|\ge 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\de f$. Again we conclude that the result holds. 
\end{proof}

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

\begin{lemma}
\label{Lemma 1'''} 
Let $M$ be a connected matroid $M$ that is not a triangle and $f$ be an element of $M$ such that $M\backslash f$ is disconnected. Then 
$$\lambda_2(M/f)=\lambda_2(M) - 1.$$
\end{lemma}

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


\begin{lemma}
\label{Lemma 1} 
Let $\{X',Y'\}$ and $\{X'',Y''\}$ be crossing $2$-separations of a connected matroid $K$ and let ${\mathcal F}(K)= 
\{X'\cap X'',X'\cap Y'',X''\cap Y',X''\cap Y''\}.$  Then, for each $Z$ in 
${\mathcal 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 \cup e_Z$. Moreover, there is  a $4$-element circuit or cocircuit $J(K)$ 
with ground set $\{e_Z: Z \in {\mathcal 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 ${\mathcal F}(K)$ with more than one element. 
\end{lemma}


\begin{proof} As $K$ is connected, we must have that
$$r(X')+r(Y')-r(K)-1=0\hbox{ and }r(X'')+r(Y'')-r(K)-1=0.$$
Adding these equations and using submodularity, we get that
$$[r(X'\cap X'')+r(Y'\cup Y'')-r(K)-1]+[r(X'\cup X'')+r(Y'\cap Y'')-r(K)-1]\le 0.$$
Therefore 
$$r(X'\cap X'')+r(Y'\cup Y'')-r(K)-1=r(X'\cup X'')+r(Y'\cap Y'')-r(K)-1=0,$$
since $K$ does not have a 1-separation and both  $X'\cap X''$ and $Y'\cap Y''$ are non-empty. Thus if $Z \in \{X' \cap X'', Y' \cap 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 ${\mathcal F}(K)$ with $|Z| > 1$.

To prove the second part of the lemma, we argue by induction on the number $n$ of members of ${\mathcal 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 \geq 1$.  Then, for some $X \in {\mathcal 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) \cup e_X$.  For all $W$ in $\{X',Y',X'',Y''\}$, let $W_1 = (W - X) \cup e_X$ if $X \subseteq 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 ${\mathcal F}(K_1) =\{X'_1\cap X''_1,X'_1\cap Y''_1,X''_1\cap Y'_1,X''_1\cap Y''_1\}$, then ${\mathcal F}(K_1) = ({\mathcal F}(K)-\{X\})\cup \{e_X\}$ and so ${\mathcal F}(K_1)$ has fewer members of size exceeding one than ${\mathcal 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 ${\mathcal F}(K_1)$ with more than one element. But $K$ is the 2-sum of $K_1$ and $K_X$, and ${\mathcal F}(K_1) = ({\mathcal F}(K)-\{X\})\cup \{e_X\}$.  The required result now follows without difficulty.
\end{proof}

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

\begin{lemma}
\label{Claim 4'} 
Let $H$ be a connected matroid without parallel elements and suppose that $H \de  e$ is not connected. Then $H$ has at most one triangle containing $e$. Moreover, when such a triangle $T$ exists, 
\begin{enumerate}
\item[(i)] the elements of $T-e$ are in different components of $H\de e$; and 
\item[(ii)] if $|E(H)|\not=3$, then there is an element $x$ of $T - e$ such that $H \de x$ is connected.
\end{enumerate} 
\end{lemma}

\begin{proof} Since $H \de  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)|\not=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\de x$ is connected having at least two elements and so $H\backslash x$, the series connection of $H_1\backslash x$ and $H_2$, is also connected. 
\end{proof}


\begin{lemma}
\label{Lemma 1''} 
Suppose that $N$ and $N\de e$ are connected matroids, that  
$\{X',Y'\}$ and $\{X'',Y''\}$ are crossing $2$-separations of $N\de e$, and that  $J(N\de 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 
$$\lambda_2(N)=\lambda_2(N\backslash e).$$
Moreover, either $N$ has a $2$-cocircuit whose union with $e$ is a triangle, or $\lambda_2(N\backslash e)=\lambda_2(N/e)+2$ and $e$ is in at most two triangles of $N$.
\end{lemma}

\begin{proof} By Lemma \ref{Lemma 1'}, since $N/e$ is disconnected and $N \not \cong U_{1,3}$, we have that  $\lambda_2(N)=\lambda_2(N\backslash e)$.
Moreover, $N$ is the parallel connection, with basepoint $e$, of the connected matroids $N|(X' \cup e)$ and $N|(Y' \cup e)$.  The deletion of $e$ from each of the last two matroids produces matroids for which $\{X' \cap X'',X' \cap Y''\}$ and $\{Y' \cap X'',Y' \cap Y''\}$, respectively, are $1$-separations.  Hence, both deletions are disconnected. It follows, since $N$ has no parallel elements by Lemma~\ref{Claim 4'}, that each of $N|(X' \cup e)$ and $N|(Y' \cup 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' \cong U_{1,2}$. It follows that $X'$ is a 2-cocircuit of $N/e$ and hence of $N$, and $X' \cup 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 \ref{Lemma 1'''}, 
$$\lambda_2((N/e)|X')  = \lambda_2(N|(X'\cup e)) - 1$$
and 
$$\lambda_2((N/e)|Y')  = \lambda_2(N|(Y'\cup e)) - 1.$$
Clearly, $\lambda_2(N/e)  = \lambda_2((N/e)|X') + \lambda_2((N/e)|Y').$ Thus, on combining the last three equations, we deduce that
$$\lambda_2(N/e)  = \lambda_2(N|(X'\cup e)) + \lambda_2(N|(Y'\cup e)) - 2.$$
As $N\de e$ is the $2$-sum of $N|(X'\cup e)$ and $N|(Y'\cup e)$, we have 
$$\lambda_2(N\backslash e)= \lambda_2(N|(X'\cup e)) + \lambda_2(N|(Y'\cup e)).$$
Finally, the combination of the last two equations gives 
$\lambda_2(N/e) =\lambda_2(N\backslash e)-2$, as required. 
\end{proof}

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



\begin{lemma}
\label{Lemma 5} 
Let $e$ be an element of a connected matroid $N$ such that $N\de e$ is connected. Then 
\begin{enumerate}
\item[(i)] $\lambda_2(N)\le\lambda_2(N\backslash e)$; and 
\item[(ii)] if $e$ destroys some $2$-separation of $N\backslash e$ and equality holds in (i), then either 
\begin{enumerate}
\item [(a)] there is a matroid $H$ in $\Lambda_2(N)$ that is isomorphic to $U_{1,3}$ such that $e$ is in $E(H)$ and $N\not=H$; or 
\item [(b)] there are matroids $H_1$ and $H_2$ in $\Lambda_2(N)$ that are isomorphic to $U_{2,4}$ and  $U_{2,3}$, respectively,  
such that $e\in E(H_1)$ and $E(H_1)\cap E(H_2)$ is non-empty. 
\end{enumerate}
\end{enumerate}
\end{lemma}

\begin{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) $\lambda_2(N) = 1$, or (b) $N\cong U_{1,3}$ and $\lambda_2(N) = 0$. In the first case, either  $\lambda_2(N\de e) \ge 1$, or $\lambda_2(N\de e) = 0$. But the latter implies that $N\de e \cong U_{1,m}$ for some $m \ge 3$, so $N \cong U_{1,m+1}$, contradicting the fact that $N$ is 3-connected. Thus $\lambda_2(N\de e) \ge 1$. It follows that, in case (a), part (i) holds, and part (ii) must also hold vacuously since if $\lambda_2(N\de e) = \lambda_2(N) = 1$, then $N\de e$ has no 2-separations.  In case (b), $N\de e \cong U_{1,2}$, so $\lambda_2(N\de e) = 1 > \lambda_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\de e)$ such that  $\{X''\cup e,Y''\}$ is a 2-separation of $N$. If $|X''| = 1$, say $X'' = \{x\}$, then, since $N\de 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\de e$.  Thus $\lambda_2(N)=\lambda_2(N\backslash e)$ but, since $e$ is parallel to $x$, it cannot destroy any 2-separations of $N\de e$.

We may now suppose that
 $|X''|\ge 2$. Thus $\{X'',Y''\}$ is a 2-separation of $N\backslash e$.
The 2-separation $\{X''\cup e,Y''\}$ of $N$ implies that $N = N_1 \oplus_2 N_2$  where $E(N_1)=X''\cup\{e,g\}$ and $E(N_2)=Y''\cup g$ for some new element $g$. 
Since $|X''| \ge 2$, it follows that $N\de e = (N_1\de e) \oplus_2 N_2$. Part (i) of the lemma will follow immediately from the following:

\begin{sublemma}
\label{dagger} 
If $N$ is the $2$-sum of matroids $N_3$ and $N_4$ where $e \in E(N_3)$ and $|E(N_3)| \ge 4$, then $\lambda_2(N) \le \lambda_2(N\de e)$. Moreover, if $\lambda_2(N)=\lambda_2(N\de e)$, then $\lambda_2(N_3)=\lambda_2(N_3\de e)$.
\end{sublemma}

To  see this, first note that  
$$\lambda_2(N)=\lambda_2(N_3)+\lambda_2(N_4)$$
and that $N\backslash e$ is the 2-sum of $N_3\backslash e$ and $N_4$. Thus 
$$\lambda_2(N\backslash e)=\lambda_2(N_3\backslash e)+\lambda_2(N_4).$$
But, as $N\de e$ is connected, so too is $N_3\de e$.  Therefore, by the induction assumption, $\lambda_2(N_3)\le \lambda_2(N_3\de e)$ so $\lambda_2(N) \le \lambda_2(N\de e)$. Moreover, if equality holds in the first of these, it holds in the second.  We conclude that (\ref{dagger}) holds.


To prove (ii), suppose that   $\lambda_2(N)=\lambda_2(N\de e)$ and let $\{X',Y'\}$ be a 2-separation of $N\backslash e$ that is destroyed by $e$. 
Suppose that $N/e$ is not connected.  Then, by Lemma~\ref{Lemma 1'}, (ii)(a) holds.  

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

\begin{sublemma}
\label{sharp} If $N$ has a $2$-separation $\{Z,W\}$ such that $Z$ is a proper subset of $X'$ or $Y'$, then the lemma holds.
\end{sublemma}

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 \not \in X'$, we deduce that $e \in W$ and $W - e$ properly contains $Y'$.  Thus $\{Z, W-e\}$ is a 2-separation of $N\de e$.  Clearly $N$ is the 2-sum of two connected matroids $N_Z$ and $N_W$ having ground sets $Z \cup f$ and $W \cup f$, for some new element $f$. Thus $N\de e = N_Z \oplus_2 (N_W \de e)$ and, since $N\de e$  is connected, so is $N_W \de e$.  Moreover, since $|W - e| > |Y'| \ge 2$, we have $|E(N_W)| \ge 4$.  Therefore, by (\ref{dagger}), since $\lambda_2(N) = \lambda_2(N\de e)$, we have that $\lambda_2(N_W) = \lambda_2(N_W\de e)$. Since $N_W \de e$ is isomorphic to a minor of $N\de e$, it is not difficult to see that $\{[(W -e) \cap X'] \cup f, Y'\}$ is a 2-separation of $N_W \de 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) \cap X'] \cup f$ in $N_W$.  But $f$ is spanned by $Z$ in $N_Z$.  Hence $e$ is spanned by $Z \cup [(W -e) \cap X']$ in $N$.  Since $Z \cup [(W -e) \cap X'] = X'$, we have a contradiction.  Hence (\ref{sharp}) holds.

Recall that $\{X'',Y''\}$ and $\{X',Y'\}$ are 2-separations of $N\de e$, that $\{X''\cup e,Y''\}$ is a 2-separation of $N$, and that $\{X',Y'\}$ is destroyed by $e$.  We shall show next that 
$$|\{X''\cap X',X''\cap Y',Y''\cap X',Y''\cap Y'\}-\{\emptyset\}| = 4.$$
To see this, note that, as neither $X'$ nor $Y'$ spans $e$, neither $X'$ nor $Y'$ contains $X''$, that is, both $Y' \cap X''$ and $X' \cap X''$ are  non-empty.  Moreover, by (\ref{sharp}), neither $X'$ nor $Y'$ contains $Y''$, so both $Y' \cap Y''$ and $X' \cap Y''$ are  non-empty.

Recall that $N\de e$ is the 2-sum, with basepoint $g$, of $N_1\de e$ and $N_2$. 
Suppose next that both $|X'' \cap X'|$ and $|X'' \cap Y'|$ are one.  Then
$|X''| = 2$. Thus $N_1 \de 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\de e\cong U_{2,3}$ and $N_1\cong U_{2,4}$. Moreover, by Lemma \ref{Lemma 1}, the matroid $J(N\de 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''\cap X'|\ge 2$ or $|X''\cap Y'|\ge 2$.  Without loss of generality, assume the former.  Then, by Lemma \ref{Lemma 1}, 
$\{X''\cap X', E(N\de e) - (X''\cap X')\}$ is a 2-separation of $N\de e$.  It follows that 
$\{X''\cap X',(X''\cap Y')\cup g\}$ is a 2-separation of $N_1\backslash e$. Since, by (\ref{dagger}), $\lambda_2(N_1)=\lambda_2(N_1\de e)$, if $e$ destroys the last 2-separation, then the result follows by induction.  Hence $e$ does not destroy this 2-separation, so $(X'' \cap Y') \cup g$ spans $e$ in $N_1$.  Thus 
$\{X''\cap X',(X''\cap Y')\cup \{g,e\}\}$ is a 2-separation of $N_1$.  Hence  
$\{X''\cap X', E(N) -(X''\cap X')\}$ is a 2-separation of $N$. Since $X'' \cap X'$ is a proper subset of $X'$, it follows by  (\ref{sharp}) that the lemma holds. 
\end{proof}


The next lemma bounds $\lambda_2(N)$ when $N$ is a connected matroid having an element $e$ for which $N\de e$ is disconnected.  In the subsequent lemma, we compare the values of $\lambda_1 + \lambda_2$ for $N, N\de e$, and $N/e$.

\begin{lemma}
\label{Lemma $6^-$} 
Let $e$ be an element of a  connected matroid $N$ and suppose that, for some $s \ge 2$, the connected components of $N\de e$ are $N_1,N_2,\dots,N_s$. For all $i$ in $\{1,2,\dots, s\}$, if $|E(N_i)| > 1$, let $N'_i$ be obtained from $N/[E(N) - (E(N_i) \cup 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,\dots,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 
$$\lambda_2(N)\le s-1-l+\sum_{i=1}^s\lambda_2(N_i),$$
where $l$  equals the number of coloops of $N\backslash e$.
\end{lemma}


\begin{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\de e$, both $N'_i$ and $N_i$ are connected, so, by Lemma \ref{Lemma 5}, $\lambda_2(N'_i)\le\lambda_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 
$\lambda_2(N_0) = s-1$.  Moreover, if $N_j$ is a coloop, then $N'_j=N_j$ and so  
$\lambda_2(N'_j) = 1$. Hence 
\vspace{-0.7cm}
\begin{center}
\begin{eqnarray*}
\lambda_2(N)&=&s-1+\sum\{\lambda_2(N_i'):|E(N_i')|>1\}\\
&=&s-1+\sum_{i=1}^s\lambda_2(N_i') -l\\
&\le&s-1-l+\sum_{i=1}^s\lambda_2(N_i). 
\end{eqnarray*}
\end{center} 
\vspace{-1.1cm}\end{proof}
\vspace{0.3cm}

\begin{lemma}
\label{Lemma 6'} 
Let $N$ be a simple matroid such that $\lambda_1(N)<\lambda_1(N\backslash e)$ for some $e$. If $l$ is the number of the coloops of $N\backslash e$ that are not coloops of $N$, then
\begin{enumerate}
\item[(i)] $\lambda_1(N\backslash e)-\lambda_1(N)+\lambda_2(N\backslash e)-\lambda_2(N)\ge l$.
\item[(ii)] Moreover, when the connected component of $N$ containing $e$ is not a triangle, 
$$\lambda_1(N\backslash e)-\lambda_1(N/e)+\lambda_2(N\backslash e)-\lambda_2(N/e)\ge l+1.$$
\end{enumerate}
\end{lemma}

\begin{proof} (i) Let $N_1,N_2,\dots,N_k$ be the connected components of $N$. Suppose that $e\in E(N_1)$. As $\lambda_1(N)<\lambda_1(N\backslash e)$, it follows that $N_1\backslash e$ is not a connected matroid. Let $H_1,H_2,\dots,H_s$ be the connected components of $N_1\backslash e$. Then the connected components of $N\backslash e$ are $H_1,H_2,\dots,H_s, N_2,N_3,\dots,N_k$. Hence
\begin{equation}
\label{E:(6.1)}
\lambda_1(N\backslash e)-\lambda_1(N)=(s+k-1)-k=s-1.
\end{equation}
Observe that 
$$\lambda_2(N\backslash e)-\lambda_2(N)=\left(\sum_{i=1}^s\lambda_2(H_i)+\sum_{i=2}^k\lambda_2(N_i)\right)-\sum_{i=1}^k\lambda_2(N_i).$$
Thus 
\begin{equation}
\label{E:(6.2)}
\lambda_2(N\backslash e)-\lambda_2(N)=\sum_{i=1}^s\lambda_2(H_i)-\lambda_2(N_1).
\end{equation}

By Lemma \ref{Lemma $6^-$}, since the number of coloops of $N_1\backslash e$ equals the number of coloops of $N\backslash e$ that are not coloops of $N$,
\begin{equation}
\label{E:(6.3)}
\lambda_2(N_1)\le s-1-l+\sum_{i=1}^s\lambda_2(H_i).
\end{equation}
On combining (\ref{E:(6.2)}) and (\ref{E:(6.3)}), we get that 
$$\lambda_2(N\backslash e)-\lambda_2(N)\ge l+1-s,$$ 
and (i) follows by combining this inequality with (\ref{E:(6.1)}).

To prove (ii), suppose that $N_1$ is not a triangle.  Then, by Lemma \ref{Lemma 1'''},
\begin{equation}
\label{E:(6.4)}
\lambda_2(N_1/e)=\lambda_2(N_1)-1.
\end{equation}
Moreover, since $N_1\backslash e$ is disconnected,  $N_1/e$ is connected  and so the connected components of $N/e$ are $N_1/e,N_2,\dots,N_k$. Therefore 
\begin{equation}
\label{E:(6.5)}
\lambda_1(N/e)=\lambda_1(N) \hbox{ and } \lambda_2(N/e)=\lambda_2(N) -1,
\end{equation}
where the second equation follows by (\ref{E:(6.4)}).  On substituting  (\ref{E:(6.5)}) into (i), we immediately obtain (ii). 
\end{proof}

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





\begin{lemma}
\label{Lemma 7}
 Suppose that $M$ is a $3$-connected matroid and that $M\backslash e$ is not $3$-connected. If $N$ is a connected restriction of $M$ such that $e\in E(N)$, then $N/e$ has at most two connected components.
\end{lemma}

\begin{proof} Let $\{X,Y\}$ be a 2-separation of $M\backslash e$. Suppose that $N/e$ has $t$ components for some $t \ge 3$. 
Then $N$ is the parallel connection of $t$ matroids across a common basepoint $e$ \cite{bry}. Thus $N$ has circuits $C_1 \cup e, C_2 \cup e$, and $C_3 \cup 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 \cap X$ and $Y_i = C_i \cap Y$.  Then, since neither $X$ nor $Y$ spans $e$ in $M$, both $X_i$ and $Y_i$ are non-empty.  Thus both  $X_1 \cup X_2 \cup X_3$ and  $Y_1 \cup Y_2 \cup 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 \cup X_2 \cup X_3$ and  $Y_1 \cup Y_2 \cup Y_3$, respectively.  Thus 
$$r(X) + r(Y)=r(B_X) + r(B_Y)
=|B_X| + |B_Y| = |B_X \cup B_Y|.$$
But $B_X \cup B_Y$ contains $C_1 \cup C_2$ and $C_1 \cup C_3$, each of which is a circuit of $M$.  Since $B_X \cup B_Y$ spans $M$, it follows that $(B_X \cup B_Y) - \{a_2,a_3\}$ spans $M$, where $a_i$ is an arbitrary element of $C_i$ for each $i$.  Hence 
$$|B_X \cup B_Y| - 2 \ge r(B_X \cup B_Y) = r(M\de e),$$ 
so $r(X) + r(Y) \ge r(M\de e) + 2$, contradicting the fact that $\{X, Y\}$ is a $2$-separation of $M\de e$.
\end{proof}

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 \ref{Proposition 2}.
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 ${\rm 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.

\begin{lemma}
\label{Lemma 7''} 
Suppose that $A$ is a circuit of a simple matroid $M$ such that $|A|\ge 4$ and that every element of $E(M)- A$ is in a triangle with two elements in $A$. Then, for $X \subseteq E(M) -A$, the matroid  $M|(A\cup X)$ is $3$-connected if and only if $G(A,M|(A \cup X))$  has either a single component or two components one of which consists of  an isolated vertex.
\end{lemma}

\begin{proof} We abbreviate $G(A,M|(A \cup X))$ to $G$. The lemma will be proved by showing that the following assertions are equivalent:
\begin{enumerate}
\item[(i)] $M|(A\cup X)$ is not 3-connected;
\item[(ii)] there is a partition $\{Y_1,Y_2\}$ of $A\cup X$ such that $\min\{|Y_1|,|Y_2|\}|\ge 2$ and
$$r(Y_1)+r(Y_2)=r(M)+1;$$
\item[(iii)] there are partitions $\{A_1,A_2\}$ of $A$ and $\{X_1,X_2\}$ of $X$ such that $\min\{|A_1|,\linebreak
|A_2|\}\ge 2$ and $X_i\subseteq E(G[A_i])$ for each $i$. \end{enumerate}

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 \cap Y_i$.  If $A_i$ is empty for some $i$, then $A \subseteq 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| \ge 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 \cup A_2$ is $A$, a spanning circuit of $M$, we have 
$$r(M)+1 = r(Y_1) + r(Y_2)\ge 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|\}\ge 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\in {\rm cl}(A_1)$. Then $M$ has a circuit $C$ such that $x\in C\subseteq A_1\cup x$. Using the circuits $C$ and $\{x,a_1,a_2\}$, we deduce that   $(C- x)\cup \{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|\}\ge 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. 
\end{proof}


\section{The core of the proof}

In this section, we prove a technical proposition from which we shall deduce Theorem \ref{Theorem 1} without difficulty. 
We shall say that 
$(M,A)$ is  a {\it 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 \cite{oxwu}.  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 {\em 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 {\em spokes} of this type-2 fan are $a_2$ and $a_4$, and its {\em rim} is $\{a_1,a_3,a_5\}$.  


\begin{proposition}
\label{Proposition 2}
Let $(M,A)$ be a minimal pair such that
\begin{enumerate}
\item[(i)] $M$ is not isomorphic to $U_{1,3}$; and
\item[(ii)] every element of $E(M)- {\rm 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) - {\rm cl}(A)$.
\end{enumerate}
Then
$$|E(M)|\le |A|+\lambda_1(A,M)+\lambda_2(A,M)-\beta(A,M),$$
where 
$$\beta(A,M)=\left\{
\begin{tabular}{ll}
$1$,&\hbox{when $A$ is a circuit of $M$ or $r(A)\not=r(M)$;}\\
$2$,&\hbox{when $A$ is not a circuit of $M$ and $r(A)=r(M)$.}\\
\end{tabular}\right.
$$
\end{proposition}


Because the proof of Proposition~\ref{Proposition 2} is quite long, we now give a brief outline of the strategy of the proof.  The two values of $\beta(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)|\le |A|+\lambda_1(A,M)+\lambda_2(A,M)-1.$$
Moreover, we focus on the case when $A$ spans $M$ for the fans that arise when $E(M) - {\rm cl}(A)$ is non-empty are not relevant to the main part of the argument.  Indeed, Lemma~\ref{Claim 2} 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~\ref{Claim 10}, and so the core of the argument can be  described assuming that $A$ spans $M$.

The proof of Proposition~\ref{Proposition 2} is by contradiction.  We begin with a minimal counterexample $M$ chosen so that $|A|$ is maximal.  Then 
$$|E(M)|> |A|+\lambda_1(A,M)+\lambda_2(A,M)-1.$$
Now, for each $e$ in ${\rm cl}(A)-A$, since $(M,A \cup e)$ is not a minimal pair,
$$|E(M)|\le |A \cup e|+\lambda_1(A \cup e,M)+\lambda_2(A \cup e,M)-1.$$
To obtain a contradiction, we aim to show that 
$$\lambda_1(A \cup e,M)+\lambda_2(A \cup e,M) \le \lambda_1(A,M)+\lambda_2(A ,M) -1.$$
Certainly $\lambda_1(A \cup e,M) \le \lambda_1(A,M).$ Hence we shall obtain the desired contradiction unless $\lambda_2(A \cup e,M) \le \lambda_2(A,M).$ 

Attention now turns to the minimal set $\mathcal S_e$ of connected components of $M|A$ whose union spans $e$ and we distinguish the  cases  (i) when $|\mathcal S_e| \ge 2$, and (ii) when $|\mathcal S_e| = 1$. In case (i), the subcase in which $\mathcal S_e$ includes a coloop is quite straightforward and is handled in Lemma~\ref{Claim 3} using Lemma~\ref{Lemma 6'}(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~\ref{Claim 2}, and the structure of this simplification, $M/e\ba (A - A_e)$, is considered in Lemma~\ref{Claim 3''} where it is shown that $(M/e\ba (A - A_e), A_e)$ is a minimal pair.  By focussing on this minimal pair and using Lemma~\ref{Lemma 6'}(ii), the remaining subcase of case (i) is completed in Lemma~\ref{Claim 5}.  Lemmas~\ref{Claim 6} and ~\ref{Claim 7} use Lemmas~\ref{Lemma 1} -- \ref{Lemma 5} 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 ${\rm cl}(A)-A$ obeys this exceptional condition.  Then Lemma~\ref{Claim 8} shows that $A$ is a circuit.  Finally, Lemma~\ref{Claim 9}, using Lemma~\ref{Lemma 7''}, shows that $A$ is non-spanning and this contradiction completes the proof.


\medskip

\noindent{\it Proof of Proposition~\ref{Proposition 2}.} 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  $\lambda_1(A,M)=1$.  Since $M$ is a counterexample to the proposition, it follows that $\lambda_2(A,M)= \lambda_2(M)=0$. Thus, by Lemma \ref{Lemma 15}(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.

\begin{lemma}
\label{Claim 1} 
$r(A)\ge 3$.
\end{lemma}

\begin{proof} Since $M|A$ is not 3-connected but is simple, $r(A)\ge 2$.   Suppose that $r(A)=2$. Then, as $M|A$ is simple but not $3$-connected, $M|A \cong 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\cup 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 $\lambda_1(A,M)=\lambda_2(A,M)=\beta(A,M)=2$.  \end{proof}


Let $F_1,F_2,\dots,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,\ldots,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 
\begin{equation}
\label{E:(2)}
n\not=1.
\end{equation}

To see this, note, from the last paragraph, that (\ref{E:(2)}) certainly holds if $A$ is spanning.  Now suppose that $A$ is not spanning. Then  
$E(M)- {\rm cl}(A)$ contains a cocircuit $D$ of $M$. Since $M$ is 3-connected of rank at least three, $|D|\ge 3$. Thus $|E(M)- {\rm cl}(A)| \ge 3$ and (\ref{E:(2)}) follows by (ii).

By Oxley and Wu \cite{oxwu}, if $i \neq 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.

\begin{lemma}
\label{disj_rim}
If $i \neq j$, then $R_i \cap R_j = \emptyset$.
\end{lemma}

\begin{proof} Suppose that $R_i \cap R_j \neq \emptyset$.  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 \subseteq Q_i$.  Then, since $\{f_{i0},f_{i2}\}$ and  $\{f_{j0},f_{j2}\}$ are disjoint, orthogonality implies that $a_{i1}\not \in R_j$ and $a_{j1}\not \in R_i$. Thus $Q_i = R_i \cup a_{j1}$ and 
$Q_j = R_j \cup a_{i1}$.  Moreover, $Q_i = R_i \cup 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 \cup F_j$.  Then $|X| = 8$.  Moreover, $R_i \cup \{f_{i0},f_{j0}\}$ spans $X$ in $M$, and $Q_i$ spans $X$ in $M^*$.  Hence
$$r(X) + r^*(X) - |X| \le 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|{\rm cl}(A)$.  Suppose that $e$ exists. Then $r(M) = 5$ and $e \not \in {\rm cl}(A)-A$. Moreover, $e$ is either a coloop of $M|A$, or a member of $E(M) - {\rm cl}(A)$.  In the latter case, $e$ is a spoke of a type-2 fan whose set of spokes is disjoint from $F_i \cup F_j$; a contradiction to the fact that $|E(M)| = 9.$  In the former case, $\lambda_1(A,M) =2$, $\lambda_2(A,M) =3$, and $\beta(A,M) = 1$.  Hence $(M,A)$ is not a counterexample to Proposition~\ref{Proposition 2}; a contradiction.  We conclude that $e$ does not exist and so 
$Q_i =A$ and $E(M) - {\rm 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.
\end{proof}





The proof of Proposition \ref{Proposition 2} will involve constructing minimal pairs in minors of $M$.  The next result will be helpful in dealing with such minimal pairs.

\begin{lemma}
\label{Claim 2} 
If $(M\backslash X/Y,A - (X\cup Y))$ is a minimal pair such that $(X\cup Y)\cap(R_1\cup R_2 \cup\ldots\cup R_n)=\emptyset$, then 
$F_1\cup F_2 \cup \ldots\cup F_n\subseteq E(M\backslash X/Y)$. Moreover, if each 
element of $X\cap A$ is  parallel with some element of $A- (X\cup Y)$ 
in $M/Y$, then $R_i$ is contained in a $4$-circuit of 
$(M\backslash X/Y)|[A-(X\cup Y)]$.
\end{lemma}

\begin{proof} Lemma \ref{Claim 2} is trivial when $n=0$. Thus, by (\ref{E:(2)}), we may suppose that $n\ge 2$. 
By Lemma~\ref{disj_rim}, $R_1 \cap R_2 = \emptyset$. 
Thus $|E(M\backslash X/Y)|\ge 6$ 
since, by hypothesis, $(R_1 \cup R_2)\cap (X\cup Y)=\emptyset$. It follows, since $M\backslash X/Y$ is 3-connected, that it is simple and cosimple.

We now prove that $X\cap (F_1\cup F_2\cup \ldots\cup F_n)=\emptyset$. If not, then $X\cap F_i\not=\emptyset$ for some $i$, say $i=1$. Then, as $X$ avoids $R_1$, we may assume that $f_{10}\in X$.  Hence $a_{10}$ and $a_{11}$ are in series  in $M\backslash f_{10}$ and hence are coloops or are in series in $M\backslash X/Y$ because $(X\cup Y)\cap R_1=\emptyset$. This contradiction to the fact that $M\backslash X/Y$ is cosimple implies that  $X\cap (F_1\cup F_2 \cup \ldots\cup F_n)=\emptyset$.

Next suppose that $Y\cap F_i\not=\emptyset$ for some $i$, say $i=1$. Then we may assume that $f_{10}$ belongs to $Y\cap F_i$. In $M/f_{10}$, the elements  $f_{12}$ and $a_{11}$ are in parallel. But $M\backslash X/Y$ is simple and has 
  $a_{11}$ as an element. Thus $f_{12}\in X\cup Y$. As $f_{12}\not\in X$, by the previous paragraph, it follows that $f_{12}\in Y$. Hence $a_{11}$ is a loop of $M\backslash 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\ba 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\ba 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\ba X/Y$, the set $R_1$ is a triangle.  It follows that $M\ba X/Y$ must be isomorphic to a rank-3 wheel or whirl.  This is a contradiction since $n \neq 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\backslash X/Y)|[A-(X\cup Y)]$ containing $R_i$.  In the second case, if $Q_i \cap X = \{x\}$, then $\{x,a_i\}$ is a circuit of $M/Y$ for some $a_i$ in $A - (X \cup Y)$.  Thus $(Q_i - x) \cup a_i$ is a $4$-circuit of $(M\backslash X/Y)|[A-(X\cup Y)]$ containing $R_i$.
\end{proof}


The proof of Proposition \ref{Proposition 2} 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~\ref{Proposition 2} fails for $(M,A)$ but holds for $(M',A')$.
Therefore,
$$|A|+\lambda_1(A,M)+\lambda_2(A,M)-\beta(A,M)-|E(M)|<0$$
and 
$$|A'|+\lambda_1(A',M')+\lambda_2(A',M')-\beta(A',M')-|E(M')|\ge 0.$$
On taking the difference of the last two inequalities, we get
$$\delta_A+\delta_1+\delta_2-\delta_\beta-\delta_E<0,$$
where
\vspace{-0.7cm}
\begin{center}
\begin{eqnarray*}
\delta_E&=&|E(M)|-|E(M')|,\\
\delta_\beta&=&\beta(A,M)-\beta(A',M'),\\
\delta_A&=&|A|-|A'|,\\
\delta_1&=&\lambda_1(A,M)-\lambda_1(A',M'),\\
\delta_2&=&\lambda_2(A,M)-\lambda_2(A',M').\\
\end{eqnarray*}
\end{center}
\vspace{-0.3cm}
Hence, we shall get a contradiction whenever we can show that 
\begin{equation}
\label{(1)}
\delta_E+\delta_\beta\le\delta_A+\delta_1+\delta_2.
\end{equation}


The elementary proof of the next lemma is omitted.


\begin{lemma}
\label{Claim 2'} 
Suppose $\delta_\beta \ge 1$. Then $\delta_\beta = 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$.
\end{lemma}




Next we introduce some more notation. For every element $e$ of ${\rm cl}(A)- A$, let $N_e$ be the connected component of $M|(A\cup e)$ that contains $e$. Let ${\mathcal S}_e$ be the set of connected components of $N_e\backslash e$. The minimal pair $(M',A')$ that will replace $(M,A)$ will depend on some properties of ${\mathcal S}_e$. In particular, the proof will use the following lemma whose proof is straightforward.

\begin{lemma}
\label{Claim 3-} 
If $e\in {\rm cl}(A)- A$, then Proposition~\ref{Proposition 2} holds for the minimal pair $(M,A \cup e)$.
\end{lemma}

\begin{lemma}
\label{Claim 3} 
If $e\in {\rm cl}(A)- A$, then ${\mathcal S}_e$ does not contain a coloop of $M|A$ and hence $M|(A \cup e)$ has no $2$-cocircuits containing $e$.
\end{lemma}

\begin{proof} If $M|(A \cup e)$ has a 2-cocircuit, say $\{a,e\}$,  containing $e$, then $\{a,e\}$ is contained in the component, $N_e$, of $M|(A \cup e)$ containing $e$ and therefore $\{a\}$ is in ${\mathcal S}_e$.  Hence it suffices to show that ${\mathcal S}_e$ contains no coloops of $M|A$.  Assume the contrary.  Let $(M',A') = (M,A\cup e)$. By Lemma~\ref{Claim 3-},  Proposition \ref{Proposition 2} holds for the minimal pair $(M',A')$. Let $l$ be the number of coloops of $M|A$ that are not coloops of $M|(A\cup e)$. Clearly all these coloops must belong to ${\mathcal S}_e$.  Applying Lemma \ref{Lemma 6'}(i) for $N=M|(A\cup e)$, we get that
$$\delta_1+\delta_2\ge l.$$
Thus, as  $\delta_A=-1$ and $\delta_E=0$, we have 
$$\delta_A+\delta_1+\delta_2\ge \delta_E + (l-1).$$
By (\ref{(1)}), when
$\delta_\beta\le l-1$,
we arrive at a contradiction. Thus we may assume that $\delta_\beta\ge l$. But $l \ge 1$, and so, by Lemma \ref{Claim 2'}, 
$\delta_\beta= 1$ and so $1 \le l \le \delta_\beta = 1$. Therefore 
\begin{equation}
\label{(3.2)}
l= 1.
\end{equation}
Moreover, since $r(A\cup e)=r(A)$, we have $r(M) - r(A \cup e) =r(M)-r(A)$, and Lemma \ref{Claim 2'} implies that $A \cup e$ is a circuit of $M$.  Therefore all the connected components of $M|A$ are coloops and belong to ${\mathcal S}_e$. Thus $l = r(A)$ and so, by Lemma \ref{Claim 1}, $l \ge 3$; a contradiction to (\ref{(3.2)}). \end{proof}

The next part of the argument uses Bixby's result, Lemma \ref{bixby}. In particular, if $e \in {\rm cl}(A)- A$ and the simplification of $M/e$ is not $3$-connected, then the cosimplification of $M\de e$ is 3-connected. Lemma \ref{Claim 4} uses a minimal pair $(M',A')$, where $M'$ is this cosimplification, to yield the contradiction that Proposition \ref{Proposition 2} 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.

\begin{lemma}
\label{Claim 3'} 
$|A|\ge 5$.
\end{lemma}

\begin{proof} Suppose that $|A|\le 4$. By Lemma \ref{Claim 1}, $|A|\ge r(A)\ge 3$. Thus $|A|\in\{3,4\}$. It follows, by (\ref{E:(2)}) and Lemma~\ref{disj_rim}, that $A$ is a spanning set of $M$. 
Moreover, if $M|A$ has a coloop, $a$ say, then ${\rm cl}(A-a)$ is a hyperplane of $M$. Hence if $e \in {\rm cl}(A)-A$, then $\{a,e\}$ is a cocircuit of $M|(A \cup e)$.  This contradiction to Lemma \ref{Claim 3} implies that $M|A$ has no coloops.  It follows from this, since $M$ is simple and $|A| \le 4$, that $M|A$ is connected. Moreover, since $M|A$ is not 3-connected,  $M|A$ must be a 4-circuit. Thus $\lambda_1(A,M)+\lambda_2(A,M)-\beta(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\de 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 \ba f$ is $3$-connected; a contradiction.  Thus both lines have exactly three points and, since $|E(M)| \ge 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 \ba g$ is not the union of two 3-point lines; a contradiction.
 \end{proof}





\begin{lemma}
\label{Claim 4} 
Suppose that $e\in {\rm cl}(A)- A$.   Then every $2$-separation of $M/e$ is minimal.
\end{lemma}

\begin{proof} We begin by showing that 
\begin{equation}
\label{(4.1)}
|E(M)|\ge 7.
\end{equation}

Suppose that   (\ref{(4.1)}) fails. Then, since $|A| \ge 5$ by Lemma \ref{Claim 3'}, it follows that $|A|=5$ and $E(M)=A\cup e$. Thus $|A| - |E(M)| = -1$ and so, as 
$$|A|+\lambda_1(A,M)+\lambda_2(A,M)-\beta(A,M)-|E(M)|<0,$$
we have $\lambda_1(A,M)+\lambda_2(A,M) \le \beta(A,M) \le 2$. Since, by Lemma \ref{Lemma 15}(i), $\lambda_2(A,M) \ge 1$, we deduce that 
$\lambda_1(A,M)=\lambda_2(A,M)=1$. Thus $M|A$ is  3-connected. This contradiction completes the proof of (\ref{(4.1)}).

Assume that  $M/e$ has a non-minimal 2-separation. Then, by Lemma~\ref{bixby}, every 2-separation of $M\backslash e$ is minimal and the cosimplification of $M\de e$ is 3-connected. It follows, since $|E(M)|\ge 7$, that if $T^*_1,T^*_2,\dots,T^*_m$ are the triads of $M$ that contain $e$
and $T^*_i = \{e,a_i,b_i\}$, then $a_1,a_2,\ldots,a_m,b_1,b_2,\ldots,b_m$ are distinct.
 
Next, we shall prove the following:
\begin{sublemma}
\label{(4.3)} 
$\{a_i,b_i\}$  is a $2$-cocircuit of $M|A$ for all $i$ in $\{1,2,\ldots m\}$.
\end{sublemma}
As $e\in {\rm cl}(A)- A$,  orthogonality implies that $\{a_i,b_i\}$ meets the component $N_e$ of $M|(A \cup e)$ containing $e$.  Clearly $\{a_i,b_i\} \cap E(N_e \de e)$ is a union of cocircuits of $M|A$.  Thus (\ref{(4.3)}) holds, otherwise $a_i$ and $b_i$ are coloops  of $M|A$ so ${\mathcal S}_e$ contains a coloop of $M|A$ and we have a contradiction to Lemma \ref{Claim 3}. 

We shall prove next that 
\begin{sublemma}
\label{(4.4)}
$|T^*_i\cap (R_1 \cup R_2 \cup \ldots \cup R_n)| \le 1$ for all $i$. Moreover, if $T^*_i$ meets $R_1 \cup R_2 \cup \ldots \cup R_n$, then we may assume that $b_i \in R_1 \cup R_2 \cup \ldots \cup R_n$.
\end{sublemma}
Assume that this assertion fails. Then we may suppose that $b_i\in R_j$ and that $i=j=1$. Then, by orthogonality, $a_1 \in Q_1$. Hence  $a_1\in R_1$. Thus $T^*_1=(R_1 - a_{1k})\cup e$ for some $k$ in $\{0,1,2\}$.  But, by orthogonality with the triangle $T_{11}$, it follows that  $a_{11}\not\in T^*_1$.  Thus $T^*_1=\{e,a_{10},a_{12}\}$.

Let $D$ be a cocircuit of $M$ such that 
$$f_{10}\in D\subseteq (T_{10}\cup T_{12}) - \{a_{11}\}=\{f_{10},f_{12},a_{10},a_{12}\}.$$
Observe that $f_{12}\in D$, by orthogonality with $T_{11}$, and that $|D\cap\{a_{10},a_{12}\}|\not=1$,   by orthogonality with $Q_1$. As $|D|\ge 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\in D'\subseteq (D\cup T^*_1) - a_{10}=\{e,f_{10},f_{12},a_{12}\}.$$
By orthogonality with $Q_1$, it follows that $a_{12}\not\in D'$. But $|D'|\ge 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' \cap A = \emptyset$ contradicting (\ref{(4.3)}).  We conclude that $|T^*_i\cap (R_1 \cup R_2 \cup \ldots \cup R_n)| \le 1$ for all $i$. Finally, if $T^*_i$ meets $R_1 \cup R_2 \cup \ldots \cup R_n$, then we may relabel if necessary to ensure that $b_i \in R_1 \cup R_2 \cup \ldots \cup R_n$. Thus (\ref{(4.4)}) holds.





Now let $M'=M\backslash e/\{a_1,a_2,\dots,a_m\}$ and let $A'=A - \{a_1,a_2,\dots,a_m\}$. Then $M'$  is the cosimplification of $M\backslash 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'\de X/Y$.  By (\ref{(4.4)}), 
$R_1\cup R_2 \cup \ldots\cup R_n\subseteq E(M')\cap A=E(N')\cap A$. Thus, by Lemma \ref{Claim 2},  $F_1\cup F_2 \cup\ldots\cup F_n\subseteq E(N')$. Hence, by (ii) of the proposition, $X\cup Y\subseteq {\rm cl}(A)- A$. As $r_{M'}(A')=r_{N'}(A')$, we must have that $Y=\emptyset$. Hence, for some set $X$,  
$$N'=M'\backslash X.$$ 
 

Next we observe that 
\begin{sublemma}
\label{(4.5)}
$|E(N')|\ge 3$ with equality only if $E(N')=\{b_1,b_2,b\}$ where $b= b_3$, or $m=2$ and $b \in A$.
\end{sublemma}
Clearly $E(N') \supseteq A' \supseteq \{b_1,b_2, \ldots, b_m\}$ and $|A| = |A'| + m \le 2|A'|$.  But, by Lemma \ref{Claim 3'},  $|A| \ge 5$, so $|E(N')|\ge |A'| \ge 3.$ Moreover, if $|E(N')| = 3$, then $A' = E(N')$. Thus $5 \le |A| = 3 + m$, so $m \ge 2$ and $E(N')=\{b_1,b_2,b\}$ where $b=b_3$, or $m=2$ and $b\in A$.


We show next that 
\begin{sublemma}
\label{(4.51)}
$|E(N')|\ge 4.$
\end{sublemma}

Assume that this fails. Then, by (\ref{(4.5)}), $|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 2-separations of $M|A$ are those of the form 
 $\{\{a_i,b_i\},A - \{a_i,b_i\}\}$ for some $i$. Hence, as $e \in {\rm cl}(A)$ and $M$ is simple and 3-connected, $M|(A\cup e)$ is 3-connected unless, for some $i$, either (i) $e \in {\rm cl}(\{a_i,b_i\})$, or (ii) $e \in {\rm 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\cup e)$ is indeed 3-connected. Thus  $E(M)=A\cup e$ and we have a contradiction to the fact that $M$ is a counterexample to the proposition since $\lambda_1(A,M)=1,\lambda_2(A,M)\ge 2$, and $\beta(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 $\lambda_2(A,M)= |A| - 2$ and $\lambda_1(A,M)=\beta(A,M)=1$. Thus, as $M$ is a counterexample to the proposition,
\begin{equation}
\label{(4.52)}
|E(M)|\ge 2|A| - 1.
\end{equation}
For all $g$ in $E(M) - (A\cup e)$, the matroid $[M|(A \cup g)]^*$ has rank 2 and has $\{g\}$ as a parallel class.  Let ${\mathcal P}_g$ be the partition of $A$ induced by the other parallel classes of this matroid.  Then the series classes of $M|(A \cup g)$ are $\{g\}$ and the members of ${\mathcal P}_g$. Thus, for all $i$, the set $\{a_i,b_i\}$ is contained in some member of ${\mathcal P}_g$. When every member of ${\mathcal 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 \cup g)$ are those of the form 
 $\{\{a_i,b_i\},(A \cup g)- \{a_i,b_i\}\}$ for some $i$, and we argue as in the preceding paragraph to deduce that $M|(A\cup\{e,g\})$ is 3-connected. This contradicts (\ref{(4.52)}). Therefore, we may assume that, for every $g$,  there is a set in ${\mathcal P}_g$  with at least three elements. Then either (i) $b = b_3$, $|A| = 6$, and, for all $g$, the partition ${\mathcal 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 \neq b_3$, $|A| = 5$, and, for all $g$, the partition ${\mathcal 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 (\ref{(4.52)}), $|E(M) - (A \cup e)| \ge |A| -2$, we deduce that ${\mathcal P}_g = {\mathcal 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 (\ref{(4.51)}).

Recall that $M'=M\backslash e/\{a_1,a_2,\dots,a_m\}$, that $A'=A - \{a_1,a_2,\dots,a_n\}$, and that $N' = M' \de X$.  We shall prove next that $X=\emptyset$ and hence that 
\begin{sublemma}
\label{(4.6)}
$(M\backslash e/\{a_1,a_2,\dots,a_m\},A - \{a_1,a_2,\dots,a_n\})$ is a minimal pair for which Proposition~\ref{Proposition 2} holds. 
\end{sublemma}




Recall that $N'$ is 3-connected, $|E(N')| \ge 4$, and $M\de (X \cup e)$ is obtained from $N'$ by adding $a_i$ in series with $b_i$ for each $i$. Thus the only 2-separations of $M\de (X \cup e)$ are those of the form  $\{\{a_i,b_i\}, E(M)- (X \cup \{a_i,b_i\})\}$ for some $i$.  Hence, as $e \in {\rm cl}(A)$ and $M$ is simple, $M\de X$ is 3-connected unless, for some $i$, either  $e \in {\rm cl}(\{a_i,b_i\})$, or  $e \in {\rm cl}(E(M) - (X \cup \{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\de X$ is 3-connected so $X = \emptyset$. Hence $(M',A')$ is a minimal pair. Moreover, by Lemma~\ref{Claim 2}, $(M',A')$ satisfies the hypotheses, and hence the conclusion, of  Proposition~\ref{Proposition 2}.

We shall now complete the proof of Lemma \ref{Claim 4} by proving (\ref{(1)}).  Certainly 
$\delta_E=m+1$ and $\delta_A=m$. Now 
\vspace{-0.6cm}
\begin{center}
\begin{eqnarray*}
M'|A' & = & [(M\de e)/\{a_1,a_2,\ldots,a_m\}]|[A-\{a_1,a_2,\ldots,a_m\}]\\
	& = &(M|A)/\{a_1,a_2,\ldots,a_m\}.
\end{eqnarray*}
\end{center}
But, in $M|A$, for each $i$, the set $\{a_i,b_i\}$ is a cocircuit by (\ref{(4.3)}). 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 $\delta_2=m$ and $\delta_1=0$.  Hence, by (\ref{(1)}), we may assume that  $\delta_\beta\ge m$. Since $m \ge 1$, it follows by Lemma \ref{Claim 2'} 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 \ref{Claim 4}. \end{proof}

By Lemma \ref{Claim 4} and Bixby's lemma (\ref{bixby}), if $e\in {\rm 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.
\begin{lemma}
\label{Claim 3''} 
Suppose that $e\in {\rm 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 
\begin{enumerate}
\item[(i)] $A =A_e$; or
\item[(ii)] $|A -A_e| = 1$ and $|{\mathcal S}_e|\ge 2$; or
\item[(iii)] $M|A_e$ has a circuit  that spans $e$.
\end{enumerate}
Then $(M/e\de (A- A_e), A_e)$ is a minimal pair for which Proposition~\ref{Proposition 2} holds. 
\end{lemma}

\begin{proof} By Lemma \ref{Claim 4}, 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\de (\tilde{X} \cup (A - A_e))$   for some subset $\tilde{X}$ of ${\rm 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

\begin{sublemma}
\label{(3.0)}
$R_1\cup R_2\cup\ldots\cup R_n\subseteq E(N')$.
\end{sublemma}

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 ${\rm cl}(A)$ but must be different from $T_{i1}$, yet $F_i$ is a type-2 fan of length three.  Hence (\ref{(3.0)}) holds.

By (\ref{(3.0)}) and Lemma \ref{Claim 2}, 
$F_1\cup F_2\cup\ldots\cup F_n\subseteq E(N')$. Hence, by (ii) of the proposition, if $N' = M'\de X/Y$, then $Y\subseteq {\rm cl}(A)- A$. As $r_{N'}(A_e)=r_{M'}(A_e)=r_{M/e}(A)$, it is not difficult to check  that $Y=\emptyset$. Hence   
$$N'=M'\backslash X.$$ 

Let $H=M\backslash (X \cup \tilde{X})$.  Then one easily checks that $E(H) \supseteq A$. Moreover,  by the hypotheses, we have   
\begin{enumerate}
\item[(i)] $A_e = A$ and $N' = H/e$; or 
\item[(ii)] $|{\mathcal S}_e|\ge 2$, the set $A_e = A - a$ for some element $a$ of $A$, and $N' = H/e\backslash a$; or 
\item[(iii)] $M|A_e$ has a circuit  that spans $e$, and $N' = H/e\de (A-A_e)$. 
\end{enumerate}
We shall prove next that, in all  cases,
\begin{sublemma}
\label{(3.1)}
$H$ is $3$-connected.
\end{sublemma}

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\cup e)$, which equals $M|(A\cup e)$. It cannot be a coloop because $A$ spans $e$, and it cannot be in series by Lemma \ref{Claim 3}.  Hence (\ref{(3.1)}) holds in case (i).

Now suppose that (ii) holds. Since $H$ is a restriction of $M$, if 
$H\backslash 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\de a$ is not $3$-connected. But  $H\backslash a/e$ is 3-connected, so either $e$ is a coloop of $H \de a$, or $e$ is in series with some element $b$ of $H \de a$.  In the first case, $e$ is a coloop of $H|[(A -  a)\cup e]$. Since this matroid equals $M|[(A -  a)\cup e]$ and $A$ spans $e$, it follows that $\{a,e\}$ is a cocircuit of $M|(A \cup e)$ and we have a contradiction to Lemma \ref{Claim 3}. Thus we may assume that $\{e,b\}$ is a cocircuit of $H\de a$.  Moreover $\{e,b\}$ is a cocircuit of $H|[(A -  a)\cup e]$, otherwise $e$ would be a coloop of $H|[(A -  a)\cup e]$, that is, of $M|[(A -  a)\cup e]$, and we arrive at a contradiction as before. Thus $b$ and $e$ are in series in $M|[(A -  a)\cup e]$. By Lemma \ref{Claim 3}, $b$ and $e$ cannot be in series in $M|(A\cup e)$. Therefore $\{e,a,b\}$ is a triad of $M|(A\cup e)$, that is, of $H|(A\cup e)$. Since $\{e,b\}$ is a cocircuit of $H\de 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\backslash a/e$ is 3-connected and, by Lemma~\ref{Claim 3'}, $|E(H\backslash a/e)| \ge |A - a| \ge 4$, it follows that 
the only 2-separation of $H\backslash 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\cup e)$ having both $a$ and $b$ in the same connected component of $M|A$ which is contrary to Lemma \ref{Claim 4'} since, by assumption, $|{\mathcal S}_e|\ge 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 (\ref{(3.1)}) holds in case (ii).

It remains to consider case (iii). In that case, since $H/e\de (A-A_e)$ is 3-connected, $H\de (A-A_e)$ is also 3-connected unless $e$ is a coloop or in series in $H\de (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\de (A-A_e)$ is indeed 3-connected. As $A_e \cup e$ spans $A - A_e$ in $H$, it follows that $H$ is 3-connected.  Thus (\ref{(3.1)}) holds in case (iii). 



By (\ref{(3.1)}) and  the choice of $M$, it follows that $X \cup \tilde{X} = \emptyset$.  Thus $N' =M'$ so $M' = M/e\de (A-A_e)$ and  we deduce that, $(M/e\de (A-A_e), A_e)$ is a minimal pair. Moreover, by Lemmas~\ref{Claim 3'} and \ref{Claim 2}, this minimal pair satisfies the hypotheses, and hence the conclusion, of Proposition~\ref{Proposition 2}.
\end{proof}

With a view to using the minimal pair $(M,A \cup e)$, the next result establishes that $\lambda_1(A,M) = \lambda_1(A \cup e,M)$ for all $e \in {\rm cl}(A)- A$. Recall that $N_e$ is the component of $M|(A \cup e)$ that contains $e$, and ${\mathcal S}_e$ is the set of components of $N_e \ba e$. 

\begin{lemma}
\label{Claim 5} 
If $e\in {\rm cl}(A)- A$, then $|{\mathcal S}_e|=1$, that is, $N_e \de e$ is connected.
\end{lemma}

\begin{proof} Assume that $|{\mathcal S}_e|\ge 2$. Then  $N_e \de e$ is disconnected.    Thus, by Lemma \ref{Claim 4'}, $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'\} \subseteq A$ and we may assume that $A_e = A - a$. Thus, by Lemma \ref{Claim 3''}, either $(M/e,A)$ or $(M/e\de a,A-a)$ is a minimal pair $(M',A')$ satisfying Proposition~\ref{Proposition 2}.

Clearly $\delta_A=k$ for some $k$ in $\{0,1\}$ and $\delta_E=k+1$. Consider $N_e$ again.  Since $|{\mathcal S}_e|\ge 2$, we have $\lambda_1(M|(A \cup e))<\lambda_1(M|A)$. By Lemma~\ref{Claim 3}, $N_e$ is not a triangle.  Hence  $r(N_e/e) \ge 2$. 
Thus, by Lemma \ref{Lemma 6'}(ii),
\begin{equation}
\label{(5.21)}
\lambda_1(M|A)-\lambda_1([M|(A \cup e)]/e)+\lambda_2(M|A)-\lambda_2([M|(A \cup e)]/e)
\ge 1.
\end{equation}
But $M'|A'$ is either $(M/e)|A$ or $(M/e)|(A-a)$, that is, $[M|(A\cup e)]/e$ or 
$[M|(A\cup e)]/e\de a$.  In the first case,  we have, by (\ref{(5.21)}), that
\begin{equation}
\label{(5.22)}
\delta_1+\delta_2\ge 1.
\end{equation}
In the second case, $[M|(A\cup e)]/e$ is obtained from $[M|(A\cup e)]/e\de a$ by adding $a$ in parallel to $a'$.  As $r(N_e/e) \ge 2$, it follows by Lemma~\ref{Lemma 1'} that $\lambda_2([M|(A\cup e)]/e) = \lambda_2([M|(A\cup e)]/e\de a)$.  Thus  
$$\lambda_1([M|(A\cup e)]/e)+\lambda_2([M|(A\cup e)]/e)=\lambda_1([M|(A\cup e)]/e\de a) + \lambda_2([M|(A\cup e)]/e\de a)$$
and so (\ref{(5.22)}) holds when $M'|A' = [M|(A\cup e)]/e\de a$.  It now follows that  
 $\delta_\beta \ge 1$ otherwise we obtain a contradiction by (\ref{(1)}).  Thus  Lemma \ref{Claim 2'} implies that $\delta_\beta = 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)\cup e$, or $A \cup e$ is a circuit of $M$.  The last possibility leads to a contradiction to Lemma \ref{Claim 3}. If $A-a$ is a circuit of $M$, then  it follows, since $|{\mathcal S}_e|\ge 2$, that $\{a,e\}$ is a cocircuit of $M|(A \cup e)$ and again we have  a contradiction to Lemma \ref{Claim 3}.  We may now assume that $(A-a) \cup e$ is a circuit of $M$ and $M|(A \cup e)$ has no 2-cocircuit containing $e$.  Then $[M|(A \cup 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 \ref{Claim 5}. \end{proof}




\begin{lemma}
\label{Claim 6} 
For each $e$ in ${\rm cl}(A)- A$, 
$$\lambda_2(A,M) = \lambda_2(A \cup e,M).$$
Moreover, either  
\begin{enumerate}
\item [(i)] there is a matroid $H$ in $\Lambda_2(N_e)$ that is isomorphic to $U_{1,3}$ such that $e\in E(H)$ and $N_e\not=H$; or 
\item [(ii)] there are matroids $H_1$ and $H_2$ in $\Lambda_2(N_e)$ that are isomorphic to $U_{2,4}$ and  $U_{2,3}$, respectively,  
such that $e\in E(H_1)$ and $E(H_1)\cap E(H_2)$ is non-empty. 
\end{enumerate}
\end{lemma}

\begin{proof} Let $(M',A') = (M, A \cup e)$.  Then, by Lemma~\ref{Claim 3-},  the proposition  holds for the minimal pair $(M',A')$. Let $M_1,M_2,\dots,M_k$ be the  components of $M|(A\cup e)$ where  $M_k=N_e$. Then the components of $M|A$ are $M_1,M_2,\ldots,M_{k-1},M_k\backslash e$  since, by Lemma \ref{Claim 5}, $N_e \de e$ is connected. Hence $\delta_1=0$. Moreover, it is not difficult to see that 
$$\delta_2=\lambda_2(A,M)-\lambda_2(A\cup e,M)
                =\lambda_2(N_e\backslash e)-\lambda_2(N_e).$$

Now suppose that 
$\lambda_2(A,M) >\lambda_2(A \cup e,M).$ 
Then  $\delta_2 \ge 1$. 
We also have that $\delta_E=0$ and $\delta_A=-1$. It follows by  (\ref{(1)})  that  $\delta_\beta=1$ otherwise we get a contradiction.  Thus, by Lemma \ref{Claim 2'}, $A\cup e$ is a circuit of $M$ and so $M|(A\cup e)$ has a 2-cocircuit containing $e$; a contradiction to Lemma \ref{Claim 3}.  We conclude that $\lambda_2(A,M) \le \lambda_2(A \cup e,M)$ and so 
$$\lambda_2(N_e\de e)\le \lambda_2(N_e).$$

Lemma \ref{Lemma 5}(i) now implies that $\lambda_2(N_e)=\lambda_2(N_e\backslash e)$. Hence $\lambda_2(A,M) = \lambda_2(A \cup e,M).$ Furthermore, it follows by Lemma \ref{Lemma 5}(ii) that to complete the proof that (i) or (ii) holds, it suffices to show that $e$ destroys some 2-separation of $N_e\de e$.  Since $(M,A)$ is a minimal pair, $M\de e$ has a  2-separation $\{X,Y\}$, say,  and this 2-separation is destroyed by $e$. Thus $\{X\cap E(N_e\de e), Y\cap E(N_e\de e)\}$ is a 2-separation of $N_e \de e$ that is destroyed by $e$ provided that both $|X\cap E(N_e\de e)|$ and $|Y\cap E(N_e\de e)|$ exceed one.  But if $|X\cap E(N_e\de e)| \le 1$, then $Y\cap E(N_e\de e)$ spans $e$, so $Y$ spans $e$ in $M$; a contradiction.  Hence $|X\cap E(N_e\de e)|\ge 2$ and, similarly, 
$|Y\cap E(N_e\de e)|\ge 2$. We conclude that $\{X\cap E(N_e\de e), Y\cap E(N_e\de e)\}$ is a 2-separation of $N_e \de e$ that is destroyed by $e$, and the lemma follows. \end{proof}

In the last part of the argument proving Proposition \ref{Proposition 2}, we shall use Lemma \ref{Lemma 7''}, 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 \ref{Lemma 7''} holds.

\begin{lemma}
\label{Claim 7} Every element $e$ of ${\rm 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$.
\end{lemma}

\begin{proof} Suppose that Lemma \ref{Claim 7} fails for the element $e$. By Lemma \ref{Claim 6}, we have the following two cases to deal with. 
\begin{enumerate}
\item[(I)] There  is a matroid $H$ in $\Lambda_2(N_e)$ that is isomorphic to $U_{1,3}$ such that $e\in E(H)$.
\item[(II)] There are matroids $H_1$ and $H_2$ in $\Lambda_2(N_e)$ that are isomorphic to $U_{2,4}$ and  $U_{2,3}$, respectively,  
such that $e\in E(H_1)$ and $E(H_1)\cap E(H_2)$ is non-empty. 
\end{enumerate}
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 \ref{Claim 3''},
$(M/e\backslash (A-A_e), A_e)$ is a minimal pair for which Proposition~\ref{Proposition 2} holds. 
Since $\delta_E=\delta_A+1$, it follows by (\ref{(1)}) that it suffices to prove, in both cases, that 
\begin{equation}
\label{first}
\delta_1+\delta_2\ge 1
\end{equation}
and 
\begin{equation}
\label{second}
\delta_\beta\le 0.
\end{equation}


Assume that (I)  occurs. Then $N_e/e$ is disconnected and, by Lemma \ref{Lemma 7}, 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 \cup e)$ and
$N_e|(Y \cup e)$. 
Let $\{V,W\}$ be a 2-separation of $M\backslash 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\cap E(N_e)$ and $Y'=W\cap E(N_e)$. Then 
$|X'| = |V \cap X| + |V \cap Y| \ge 2$, and, similarly, $|Y'| \ge 2$. Hence 
$\{X',Y'\}$ is a 2-separation of $N_e\backslash e$. Moreover, 
$\{X,Y\}$ is also a 2-separation of $N_e\backslash e$.
Let
$${\mathcal F}(N_e \ba e)=\{X\cap X',X\cap Y',Y\cap X',Y\cap Y'\}.$$
Clearly $|{\mathcal F}(N_e \ba e)| = 4$. Next we observe that $\min\{|X|,|Y|\}\ge 3$.  To see this, note that if, say, $|X|=2$, then 
 $X\cup\{e\}$ is a triangle of $M$ and $X$ is contained in a series class of $M|A$; a contradiction to the assumption that Lemma \ref{Claim 7} 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 \cup e)$. Now  $|{\mathcal F}(N_e \ba e)| = 4$. 
Since $N_e/e$ has exactly two components, it follows, by Lemma~\ref{Lemma 1}, that $J(N_e \ba e)$ is a $4$-circuit.  Therefore, 
 $N_Z\backslash e$ is disconnected for each $Z$. Since $N_Z$ is connected, Lemma \ref{Claim 4'} implies that each $N_Z$ has at most one triangle $T_Z$ such that $e\in T_Z$, and $T_Z - e\subseteq Z\cap A$. As $|Z|\ge 3$, at least one of $Z\cap X'$ and $Z\cap Y'$ has more than one element. By Lemma \ref{Claim 4'}, when $T_Z$ exists, it has an element $a_Z$ such that $N_Z \de 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 \cap E(N_e)) \cup e]$ is the parallel connection, with basepoint $e$,  of $N_X|[(A_e\cap E(N_X))\cup e]$  and $N_Y|[(A_e\cap E(N_Y))\cup e]$. 
Since each of the last two matroids is connected, it follows that 
$N_e|[A_e \cap E(N_e)]$  has a circuit  spanning  $e$. Hence, by Lemma \ref{Claim 3''}, $(M/e\backslash (A-A_e), A_e)$ is a minimal pair, $(M',A')$, for which Proposition~\ref{Proposition 2} holds. 

Observe that the sets of connected components of $M|A$ and $M'|A_e$ coincide except for those meeting $E(N_e)$.  Thus 
$\delta_1=-1$ since $N_e$ is a component of $M|A$ whereas $N_e/e \ba (A - A_e)$ has exactly two connected components. Next we note that, since Lemma \ref{Claim 7} fails for $e$, Lemma \ref{Lemma 1''} implies that 
$$\lambda_2(N_e\de e) = \lambda_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 $\lambda_2(N_e/ e)= \lambda_2(N_e/e \ba (A - A_e))$. 
Thus $\lambda_2(N_e\de e) = \lambda_2(N_e/e \ba (A - A_e)) + 2$, so $\delta_2=2$ and (\ref{first}) holds. Assume that (\ref{second}) fails, that is, 
 $\delta_\beta\ge 1$. Then, by Lemma \ref{Claim 2'}, $A_e$ is a circuit of $M'$. But this is a contradiction since $M'|A_e$ has at least two connected components. Hence both (\ref{second}) and (\ref{first}) 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 $\Lambda_2(N_e)$, and $N_e$ is the 2-sum, with basepoint $f$, of two matroids $K_1$ and $K_2$, where $H_i \in \Lambda_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 $\Lambda_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\de f$. Since $H_1$ is a 4-point line containing $e$ and $f$, we see that $H_1\de f$ is connected and $H_1\de f\de 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\de f$ is connected and  $K_1\de f\de e$ is disconnected. Hence, by Lemma \ref{Claim 4'}, $K_1 \de f$ has at most one triangle containing $e$.  Thus $N_e/e$ has at most one non-trivial parallel class meeting $E(K_1\de f)$ and this class has at most two elements.  Therefore, either (i) we can choose $A_e = A$, or (ii) $K_1 \de f$ has a triangle $T$ containing $e$ and $T -e \subseteq A$.  Consider the second case. We may assume that $K_1 \neq 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 \ba f)| \neq 3$.  Therefore, by  Lemma \ref{Claim 4'}, $T-e$ contains an element $a$ of $A$ such that $K_1 \de f \de a$ is connected.  Since $K_1 \de e \de a$ is isomorphic to $K_1 \de f \de a$ under the map that takes $f$ to $e$ and fixes every other element, $K_1 \de e \de a$ is connected. Therefore 
 $N_e\backslash\{e,a\}$ is connected since it is the 2-sum, with basepoint $f$, of $K_1 \de e \de a$ and $K_2$.  Thus, in case (ii), we can choose $A_e = A - a$ and check that $N_e|(A_e\cap E(N_e))$ has a circuit spanning $e$.  We deduce that either 
\begin{enumerate}
\item[(i)] $A_e =A$; or 
\item[(ii)] $A_e = A-a$ and $\{a,e,a'\}$ is a triangle of $M$ for some $a'$ in $A$.
\end{enumerate}
In both cases, by Lemma \ref{Claim 3''}, $(M/e\backslash (A-A_e), A_e)$ is a minimal pair, $(M',A')$, satisfying Proposition~\ref{Proposition 2}.


Now $N_e/e$ is connected. Thus $M|A$ and $M'|A'$ have the same number of connected components. Hence 
$$\delta_1 = 0.$$

Next consider $\delta_2$. 
Let $M_1,M_2,\dots,M_k$ be the connected components of $M|(A\cup e)$ where $N_e = M_k$. As $e\in E(H_1)$ and both $H_1\backslash e$ and $H_1/e$ are 3-connected,  
\begin{equation}
\label{(7.1)}
\Lambda_2(N_e\backslash e)=(\Lambda_2(N_e) - \{H_1\})\cup\{H_1\backslash e\}  \end{equation}
and
\begin{equation}
\label{(7.1')}
\Lambda_2(N_e/e)=(\Lambda_2(N_e) - \{H_1\})\cup\{H_1/e\}.
\end{equation}

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 $\lambda_2(N_e/ e)= \lambda_2(N_e/ e\ba (A - A_e))$.
As $M_1,M_2,\dots,M_{k-1}$ are connected components of  both $M|A$ and $M'|A'$, it follows that
$$\delta_2=\lambda_2(A,M)-\lambda_2(A_e,M')=\lambda_2(N_e\backslash e)-\lambda_2(N_e/e).$$
Thus, $$\delta_2=1,$$ 
by (\ref{(7.1)}) and (\ref{(7.1')}), because $H_1\backslash e$ is isomorphic to $U_{2,3}$, and therefore contributes one to $\lambda_2(N_e\backslash e)$, and $H_1/e$ is isomorphic to $U_{1,3}$ and so does not contribute to $\lambda_2(N_e/e)$. 

We now know that $\delta_1+\delta_2 = 1$, that is, (\ref{first}) holds.  Assume that (\ref{second}) fails, that is,  $\delta_\beta \ge 1$. Then, by Lemma \ref{Claim 2'}, $A_e$ is a circuit of $M'$ but $A$ is not a circuit of $M$.  Thus one of $A-a, (A-a) \cup e$, or $A \cup e$ is a circuit of $M$.  The third possibility contradicts Lemma \ref{Claim 3}.  In the other two cases, $\{a,a',e\}$ is a triangle of $M$.  If $(A-a) \cup e$ is a circuit of $M$, then, from considering $[M|(A \cup e)]^*$, it is not difficult to see that $\{a',e\}$ is a cocircuit of $M|(A\cup e)$, again contradicting Lemma \ref{Claim 3}. 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) \cup e]$. But the circuit $\{a,a',e\}$ now implies that $\{a,e\}$ is a cocircuit of $M|(A\cup e)$.  This contradiction to Lemma \ref{Claim 3} completes the proof that (\ref{second}) holds in case (II) and thereby finishes the proof of Lemma \ref{Claim 7}. \end{proof}

We shall use the last lemma to show, in Lemma \ref{Claim 9}, that $A$ is non-spanning.  The next lemma proves a preliminary step towards this goal,

\begin{lemma}
\label{Claim 8} 
If ${\rm cl}(A)=E(M)$, then $A$ is a circuit.
\end{lemma}

\begin{proof} As $E(M) -A \neq \emptyset$, it follows from Lemma \ref{Claim 7} that $M|A$ has a non-trivial series class $S$.  If $S =A$, then the result is immediate.  Hence we may suppose that $S \neq 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 $\{{\rm cl}(S),E(M) -{\rm cl}(S)\}$ is a 1- or 2-separation of $M$;  a contradiction.  
\end{proof}

\begin{lemma}
\label{Claim 9} 
$E(M) -  {\rm cl}(A)\not=\emptyset$.
\end{lemma}

\begin{proof} Suppose that $A$ is spanning. Then, by Lemma \ref{Claim 8},  $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 \ref{Lemma 7''}. As $M$ is 3-connected, Lemma \ref{Claim 7} and Lemma \ref{Lemma 7''} 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\de e$ is not 3-connected, so $G(A,M\de e)$, which equals 
$G(A,M)\de 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 
$$\lambda_1(A,M) + \lambda_2(A,M) -\beta(A,M) = 1 + (|A| -2) - 1 = |A| -2,$$ 
and we obtain a contradiction since it follows that $(M,A)$ does satisfy the proposition. \end{proof} 


Let $S_1,S_2,\dots,S_m$ be the non-trivial series classes of $M|A$. The following lemma, whose proof is heavily based on Lemma \ref{Lemma 7''}, will quickly yield a final contradiction, namely that $(M,A)$ is not a counterexample to the proposition.
\begin{lemma}
\label{Claim 10} 
There is a partition $P_1,P_2,\dots,P_m$ of  $E(M) -  A$ such that
$$|P_i|\le\left\{
\begin{tabular}{ll}
\hbox{$|S_i|-2,$}&\hbox{when $S_i$ is a circuit of $M|A$;}\\
\hbox{$|S_i|-1,$}&\hbox{when $S_i$ is not a circuit of $M|A$.}\\
\end{tabular}\right.
$$
\end{lemma}

\begin{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) - {\rm cl}(A)$ is contained in one of the fans, $F_t$, 
 it only remains to partition ${\rm cl}(A)- A$. 

By Lemma \ref{Claim 7}, each element of ${\rm 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 \ref{Lemma 7''} has vertex set $A$ and edge set ${\rm cl}(A)- A$.  Let $G_1,G_2,\ldots,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) \subseteq S_i$.  We now abbreviate $V(G_j)$ and $E(G_j)$ as $V_j$ and $E_j$, respectively.

First we show the following:
\begin{sublemma}
\label{(10.1)}
For all $j$, the set $V_j$ is not a circuit of $M|A$.
\end{sublemma}

Suppose that $V_j$ is a circuit of $M|A$ for some $j$.  Then $|V_j| \ge 3$.  Assume that $|V_j| = 3$.  Then $V_j$ is a triangle of $M$ and so, if $e \in E_j$, then $M|(V_j \cup e)$ is a 4-element simple rank-2 matroid and so is isomorphic to $U_{2,4}$. Hence $M\de e$ is 3-connected; a contradiction to the fact that $(M,A)$ is a minimal pair.  We may now assume that $|V_j| \ge 4$.  Consider the matroid $M_j = M|(V_j \cup E_j)$. The graph $G(V_j,M_j)$ coincides with the connected graph $G_j$ and so, by Lemma \ref{Lemma 7''}, $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\ba 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 \de e$ has two components, one an isolated vertex.  Since $G_j \de e = G(V_j,M_j \de e)$, Lemma \ref{Lemma 7''} implies that $M_j \de 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 \de e$ is connected and  Lemma \ref{Lemma 7''} again implies that $M_j \ba e$ is 3-connected.

Consider $M\de e$.  It has a 2-separation $\{X,Y\}$.  Since $\{X \cap E(M_j), Y \cap E(M_j)\}$ is not a 2-separation of $M_j$, we may assume that $|X \cap E(M_j)| \le 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 \cap E(M_j)$ and $Y \cap E(M_j)$. Thus $X \cap E(M_j) = \{a\}$ for some $a$ in $T_e - e$.  Hence $V_j \cap Y \cap 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 (\ref{(10.1)}).

Most of the rest of the proof of Lemma \ref{Claim 10} will be devoted to proving the following:
\begin{sublemma}
\label{(10.2)}
For all $j$, the graph $G_j$ is a tree.
\end{sublemma}

If $|E_j| = 1$, then (\ref{(10.2)}) certainly holds.  Thus we may assume that $|E_j| \ge 2$.  Let $C$ be a circuit of $M|A$ that contains $V_j$.  By (\ref{(10.1)}), $C \neq V_j$.  As a step towards (\ref{(10.2)}), we now prove that 
\begin{sublemma}
\label{(10.3)}
$C - V_j$ is contained in a series class of $M|(C \cup E_j)$.
\end{sublemma}

To see this, note first that $M|(C \cup E_j)$ is connected since it has $C$ as a spanning circuit.  Hence $r(M|(C \cup E_j)) = |C| - 1$.  Consider the partition $\{V_j, C - V_j\}$ of $C$.  Certainly $|V_j| \ge 2$.  Moreover, we may assume that $|C- V_j| \ge 2$ otherwise (\ref{(10.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 \cup E_j)) = |C| = |V_j| + |C-V_j| = r(V_j) + r(C-V_j) = 
r(V_j \cup E_j) + r(C - V_j).$$
Thus $\{V_j \cup E_j, C - V_j\}$ is a 2-separation of $M|(C \cup 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 \cup E_j)$ is connected, we conclude that (\ref{(10.3)}) holds.

Now, for each $c$ in $C-V_j$, define  
$$H_c = [M|(C \cup E_j)]/ [C -  (c \cup V_j)],$$ 
noting that (\ref{(10.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 
\begin{sublemma}
\label{(10.4)}
$H_c$ is $3$-connected.
\end{sublemma} 

Consider $G(V_j \cup 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 \cup c$ of vertices.  As $|E_j| \ge 2$, we have $|V_j| \ge 3$, so $|V_j \cup c| \ge 4$.  We show next that $H_c$ is simple.  This follows by (\ref{(10.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) \cup z$ is a circuit of $M$.  Since this circuit cannot properly be contained in $C$, it follows that $z \in E_j$. Let $a$ and $b$ be the end-vertices of $z$ in $G(V_j \cup c, H_c)$.  Then $\{a,b,z\}$ is a circuit of $M$.  Hence, by circuit elimination, $\{a,b\} \cup (C - V_j)$ contains a circuit of $M$ that, since $|V_j| \ge 3$, is properly contained in $C$.  This contradiction completes the proof that $H_c$ is simple.  But $G(V_j \cup c, H_c)$ has two components, one of which consists of the isolated vertex $c$.  We may now apply Lemma \ref{Lemma 7''} to deduce that  (\ref{(10.4)}) holds.   

We now show that, for all $e$ in $E_j$,
\begin{sublemma}
\label{(10.5)}
$H_c\de e$ is not $3$-connected.
\end{sublemma}
 
Suppose that $H_c\de e$ is  $3$-connected for some $e$.  Then, as $M\de e$ has a 2-separation $\{X,Y\}$ but $\{X\cap E(H_c),Y\cap E(H_c)\}$ cannot be a 2-separation of $H_c \de e$, we may assume that $|X \cap E(H_c)| \le 1$. Then, as $T_e - e$ meets both $X$ and $Y$, it follows that $X \cap E(H_c) = \{a\}$ for some $a$ in $T_e -e$.

We observe next that 
$$C - V_j \not \subseteq Y,$$
for, if $C-V_j \subseteq Y$, then, as $X \cap E(H_c) = \{a\}$, it follows that $C - a \subseteq Y$.  Hence $Y$ spans $C$ and so spans $e$; a contradiction. We conclude that $(C - V_j) \cap X$ contains an element $d$.  Then, as $X \cap E(H_c) = \{a\}$, we deduce that $X \cap E(H_d) = \{d,a\}$. Hence $\min\{|X \cap E(H_d)|,|Y \cap E(H_d)|\} \ge 2$ and so $\{X \cap E(H_d),Y \cap E(H_d)\}$ is a 2-separation of $H_d \de e$.  The isomorphism between $H_d \de e$ and $H_c \de e$ that maps $d$ to $c$ and fixes every other element implies that $H_c \de e$ is not 3-connected.  Hence (\ref{(10.5)}) holds.

The graph $G(V_j \cup c, H_c)$ is the disjoint union of $G_j$ and the isolated vertex $c$.  Moreover, since, by (\ref{(10.5)}), $H_c \de e$ is not 3-connected, Lemma \ref{Lemma 7''} implies that $G(V_j \cup c, H_c\de e)$ which equals $G(V_j \cup c, H_c)\de e$,must have more than two components.  Thus $G_j \de e$ is disconnected for all $e$ in $E_j$, and (\ref{(10.2)}) follows.

To complete the proof of Lemma \ref{Claim 10}, 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 \subseteq S_i$. Thus 
$$|P_i| = \sum_{V_j\subseteq S_i}|E_j|.$$
But 
$$|S_i| = \sum_{V_j\subseteq 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 \subseteq S_i$, then 
$$|P_i| = \sum_{V_j\subseteq S_i}(|V_j|-1) = |S_i| - p - |S'_i|.$$ 
The inequality in Lemma \ref{Claim 10} certainly holds if $p + |S'_i| \ge 2$, so assume that $p + |S'_i| \le 1$.  Then $|S'_i| = 0$ and $S_i = V_j$ for some $j$.  But, in this case, by (\ref{(10.1)}), $S_i$ is not a circuit of $M|A$ and again the desired inequality holds. \end{proof}



We are now able to complete the proof of Proposition \ref{Proposition 2} and hence that of Theorem \ref{Theorem 1}.

Clearly we may adjust the labelling so that $S_1,S_2,\ldots,S_t$ are circuits and $S_{t+1},\linebreak
S_{t+2},\ldots,S_m$ are not.  Then $M|A$ is the direct sum of 
$M|S_1,M|S_2,\ldots,M|S_t$, and $M|[A - (S_1 \cup S_2\cup \ldots \cup 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,\ldots,|S_m| + 1$.  Thus, by Lemma \ref{Claim 10}, there is a partition $P_1,P_2,\dots,P_m$ of  $E(M) -  A$ such that
$$|P_i|\le\left\{
\begin{tabular}{ll}
\hbox{$|S_i|-2,$}&\hbox{when $1\le i \le t$;}\\
\hbox{$|S_i|-1,$}&\hbox{when $t+1\le i \le m$.}\\
\end{tabular}\right.
$$
Since, for every  circuit $C$ with at least three elements, we have $\lambda_2(C) = |C| - 2$, it follows that 
\vspace{-0.8cm}
\begin{center}
\begin{eqnarray*}
\lambda_1(A,M) + \lambda_2(A,M)&=&\sum_{i=1}^{t} \lambda_1(S_i,M) + \sum_{i=1}^{t} \lambda_2(S_i,M) + \lambda_1(A -\bigcup_{i=1}^{t} S_i,M)\\
& & \hspace{4.5cm} + \lambda_2(A-\bigcup_{i=1}^{t} S_i,M)\\
&\ge &t+ \sum_{i=1}^{t}(|S_i| - 2) + 1 + \sum_{i=t+1}^{m}(|S_i| - 1)\\
&\ge &t+1 + \sum_{i=1}^{m}|P_i|\\
&=& t+1 + |E(M) -A|.
\end{eqnarray*}
\end{center}
But, by Lemma \ref{Claim 9}, $\beta(A,M) = 1$.  Since $t \ge 0$, we obtain the contradiction that $(M,A)$ is not a counterexample to the proposition thereby completing the proof of Proposition \ref{Proposition 2}. \hfill $\square$

\medskip

\noindent{\it Proof of Theorem \ref{Theorem 1}.}  Observe that $(M,A)$ is a minimal pair where $M\not \cong U_{1,3}$ and $A$ is non-empty and spanning.  Then $(M,A)$ satisfies the hypotheses of Proposition \ref{Proposition 2}.  Hence if $A$ is not a circuit, then 
$$|E(M)|\le |A|+\lambda_1(A,M)+\lambda_2(A,M)-2,$$ 
while, if $A$ is a circuit, then 
$$|E(M)|\le |A|+\lambda_1(A,M)+\lambda_2(A,M)-1.$$
But, in the latter case, $\lambda_1(A,M) = 1$ and either   $|A|\ge 4$ and $\lambda_2(A,M) = |A| - 2$, or $|A| \in \{1,2,3\}$.   The first possibility  implies that $|E(M)| \le 2|A| - 2$ as required. The second possibility implies that $M =M|A$ so $|E(M)| \le |A|+\lambda_1(A,M)+\lambda_2(A,M)-2$. 
\hfill $\square$


\section{Proof of Theorem 5}

In this section, we show that Theorem \ref{Theorem 1} is best-possible by proving Theorem \ref{Theorem 5}.

\noindent{\em Proof of Theorem \ref{Theorem 5}.} 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 $\Lambda_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 $\Lambda_2(N)$ by replacing each 2-sum operation by the corresponding parallel connection.  Thus all the basepoints are retained rather than being deleted.  Since $\Lambda_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 $\Lambda_2(N)$ if and only if $H\cong U_{1,3}$.  Let $P_1,P_2,\ldots,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) \cap 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 \in \Lambda_2(N)$ but $H \not \cong U_{1,3}$, then, for each $i$ such that $E(H) \cap P_i$ is non-empty, we relabel the unique element of $E(H) \cap P_i$ by $p_i$.  Let the resulting matroid be $H'$ and let $\Lambda_2' = \{H': H \in \Lambda_2(N) \hbox{ and } H \not \cong U_{1,3}\}$.

Let $N' = N_1 \de (\cup_{i=1}^{n} (P_i - p_i)).$  Then $N'$ is simple and can be constructed from the members of $\Lambda_2'$ by a sequence of direct sums and parallel  connections, the basepoints of which are $p_1,p_2,\ldots,p_n$.  We remark that the operation of parallel connection \cite{bry} 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 $\Lambda_2'$, and two different such vertices $H_1$ and $H_2$ are joined by an edge in $G(N)$ when $E(H_1) \cap E(H_2) \neq \emptyset$.  If we label such an edge by the unique element of $E(H_1) \cap 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,\ldots,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)| \ge 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,\ldots,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)\ba \{f_1,f_2,\ldots,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,\ldots,f_k$.  We extend the matroid $N'$ as follows, noting that each added element is canonically associated with an edge of $T$.  
\begin{enumerate}
\item[(i)] For each edge $x$ of $E(T) - \{f_2,f_3,\ldots,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}\}$.
\item[(ii)] For each $i$ in $\{1,2,\ldots,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.
\end{enumerate}
Let $M_1$ be the matroid that is obtained after all these elements have been added.  

\begin{lemma}
\label{M1}
$M_1$ is $3$-connected.
\end{lemma}

\begin{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 \ge 1$.

We show next that  
\begin{sublemma}
\label{Tedge}
$E(T) = \{f_2,f_3,\ldots,f_n\}$.
\end{sublemma}


Assume that $T$ has an edge other than $f_2,f_3,\ldots,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) \cup E(H_2) \cup e_x)$.  Then $H \de 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 
\begin{sublemma}
\label{H3-conn}
$H$ is $3$-connected.
\end{sublemma}

To see this, let $\{X,Y\}$ be a 2-separation of $H$.  Then $\min \{|X \cap E(H_i)|, |Y \cap E(H_i)|\} \le 1$ for each $i$ because $H_i$ is 3-connected. As 
$\min \{|E(H_1)|, |E(H_2)|\} \ge 3$, we may assume that  $|X \cap E(H_2)|\le 1$ and $|Y \cap E(H_1)| \le 1$.  Then $X$ and $Y$ span $H_1$ and $H_2$, respectively.  Thus 
$$r(H) + 1 \ge r(X) + r(Y) \ge 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 (\ref{H3-conn}).

Let $N'' = M_1|(E(N') \cup e_x).$ Then $\Lambda_2'(N'') = (\Lambda_2'(N') - \{H_1,H_2\}) \cup \{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 (\ref{Tedge}) holds otherwise the lemma holds.

By (\ref{Tedge}), every component of $N$ is 3-connected.  Then, arguing as in \cite[(4.1)]{ox_pack}, we get that $M_1|(E(L_1) \cup E(L_i) \cup \{x_{1,i},y_{1,i}\})$ is 3-connected for all $i$.  It follows, by \cite{ox_wu_conn}, that $M_1$ is 3-connected.
\end{proof}

We show next that 
\begin{lemma}
\label{minpr}
$(M_1,E(N'))$ is a minimal pair.
\end{lemma}

\begin{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 \de 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,\ldots,f_k\}$; or (ii) $e \in \{x_{1,i},y_{1,i}\}$ for some $i$ in $\{2,3,\ldots,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=\cup_{H \in 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 \de \{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 \ba e_x/x$ since $x$ is the basepoint of a parallel connection in $N'$. 
Therefore, in each case, $M_1 \de e$ is not 3-connected.  We conclude that (\ref{minpr}) holds. \end{proof}
 
To complete the proof of Theorem \ref{Theorem 5}, 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) \cup S)$, the matroid $M\de 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))| = \lambda_2(N)$ and $\lambda_1(N) = k$.  Moreover, by construction,
\vspace{-0.6cm}
\begin{center}
\begin{eqnarray*}
|E(M_1)| - |E(N')| & = & [|E(T)| - (k-1)] + 2(k-1)\\
		   & = & [(|V(T)| - 1) - (k-1)] + 2(k-1)\\
		   & = & [(\lambda_2(N) - 1) - (\lambda_1(N) - 1)] + 					2(\lambda_1(N) - 1)\\			  
		   & = & \lambda_1(N) + \lambda_2(N) - 2.
\end{eqnarray*}
\end{center}
But 
$$|E(N')| - |E(N)| \ge |S| = |E(M_1)| - |E(M)|.$$ 
Thus 
\vspace{-0.6cm}
\begin{center}
\begin{eqnarray*}
0 & \le & (|E(N')| - |E(N)|) - (|E(M_1)| - |E(M)|)\\ 
  &  =  & (|E(M)| - |E(N)|) - (|E(M_1)| - |E(N')|).
\end{eqnarray*}
\end{center}
Hence $|E(M)| - |E(N)| \ge \lambda_1(N) + \lambda_2(N) - 2.$ But, by Theorem \ref{Theorem 1}, the reverse inequality also holds.  Hence equality holds and the theorem is proved. \hfill $\square$

\medskip

\noindent{\bf 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. 



\begin{thebibliography}{99}

\bibitem{bix} Bixby, R.E., A simple theorem on $3$-connectivity, {\em Linear Algebra Appl.} {\bf 45} (1982), 123--126.


\bibitem{bixco} Bixby, R.E. and Coullard, C.R., Finding a smallest $3$-connected minor maintaining a fixed minor and a fixed element, {\em Combinatorica} {\bf 7} (1987), 231--242.

\bibitem{bry} Brylawski, T.H., A combinatorial model for series--parallel networks, {\em Trans.\ Amer.\ Math.\ Soc.} {\bf 154} (1971), 1--22.

\bibitem{bry2} Brylawski, T.H.,  A decomposition for combinatorial geometries, {\em Trans.\ Amer.\ Math.\ Soc.} {\bf 171} (1972), 235--282.
 
\bibitem{cunn} Cunningham, W.H., {\em A combinatorial decomposition theory}, Ph.~D. thesis, University of Waterloo, 1973.

\bibitem{lemox} Lemos, M. and Oxley, J.,  On packing minors into connected matroids, {\em Discrete Math.}, to appear.

\bibitem{Paper3} Lemos, M. and Oxley, J.,  On size, circumference and circuit removal in $3$-connected matroids, submitted.

 

\bibitem{Paper2} Lemos, M., Oxley, J., and Reid, T.J., On the $3$--connected matroids that are minimal having a fixed  restriction, submitted.

\bibitem{oxbook} Oxley, J.G., {\em Matroid theory,} Oxford University Press,
New York, 1992.

\bibitem{ox_pack} Oxley, J.G., On packing 3-connected restrictions into 3-connected matroids, {\em Discrete Math.} {\bf 178} (1998), 181--198.

\bibitem{ox_wu_conn} Oxley, J. and Wu, H., On matroid connectivity, {\em Discrete Math.} {\bf 146} (1995), 321--324.

\bibitem{oxwu} Oxley, J. and Wu, H., On the structure of $3$-connected matroids and graphs, submitted.


\bibitem{tru} Truemper, K., Partial matroid representations, {\em Europ. J. Combin.} {\bf 3} (1984), 377--394.

\end{thebibliography}

\end{document}



add $e_x$ and $e_x'$ for every $x=f_i$. When $f_i$ joins a vertex $K_1$ to a vertex $K_2$ of $T$, we choose in $K_i$ two different elements $a_i$ and $b_i$ --- none of them bases points of 2-sums. These elements are added freely with the exception of the triangles $\{a_1,a_2,e_x\}$ and $\{b_1,b_2,f_x\}$.
\end{enumerate}

Now, we shall prove that the matroid $M$ obtained after all these elements are added is 3-connected. Suppose that $\{X,Y\}$ is a $k$-separation for $M$, for $k\in\{1,2\}$.

Let $\Lambda_Z$ be the $K\in\Lambda_2$ such that $|E(K)\setminus Z|\le 1$, for every $Z\in\{X,Y\}$. Observe that $\{\Lambda_X,\Lambda_Y\}$ is a partition of $\Lambda_2$, since each $K$ is 3-connected. We may also suppose that $E(K)\subseteq Z$, when $K\in \Lambda_Z$, unless there is a $K'\in\Lambda_W$, for $W\not=Z$, such that $E(K)\cap E(K')\not=\emptyset$, otherwise $\{Z\cup E(K),W\setminus E(K)\}$ is a $k$-separation for $M$ because $E(K)\setminus Z=\{e\}$, for some $e$, $E(K)\cap Z$ spans $e$ and, when $|W|=2$, $W$ is a series class of $M$ and $e$ cannot exist. So, we may suppose that all the connected components of $N'$, with the possible exception of one, which is called by $H$ when exists, are contained in $X$ or $Y$, otherwise there are a pair of disjoint circuits of $N'$ which cuts $X$.

Let $E$ be the set of edges of $T$ which joins a vertex in $\Lambda_X$ to a vertex in $\Lambda_Y$. We shall prove that $f_i\not\in E$. Suppose that $f_i\in E$. Observe that both $e_x$ and $e_x'$ are not spanned by $X\cap E(N')$ and $Y\cap E(N')$ in $M$, where $x=f_i$, because the $a_l$ and $b_l$ chosen in (ii) are not bases points of 2-sums and one must be in $X$ and the other in $Y$. In particular $\{X,Y\}$ cannot be a 1-separation.

Now, we shall prove that $Z\cap E(N')$, where $Z\in\{X,Y\}$, does not span $e_x$ when $x=K_1K_2\in E$. We may suppose that $Z$ is closed in $M$ --- this can be done since $M$ is simple. So, $Z\cap E(N')$ spans $e_x$ only when both $a_{K_1}$ and $a_{K_2}$ belongs to $Z$, where $\{e_x,a_{K_1},a_{K_2}\}$ is the triangle which contains $e_x$. So, when we suppose that $E(K_1)\subseteq Z$ (remember that we are taking $Z$ closed and it must contains one of $E(K_i)$), it follows that $Z$ contains two elements of $K_2$, namely: the element that belongs to $E(K_1)\cap E(K_2)$ and $a_{K_2}$. We arrive at a contradiction. Thus, $Z\cap E(N')$ does not span $e_x$ for every $x\in E$. Thus, $E=\emptyset$ and the 2-separation does not exist.

Now, when we delete any element of $E(M)\setminus E(N')$, we 3-disconnect this matroid, since this element is associated with an edge $x$ of $T$. Thus, $T-x$ has two connected components which induces a partition $\{\Lambda_X,\Lambda_Y\}$ of the vertices of $G$. This partition of the vertex set of $G$ induces a partition $\{X,Y\}$ of the elements of $N'$, where
$$X=\bigcup_{K\in\Lambda_X}E(K)\hbox{ and }Y=E(N')\setminus X.$$
(We are making this distinction on the definitions of these sets because of the common element between the vertices of $x$). Observe that $Z$ spans every element that is associated with an edge that joins two vertices of $\Lambda_Z$. Thus, we put all these elements in $Z$ and call the set that we get by $Z'$. Thus, $\{X',Y'\}$ is a
\begin{enumerate}
\item[(iii)] 2-separation for $M\backslash e_x$, where $e_x$ is as in (i);
\item[(iv)] 1-separation for $M\backslash\{e_x,e_x'\}$, where $e_x$ and $e_x'$ are as in (ii).
\end{enumerate}
Thus, the elements that we are deleting is equal to $e_x$ or $e_x'$ and we get that the deletion of it 3-disconnect $M$. Thus, $(M,E(N'))$ is a minimal pair.

Now, we shall delete the elements of $E(N')\setminus E(N)$ one by one until the deletion of each of them 3-disconnect the matroid $M'$ that we get. Thus, $(M',E(N))$ is a minimal pair and
$$|E(M')|-|E(N)|=|E'|+(\lambda_2(N)-\lambda_1(N))+2(\lambda_2(N)-2),$$
where $E'=(E(M')\setminus E(N))\cap E(N')$. Hence
$$|E(M')|-|E(N)|\ge \lambda_1(N)+\lambda_2(N)-2$$
and we must have equality by theorem ?, when $N$ is not a circuit.



 

\end{document}