\documentstyle[12pt]{article} %\documentstyle[12pt,a4]{article} \newtheorem{thm}{Theorem} %\newtheorem{rmk}{Remark} \newtheorem{pro}{Problem} \newtheorem{clm}{Claim} \newtheorem{cor}[thm]{Corollary} \newtheorem{lem}[thm]{Lemma} \newtheorem{con}{Conjecture} \renewcommand{\theenumi}{\alph{enumi}} \renewcommand{\labelenumi}{(\theenumi)} \def\endprf{\hbox{\kern1pt\vrule height6pt width4pt depth1pt\kern1pt}} \def\prf{\par\noindent{\bf Proof.\enspace}\rm} \def\eop{\penalty 500\hbox{\quad\blackslug}\ifmmode\else\par \vskip4.5pt plus3pt minus2pt\fi} \def\rmk{\par\noindent{\bf Remark\enspace}\rm} \def\eop{\penalty 500\hbox{\quad\blackslug}\ifmmode\else\par \vskip4.5pt plus3pt minus2pt\fi} \title{Removable Circuits in Binary Matroids} \author{Luis A Goddyn\\ Department of Mathematics and Statistics\\ Simon Fraser University, Burnaby, B.C., Canada V5A 1S6 \\and\\ Bill Jackson\\ Department of Mathematical and Computing Sciences\\ Goldsmiths' College, London SE14 6NW, England} \begin{document} \maketitle \begin{abstract} We show that if $M$ is a connected binary matroid of cogirth at least five which does not have both an $F_7$-minor and an $F_7^*$-minor, then $M$ has a circuit $C$ such that $M-C$ is connected and $r(M-C)=r(M)$. \end{abstract} \section{Introduction} We shall consider the problem of finding sufficient conditions for the existence of a circuit in a given matroid $M$ whose deletion leaves the rank or connectivity of $M$ unchanged. The existence of such a circuit in graphs has been considered by various authors. The most general result for simple graphs can be deduced from a theorem of W. Mader \cite[Satz 1]{wolf}. \begin{thm}\label{m1} Let $k$ be a positive integer and $G$ be a simple $k$-connected graph of minimum degree at least $k+2$. Then $G$ has a circuit $C$ such that $G-E(C)$ is $k$-connected. \end{thm} Stronger results for the special case when $G$ is simple and $k=2$ can be found in Jackson \cite{bill} and Thommassen and Toft \cite{TT}. It seems natural to ask if Theorem \ref{m1} can be extended to a graph $G$, which may contain multiple edges. We can obtain a partial result by applying Theorem \ref{m1} to the underlying simple graph of $G$, if $G$ has no edges of multiplicity greater than two, and otherwise choosing $C$ to be a 2-circuit of $G$ belonging to an edge of multiplicity at least three, to deduce \begin{cor} \label{m2} Let $k$ be a positive integer and $G$ be a $k$-connected graph of minimum degree at least $k+3$. Then $G$ has a circuit $C$ such that $G-E(C)$ is $k$-connected. \end{cor} It follows from a result of Sinclair \cite{phil} that the bound $k+3$ in Corollary \ref{m2} can be reduced to $k+2$ for the special case when $k=1$. This is not true when $k=2$, however, as can be seen from an example constructed by N. Robertson and later B. Jackson (see \cite{bill}). However, replacing $k+3$ by $k+2$ when $k=2$ in Corollary \ref{m2} is valid for graphs which do not contain a vertex of degree four incident with two edge-disjoint 2-circuits by \cite{phil}, for planar graphs by \cite{herb}, and, more generally, graphs with no Petersen minor, by \cite{luis}. Oxley asked in \cite[Problem 14.4.8]{ox} if the following partial extension of Theorem \ref{m1} when $k=2$ is valid for binary matroids: does every connected binary matroid of girth at least three and cogirth at least four have a circuit $C$ such that $M-C$ is connected? L Lemos (see \cite{luis}) has constructed a cographic matroid of cogirth four which shows that the answer to Oxley's question is no. It remains an open problem, however, to decide if there exists an integer $t\geq 5$ such that all connected binary matroids $M$ of cogirth at least $t$ have a circuit $C$ such that $M-C$ is connected. We shall show in Theorem \ref{b} that this assertion is true with $t=5$ for binary matroids $M$ which do not have both an $F_7$- and an $F_7^*$-minor. This gives a partial generalisation of Corollary \ref{m2} when $k=2$. Our proof uses the decomposition theory of Seymour in \cite{S} which implies that a 3-connected, vertically 4-connected binary matroid which does not have both an $F_7$-minor and an $F_7^*$-minor is either graphic or cographic, or is isomorphic to $R_{10}$, $F_7$ or $F_7^*$. We shall first show that our result holds for graphic and cographic matroids. We then proceed by contradiction and show that a smallest counterexample to the result would be vertically 4-connected. It then only remains to check that the result holds for matroids obtained from $R_{10}$, $F_7$ or $F_7^*$ by parallel extensions. \section{Graphs} We shall consider finite graphs which may contain multiple edges, but no loops. We consider a graph $G$ to be 2-connected if $G-v$ is connected for all $v\in V(G)$. We shall use $E_G(v)$ to denote the set of edges of $G$ incident with a vertex $v$ and put $d_G(v)=|E_G(v)|$. We will suppress the subscript $G$ when it is clear to which graph we are referring. Given a circuit $C$ of $G$, put $|C|=|E(C)|$. We first obtain, in Lemma \ref{g} below, a slight extension of the case $k=2$ of Corollary \ref{m2}. We need this extension for our inductive proof on matroids. Lemma \ref{g} itself follows from a result of Sinclair \cite{phil}. We include a proof in this paper for the sake of completeness. We shall use the following elementary result. \begin{lem}\label{lemg} Let $G$ be a graph on $n$ vertices and $C_0$ be a circuit of $G$ such that $|C_0|\leq 3$ and $n> |C_0|$. Suppose that for all $v\in V(G)-V(C_0)$ we have $d_G(v)\geq 4$. Then $G$ has a circuit $C$ such that $E(C_0)\cap E(C)=\emptyset$. \end{lem} \prf If $G$ is not 2-connected then choosing $C$ to be any circuit in an end-block of $G$ which does not contain $C_0$ we have $E(C_0)\cap E(C)=\emptyset$. Hence we may suppose that $G$ is 2-connected. Let $H=G-E(C_0)$. Suppose $H$ is a forest. Then $|E(H)|\leq n-1$. Let $t$ be the number of edges between $V(C_0)$ and $V(G)-V(C_0)$. Then $|E(H)|=\frac{1}{2}(t+\sum_{v\in V(G)-V(C_0)}d_G(v))$. Since $G$ is 2-connected, $t\geq 2$, and since $d(v)\geq 4$ for all $v\in V(G)-V(C_0)$, we have $|E(H)|\geq 2n-2|C_0|+1$. Thus $n\leq 2|C_0|-2$. Since $n\geq |C_0|$, we have $|C_0|=3$, and $n=4$. Let $ V(G)-V(C_0)=\{v\}$. Using the assumption that $H$ is a forest, we have $d_G(v)\leq 3$. This contradicts an hypothesis on $G$ and so the assumption that $H$ is a forest must be false. \endprf \begin{lem}\label{g} Let $G$ be a 2-connected graph on $n$ vertices and $C_0$ be a circuit of $G$ such that $|C_0|\leq 3$ and $n> |C_0|$. Suppose that for all $v\in V(G)-V(C_0)$ we have $d_G(v)\geq 5$. Then $G-E(C_0)$ has a circuit $C$ such that $G-E(C)$ is 2-connected. \end{lem} \prf Suppose the theorem is false and let $G$ be a counterexample. By Lemma \ref{lemg}, we can choose a circuit $C$ in $G-E(C_0)$. Let $H=G-E(C)$, let $B_0$ be the block of $H$ which contains $C_0$ and $B$ be an end-block of $H$ distinct from $B_0$. We may suppose that $C$ has been chosen such that $|E(B)|$ is minimal. Let $e$ be an edge of $B$ chosen such that, if $B$ contains a cut-vertex $x$ of $H$, then $e$ is incident with $x$. Since $d_G(v)\geq 5$ for all $v\in V(G)-V(C_0)$, at most one vertex of $B-e$ has degree less than two. Thus we may choose a circuit $C'$ contained in $B-e$. Using the minimality of $|E(B)|$ and the fact that $G$ is 2-connected we see that each end-block of $H-E(C')$ is incident with $C$ and each component of $H-E(C')$ is incident with at least two vertices of $C$. Thus $G-E(C')=(H-E(C'))\cup E(C)$ is 2-connected. This contradicts the choice of $G$ as a counterexample to the theorem. \endprf \vspace{3mm} Given a graph $G$ and $U\subseteq V(G)$, we use $N_G(U)$ to denote the set of vertices of $V(G)-U$ adjacent to a vertex of $U$ and $G[U]$ to denote the subgraph of $G$ induced by $U$. For $S\subseteq E(G)$, let $G/S$ be the graph obtained from $G$ by contracting the edges in $S$, and $V(S)$ the set of vertices of $G$ incident with $S$. We next show, in Lemma \ref{c} below, that the case $k=2$ of Corollary \ref{m2} can be extended to cographic matroids. We shall use the following elementary result. \begin{lem}\label{lemc} Let $G$ be a connected graph on $n$ vertices and $X_0$ be a cocircuit of $G$ such that $|X_0|\leq 3$ and $|E(G)|\geq n+|X_0|-1$. Suppose that $G-X_0$ has girth at least four. Then $V(G)\neq V(X_0)$. \end{lem} \prf Let $H_1$ and $H_2$ be the two components of $G-X_0$. Suppose $V(G)= V(X_0)$. Then $|V(H_i)|\leq 3$ and since $G-X_0$ has girth at least four, $H_i$ is a tree for $1\leq i \leq 2$. Thus $$|E(G)|= |V(H_1)|-1 + |V(H_2)|-1 + |X_0| = n+|X_0|-2.$$ This contradicts the hypothesis on $|E(G)|$. \endprf \begin{lem}\label{c} Let $G$ be a 2-connected graph on $n$ vertices and $X_0$ be a cocircuit of $G$ such that $|X_0|\leq 3$ and $|E(G)|\geq n+|X_0|-1$. Suppose that $G-X_0$ has girth at least five. Then there exists $v\in V(G)- V(X_0)$ such that $G/E(v)$ is 2-connected. \end{lem} \prf Suppose the theorem is false and let $G$ be a counterexample. By Lemma \ref{lemc}, we can choose a vertex $v$ in $V(G)-V(X_0)$. Let $H=G/E(v)$ and $x$ be the vertex of $H$ corresponding to $N_G(v)\cup \{v\}$. Then $x$ is the unique cut vertex of $H$. Since $X_0\cap E(v)=\emptyset$, $X_0$ is a cocircuit of $H$ and hence is contained in a block $B$ of $H$. Let $U=V(B)-x$. We may suppose that $v$ has been chosen such that $|U|$ is maximal. Note that $N_G(U)\subseteq \{v\}\cup N_G(v)$. Furthermore, since $G$ is 2-connected, $|N_G(U)|\geq 2$ and $G[U\cup N_G(U)\cup \{v\}]$ is 2-connected. Choose $v'\in V(H)-V(B)$. Then $v'\in V(G)-V(X_0)$. Let $H'=G/E(v'_)$ and $x'$ be the vertex of $H$ corresponding to $N_G(v')\cup \{v'\}$. Let $B'$ be the block of $H'$ containing $X_0$ and $U'=V(B')-x'$. Then $U\cup (N_G(U)-N_G(v'))$ is properly contained in $V(B')$. By the maximality of $|U|$ we must have $N_G(U)\subseteq N_G(v')$. Now the facts that $N_G(U)\subseteq \{v\}\cup N_G(v)$ and $|N_G(U)|\geq 2$ imply that $E(v)\cup E(v')$ contains a circuit of $G$ of length at most four. This contradicts the fact that $G-X_0$ has girth at least five. \endprf \section{Binary Matroids} We shall use the following operation on binary matroids from Seymour \cite{S}. Given binary matroids $M_1$ and $M_2$ let $M_1\triangle M_2$ be the binary matroid with $E(M)=E(M_1)\triangle E(M_2)$ and circuits all minimal non-empty subsets of $E(M)$ of the form $C_1\triangle C_2$, where $C_i$ is a circuit of $M_i$. We refer the reader to \cite{ox} for other definitions on matroids. Our main result is \begin{thm} \label{b} Let $M$ be a connected binary matroid which does not have both an $F_7$-minor and an $F_7^*$-minor. Let $C_0$ be a circuit of $M$ such that $|C_0|\leq 3$ and $r(M)>r(C_0)$. Suppose $|X|\geq 5$ for all cocircuits $X$ of $M$ such that $X\cap C_0 =\emptyset$. Then $M-C_0$ has a circuit $C$ such that $M-C$ is connected and $r(M-C)=r(M)$. \end{thm} \prf We proceed by contradiction. Suppose the theorem is false and let $M$ be a counterexample chosen such that $r(M)$ is as small as possible. \begin{clm} \label{cm1} $M$ is vertically 3-connected. \end{clm} \prf Suppose that $M$ has a vertical $2$-separation $(S_1,S_2)$. Choose $(S_1,S_2)$ such that $|S_1\cap C_0|$ is minimal. Since $r(S_i)\geq 2$ we have $|S_i|\geq 2$. By \cite[2.6]{S}, $M=M_1\triangle M_2$ for minors $M_1$ and $M_2$ of $M$ such that $2\leq r(M_i) < r(M)$, $E(M_1)\cap E(M_2) = C_0'$ for some $2$-circuit $C_0'=\{f,g\}$ of $M_i$, and $E(M_i)-C_0'=S_i$ for $1\leq i \leq 2$. Since $M$ is connected each $M_i$ is connected. Since $M_i$ is a minor of $M$, $M_i$ is binary and does not have both an $F_7$-minor and an $F_7^*$-minor. Since $C_0'\cap E(M)=\emptyset$ we have $C_0'\cap C_0=\emptyset$. Since $|C_0|\leq 3$, $|C_0\cap E(M_1)|\leq 1$. Suppose $C_0\cap E(M_1)=\{e\} $. Then $C_0=C_1 \triangle C_2$ for some circuits $C_i$ of $M_i$, $1\leq i \leq 2$. Thus $|C_1|=2$ and $e$ is parallel to $f$ and $g$ in $M_1$. Let $h\in S_1-e$ and $Y$ be a circuit of $M$ which meets both $S_1$ and $S_2$. Then $Y=Y_1\triangle Y_2\triangle $ for some circuits $Y_i$ of $M_i$ such that $|Y_i\cap C_0'|=1$, $1\leq i \leq 2$. Thus $Y_1-C_0'+e$ is a circuit of both $M_1$ and $M$, and $r(S_1-e)=r(S_1)\geq 2$. Similarly since $e\in C_0\subseteq S_2+e$ we have $r(S_2+e)=r(S_2)\geq 2$. Thus $(S_1-e, S_2+e)$ is a vertical 2-separation of $M$. This contradicts the minimality of $|S_1\cap C_0|$. Hence we must have $C_0\cap E(M_1)=\emptyset$. Let $X_1$ be a cocircuit of $M_1$ such that $X_1\cap C_0' =\emptyset$. Then $X_1$ is a cocircuit of $M$ such that $X_1\cap C_0 =\emptyset$ so by an hypothesis of the theorem we have $|X_1|\geq 5$. Using the minimality of $r(M)$ we deduce that $M_1-C_0'$ has a circuit $C$ such that $M_1-C$ is connected and $r(M_1-C)=r(M_1)$. Since $M-C=(M_1-C)\triangle M_2$ we have $C$ is a circuit of $M-C_0$ such that $M-C$ is connected and $r(M-C)=r(M)$. This contradicts the choice of $M$. Thus $M$ has no vertical 2-separation and hence $M$ is vertically 3-connected. \endprf \begin{clm} \label{cm2} $M$ is vertically 4-connected. \end{clm} \prf Suppose that $M$ has a vertical $3$-separation $(S_1,S_2)$. Choose $(S_1,S_2)$ such that $|S_1\cap C_0|$ is minimal. Since $|C_0|\leq 3$, $|C_0\cap E(M_1)|\leq 1$. We first show that $|S_i|\geq 4$ for $1\leq i \leq 2$. Suppose $|S_i|=3$ for some $i\in\{1,2\}$. Since $r(S_i)\geq 3$ we must have $r(S_i)=3$. Since $r(S_1)+r(S_2)-r(M)=2$ we have $r(S_j)=r(M)-1$, for $j=3-i$. Thus the closure of $S_j$ is a hyperplane of $M$. The complement of this hyperplane will be a cocircuit $X_0$ of $M$ contained in $S_i$. Since $|X_0|\leq|S_i|=3$, it follows from an hypothesis of the theorem that $X_0\cap C_0 \neq \emptyset$. Since $M$ is binary we must have $|X_0\cap C_0|=2$. Since $S_i$ is independent we must have $|C_0|=3$ and $|S_j\cap C_0|=1$. By the minimality of $|S_1\cap C_0|$, we must have $i=2$. Choosing $e_0\in S_1\cap C_0$ we have $r(S_1-e)\leq r(S_1)$ and, since $e_0\in C_0\subseteq S_2+e_0$, $r(S_2+e_0)=r(S_2)=3$. Thus $(S_1-e_0,S_2+e_0)$ is either a vertical 2-separation of $M$, contradicting Claim \ref{cm1}, or it is a vertical 3-separation of $M$, contradicting the minimality of $|S_1\cap C_0|$. Thus $|S_i|\geq 4$ for $i\in\{1,2\}$. By \cite[2.9]{S}, $M=M_1\triangle M_2$ for minors $M_1$ and $M_2$ of $M$ such that $3\leq r(M_i) < r(M)$, $E(M_1)\cap E(M_2) = C_0'$ for some $3$-circuit $C_0'=\{f,g,h\}$ of $M_i$, and $E(M_i)-C_0'=S_i$ for $1\leq i \leq 2$. Since $M$ is connected, each $M_i$ is connected. Since $M_i$ is a minor of $M$, $M_i$ is binary and does not have both an $F_7$- and an $F_7^*$-minor. Since $C_0'\cap E(M)=\emptyset$ we have $C_0'\cap C_0=\emptyset$. Suppose $e\in C_0\cap E(M_1)$. Then $C_0=C_1\triangle C_2$ for some circuit $C_i$ of $M_i$, $1\leq i \leq 2$. Thus $C_1- C_0'= \{e\}$ and $1\leq |C_1\cap C_0'|\leq 2$. If $|C_1\cap C_0'| = 2$ then replacing $C_1$ by $C_1'=C_1\triangle C_0'$ we have $|C_1'\cap C_0'|=1$. Thus we may assume without loss of generality that $e$ is parallel to $f$ in $M_1$. Let $M_1'$ be the simple matroid obtained by replacing all parallel classes of $M_1$ by single elements and let $f$, $g$ and $h$ represent their own parallel classes in $M_1'$. Using Claim \ref{cm1} it follows that $M_1'$ is 3-connected. If $f$ is a coloop $M_1'-\{g,h\}$ then $C_0'$ would contain a cocircuit of $M_1'$. Since $M_1'$ is binary this cocircuit would have size two and hence would contradict the fact that $M_1'$ is 3-connected. Thus $f$ is contained in some circuit of $M_1'-\{g,h\}$. Since $e$ is parallel to $f$ we deduce that $M$ has a circuit which contains $e$ and is contained in $S_1$. Hence $r(S_1-e)=r(S_1)\geq 2$. Similarly since $e\in C_0\subseteq S_2+e$ we have $r(S_2+e)=r(S_2)\geq 2$. Thus $(S_1-e, S_2+e)$ is a vertical 3-separation of $M$ which contradicts the minimality of $|S_1\cap C_0|$. Hence we must have $C_0\cap E(M_1)=\emptyset$. Let $X_1$ be a cocircuit of $M_1$ such that $X_1\cap C_0' =\emptyset$. Then $X_1$ is a cocircuit of $M$ such that $X_1\cap C_0 =\emptyset$ so by an hypothesis of the theorem we have $|X_1|\geq 5$. Using the minimality of $r(M)$ we deduce that $M_1-C_0'$ has a circuit $C$ such that $M_1-C$ is connected and $r(M_1-C)=r(M_1)$. Since $M-C=(M_1-C)\triangle M_2$ it follows that $C$ is a circuit of $M$ such that $M-C$ is connected and $r(M-C)=r(M)$. This contradicts the choice of $M$. Thus $M$ has no vertical 3-separation and hence $M$ is vertically 4-connected. \endprf We are now ready to complete the proof of the theorem. Let $M'$ be the simple matroid obtained by replacing all parallel classes of $M$ by single elements. By Claims \ref{cm1} and \ref{cm2}, $M'$ is a 3-connected vertically 4-connected binary matroid. By \cite[7.6 and 14.3]{S}, $M'$ is either graphic or cographic, or is isomorphic to $R_{10}$, $F_7$ or $F_7^*$. Thus $M$ is either graphic or cographic, or can be obtained from $R_{10}$, $F_7$ or $F_7^*$ by a sequence of parallel extensions. If the latter alternative holds then since $R_{10}$, $F_7$ and $F_7^*$ have many cocircuits of size four, $M-C_0$ must contain a circuit $C$ of size two. The 3-connectivity of $M'$ now implies that $M-C$ is connected and $r(M-C)=r(M)$. Hence $M$ is graphic or cographic. Lemmas \ref{g} and \ref{c} now give a contradiction to the choice of $M$ as a counterexample to the theorem. \endprf \section{Closing Remarks} \rmk {\bf 1} It follows from Corollary \ref{m2} that every connected graph $G$ of minimum degree at least three has a circuit $C$ such that $G-E(C)$ is connected. Thus every graphic matroid $M$ of cogirth at least three has a circuit $C$ such that $r(M)=r(M-C)$. The same result holds for a cographic matroid $M$ of cogirth at least three. (This can be seen by considering the graph $G$ for which $M$ is the cographic matroid. Then $G$ has girth at least three and the set of edges incident with any non-cutvertex of $G$ will give the required circuit $C$ of $M$.) The result does not extend to regular matroids of cogirth at least three since it does not hold for $R_{10}$ (which has cogirth four). However, if $M$ is a binary matroid which does not have both an $F_7$- and an $F_7^*$-minor, and has cogirth at least five, then we may apply Theorem \ref{b} to a component of $M$ to deduce that $M$ has a circuit $C$ such that $r(M)=r(M-C)$. One may hope that all binary matroids $M$ of sufficiently high girth have a circuit $C$ such that $r(M)=r(M-C)$. This is not the case. To see this note that $r(M)=r(M-C)$ if and only if $C$ does not contain any cocircuit of $M$. Thus, if $M$ is identically self-dual (and in particular if $M=R_{10}$) then no such circuit can exist. The assertion now follows since there exist identically self-dual binary matroids of arbitrarily high cogirth. The column matroid of the parity check matrix of the binary Reed-Muller code $R(s,2s+1)$, for example, is identically self dual and has cogirth $2^{s+1}$. \rmk {\bf 2} It is not true that every connected matroid of sufficiently high girth has a circuit $C$ such that $M-C$ is connected. This can be seen by considering the uniform matroid $U_{m,2m}$. It is still conceivable, however, that this may hold for binary matroids. \begin{pro} Does there exist an integer $t$ such that every connected binary matroid $M$ of cogirth at least $t$ has a circuit $C$ such that $M-C$ is connected? \end{pro} \rmk {\bf 3} We could also ask for sufficient conditions for the existence of a cocircuit in a matroid $M$ the deletion of which preserves the connectivity of $M$. The following reult of P.D. Seymour (see \cite[Lemma 6]{ox1}) is in the spirit of this paper. It is a matroid analogue of an earlier graph theoretic result of Kaugars (see \cite[p. 31]{H}). \begin{lem} Let $M$ be a connected binary matroid of girth and cogirth at least three. Then $M$ has a cocircuit $X$ such that $M-X$ is connected. \end{lem} \begin{thebibliography}{BJJ} \bibitem{herb} H. Fleischner and B. Jackson, Removable cycles in planar graphs, {\em J. London Math. Soc.} 31 (1985) 8-48. \bibitem{luis} L.A. Goddyn, J. van den Heuvel and S. McGuinness, Removable circuits in multigraphs, submitted. \bibitem{H} F. Harary, "Graph Theory" {\em Addison-Wesley} Reading, Mass.; Menlo Park, Calif.; London (1969). minimum degree at least four, {\em J. London Math. Soc.} 21 (1980) 385-392. \bibitem{bill} B. Jackson, Removable circuits in 2-connected graphs of minimum degree at least four, {\em J. London Math. Soc.} 21 (1980) 385-392. \bibitem{wolf} W. Mader, Kreuzungsfreie $a,b$-Wege in endlichen Graphen, {\em Abh. Sem. Univ. Hamburg} 42 (1974) 187-204. \bibitem{ox1} J.G. Oxley, Circuit coverings and packings for binary matroids, {\em Math. Proc. Cambridge Phil. Soc.} 83 (1978) 347-351. \bibitem{ox} J.G. Oxley, "Matroid Theory",{\em Oxford Univ. Press} Oxford (1992). \bibitem{S} P.D. Seymour, Decomposition of regular matroids, {\it J. Combinatorial Theory (B)}, 28 (1980) 305-359. \bibitem{phil} P.A. Sinclair, Strong snarks and the removal of edges from circuits in graphs, PhD thesis, University of London, 1997. \bibitem{TT} C. Thomassen and B. Toft, Non-separating induced cycles in graphs, {\em J. Combinatorial Theory (B)} 31 (1981) 199-224. \end{thebibliography} \end{document}