%%%%%%%%%%     Beginning of LaTeX - file     %%%%%%%%%%
% Time-stamp: <97/05/02 11:46:48 jan>
\documentstyle[draft,11pt,leqno,fleqn,bezier]{article}

%% All kind of stuff I usually have in help-files
\renewcommand{\baselinestretch}{1.45}\small\normalsize

\topmargin -5mm %0pt
\oddsidemargin 0.125 in
\evensidemargin 0.125 in
\marginparwidth 0.75 in
\textwidth 6.19 in

\textheight 210mm
\advance\textheight by \topskip

\newcounter{fig}
\newcounter{lit}
\newcounter{clai}
\newcounter{theorem}[section]
\renewcommand{\thetheorem}{\arabic{section}.\arabic{theorem}}

\newenvironment{theorem}{\begin{trivlist}\item[]\refstepcounter{theorem}%
	{\bf\thetheorem\ Theorem}\par\nobreak\noindent\sl\ignorespaces}{%
	\ifvmode\smallskip\fi\end{trivlist}}
\newenvironment{theoremplus}[1]{\begin{trivlist}\item[]%
	\refstepcounter{theorem}{\bf\thetheorem\ Theorem} {\rm (\,#1\,)}%
	\par\nobreak\noindent\sl\ignorespaces}{%
	\ifvmode\smallskip\fi\end{trivlist}}
\newenvironment{lemma}{\begin{trivlist}\item[]\refstepcounter{theorem}%
	{\bf\thetheorem\ Lemma}\par\nobreak\noindent\sl\ignorespaces}{%
	\ifvmode\smallskip\fi\end{trivlist}}
\newenvironment{conjecture}{\begin{trivlist}\item[]%
	\refstepcounter{theorem}{\bf\thetheorem\ Conjecture}\par%
	\nobreak\noindent\sl\ignorespaces}{%
	\ifvmode\smallskip\fi\end{trivlist}}
\newenvironment{conjectureplus}[1]{\begin{trivlist}\item[]%
	\refstepcounter{theorem}{\bf\thetheorem\ Conjecture} %
	{\rm(\,#1\,)}\par\nobreak\noindent\sl\ignorespaces}{%
	\ifvmode\smallskip\fi\end{trivlist}}
\newenvironment{remark}{\begin{trivlist}\item[]\refstepcounter{theorem}%
	{\bf\thetheorem\ Remark}\par\nobreak\noindent\ignorespaces}{%
	\ifvmode\smallskip\fi\end{trivlist}}
\newenvironment{question}{\begin{trivlist}\item[]%
	\refstepcounter{theorem}{\bf\thetheorem\ Question}%
	\par\nobreak\noindent\sl\ignorespaces}{%
	\ifvmode\smallskip\fi\end{trivlist}}
\newenvironment{questionplus}[1]{\begin{trivlist}\item[]%
	\refstepcounter{theorem}{\bf\thetheorem\ Question} %
	{\rm(\,#1\,)}\par\nobreak\noindent\sl\ignorespaces}{%
	\ifvmode\smallskip\fi\end{trivlist}}
\newenvironment{problem}{\begin{trivlist}\item[]%
	\refstepcounter{theorem}{\bf\thetheorem\ Problem}%
	\par\nobreak\noindent\sl\ignorespaces}{%
	\ifvmode\smallskip\fi\end{trivlist}}
\newenvironment{problemplus}[1]{\begin{trivlist}\item[]%
	\refstepcounter{theorem}{\bf\thetheorem\ Problem} %
	{\rm(\,#1\,)}\par\nobreak\noindent\sl\ignorespaces}{%
	\ifvmode\smallskip\fi\end{trivlist}}

\newenvironment{capt}{\refstepcounter{fig}%
	\list{}{\topsep 12pt\leftmargin\mathindent%
	\rightmargin\leftmargin}\item[]{\bf Figure \thefig}\mbox{ \ }}%
	{\endlist\unskip}

\newenvironment{claim}{\begin{trivlist}\item[]\refstepcounter{clai}%
	{\bf Claim \theclai}\mbox{ \ }\sl\ignorespaces}{%
	\ifvmode\smallskip\fi\end{trivlist}}
\newenvironment{proof}{\begin{trivlist}\item[]{\bf Proof}\mbox{ \ }}%
	{\qquad\hspace*{\fill}\eop\end{trivlist}}
\newenvironment{proofplus}[1]{\begin{trivlist}\item[]
	{\bf Proof of #1}\mbox{ \ }}{\qquad\hspace*{\fill}\eop%
	\end{trivlist}}
\newenvironment{proofopen}{\begin{trivlist}\item[]{\bf Proof}\mbox{ \ }}%
	{\qquad\hspace*{\fill}$\Box$\end{trivlist}}

\newenvironment{semieq}{\refstepcounter{equation}\trivlist\item[]
	\leavevmode\hangindent\mathindent
	\hbox to \mathindent{\rm (\theequation)\hfil}\ignorespaces}%
	{\endtrivlist}
\newcommand{\wideitem}[1]{\leavevmode\hangindent\mathindent\noindent%
        \hbox to \mathindent{#1\hfil}\ignorespaces}

\newcommand{\case}[2]{{\left\{\begin{array}{@{}l@{}l@{}}%
	#1\\#2\end{array}\right.}}

\newcommand{\contr}{\mathbin{/}}
\newcommand{\EC}{E(C)}
\newcommand{\EG}{E(G)}
\renewcommand{\emptyset}{\mathchar"001F}
\newcommand{\eop}{\rule{1.4ex}{1.4ex}}
\newcommand{\eqref}[1]{(\ref{#1})}
\renewcommand{\H}{{\cal H}}
\renewcommand{\L}{{\cal L}}
\renewcommand{\P}{{\bf P}}
\newcommand{\half}{{\textstyle\frac{1}{2}}}
\let\labl=\label
%\renewcommand{\label}[1]{\labl{#1}\marginpar{\scriptsize{#1}}}
\newcommand{\litref}[1]{[\ref{#1}]}
\newcommand{\litrefplus}[2]{[\ref{#1}, {#2}]}
\newcommand{\rif}{\qquad\mbox{\rm if }}
\newcommand{\rotherwise}{\qquad\mbox{\rm otherwise}}
\newcommand{\se}{\subseteq}
\newcommand{\sm}{\setminus}
\newcommand{\VC}{V(C)}
\newcommand{\vertex}{\circle*{15}}
\newcommand{\VG}{V(G)}
\newcommand{\VH}{V(H)}

\mathindent = 2\parindent

%%%% Now the real text begins%%%%%%%%%%

\title{\bf Removable Circuits in Multigraphs}

\author{\quad\\
{\sc Luis A. Goddyn $^1$}\,\thanks{\ Supported by the Natural Sciences and
Engineering Research Council of Canada}\\[1ex]
{\sc Jan van den Heuvel $^1$}\thanks{\ Supported by a grant from the
Natural Sciences and Engineering Research Council of Canada}\ \thanks{\
Current address\,: Centre for Discrete and Applicable Mathematics,
Department of Mathematics, London School of Economics, Houghton Street,
London WC2A 2AE, United Kingdom}\\[1ex]
{\sc Sean McGuinness $^2$}\\
\\
$^1$ Department of Mathematics and Statistics, Simon Fraser University\\
Burnaby, B.C., Canada V5A 1S6\\[1.5ex]
$^2$ Department of Mathematics, University of Ume\aa\\
Ume\aa, Sweden}

\date{}

\begin{document}
\maketitle

\newpage
{\bf Proposed Running Head: } Removable Circuits in Multigraphs
\vspace{2cm}
\newline
Please send proofs to:
\begin{quote}
Luis Goddyn \\
Department of Mathematics and Statistics \\
Simon Fraser University \\
Burnaby, BC  V5A 1S6 \\
CANADA 
\vspace{1cm} \\
email: goddyn@sfu.ca \\
tel: (604) 291-4699 
\end{quote}

\newpage

\begin{abstract}
\normalsize
\noindent
We prove the following conjecture of Bill Jackson (\,J.~London Math.\
Soc.~(2)~{\bf21} (1980) p.~391\,).
\begin{quote}
{\sl If~$G$ is a 2-connected multigraph with minimum degree at least~4 and
containing no Petersen minor, then~$G$ contains a circuit~$C$ such that
$G-\EC$ is 2-connected.}
\end{quote}
In fact,~$G$ has at least {\em two\/} edge-disjoint circuits which can
serve as~$C$. Until now, the conjecture had been verified only for planar
graphs and for simple graphs.

\bigskip
\bigskip\noindent
{\sl Keywords}\,: (\,removable\,) circuit, multigraph, Petersen graph

\bigskip\noindent
{\sl AMS Subject Classifications (1991)}\,: 05C38, 05C40, 05C70
\end{abstract}

\newpage

\section{Introduction}\label{sec-intro}

In this paper a graph may have multiple edges, but no loops. A graph is
{\it simple\/} if it has no multiple edges. A {\it circuit\/} in a
graph~$G$ is a connected 2-regular subgraph of~$G$. A circuit~$C$ in~$G$ is
{\it removable\/} if $G-\EC$ is 2-connected. A {\it Petersen minor\/} of a
graph~$G$ is a minor of~$G$ which is isomorphic with Petersen's graph. A
graph is called {\it eulerian\/} if all its vertices have even degree.

The study of removable circuits in a graph seems to have been initiated by
A.~Hobbs~\litref{hob}, who asked whether every 2-connected eulerian graph
with minimum degree at least~4 contains a removable circuit. The answer to
this question is no, as was first realized by N.~Robertson~\litref{rob},
and later, independently, by B.~Jackson~\litref{jac}. Their counterexample
is depicted in Figure~\ref{fig1}.
\begin{figure}[htb]
\vspace{10pt}
\centerline{
\setlength{\unitlength}{0.15mm}%
%The Petersen graph with doubled and split spokes
\begin{picture}(278.2,265.3)(-139.1,-119.3)
\linethickness{1.1\unitlength}
\put(-82.3,-113.3){\vertex}\put(82.3,-113.3){\vertex}
\put(133.1,43.3){\vertex}\put(0.0,140.0){\vertex}
\put(-133.1,43.3){\vertex}
%
\put(-58.8,-81.9){\vertex}\put(58.8,-81.9){\vertex}
\put(95.1,30.9){\vertex}\put(0.0,100.0){\vertex}
\put(-95.1,30.9){\vertex}
%
\put(-35.3,-48.5){\vertex}\put(35.3,-48.5){\vertex}
\put(57.1,18.5){\vertex}\put(0.0,60.0){\vertex}
\put(-57.1,18.5){\vertex}
%
\put(-82.3,-113.3){\line(1,0){164.8}}
\bezier{165}(82.3,-113.3)(107.7,-35.0)(133.1,43.3)
\bezier{165}(133.1,43.3)(66.55,91.65)(0.0,140.0)
\bezier{165}(0.0,140.0)(-66.55,91.65)(-133.1,43.3)
\bezier{165}(-133.1,43.3)(-107.7,-35.0)(-82.3,-113.3)
%
\bezier{114}(-35.3,-48.5)(-17.75,5.75)(0.0,60.0)
\bezier{114}(0.0,60.0)(17.75,5.75)(35.3,-48.5)
\bezier{114}(35.3,-48.5)(-10.9,-15.0)(-57.1,18.5)
\put(-57.1,18.5){\line(1,0){114.2}}
\bezier{114}(57.1,18.5)(10.9,-15.0)(-35.3,-48.5)
%
\bezier{41}(-82.3,-113.3)(-78.7,-90.6)(-58.8,-81.9)
\bezier{41}(-82.3,-113.3)(-61.8,-102.9)(-58.8,-81.9)
\bezier{41}(82.3,-113.3)(78.7,-90.6)(58.8,-81.9)
\bezier{41}(82.3,-113.3)(61.8,-102.9)(58.8,-81.9)
\bezier{41}(133.1,43.3)(116.9,27.0)(95.1,30.9)
\bezier{41}(133.1,43.3)(110.5,46.9)(95.1,30.9)
\bezier{41}(0.0,140.0)(10.5,119.5)(0.0,100.0)
\bezier{41}(0.0,140.0)(-10.5,119.5)(0.0,100.0)
\bezier{41}(-133.1,43.3)(-116.9,27.0)(-95.1,30.9)
\bezier{41}(-133.1,43.3)(-110.5,46.9)(-95.1,30.9)
%
\bezier{41}(-35.3,-48.5)(-54.5,-58.5)(-58.8,-81.9)
\bezier{41}(-35.3,-48.5)(-38.8,-70.0)(-58.8,-81.9)
\bezier{41}(35.3,-48.5)(54.5,-58.5)(58.8,-81.9)
\bezier{41}(35.3,-48.5)(38.8,-70.0)(58.8,-81.9)
\bezier{41}(57.1,18.5)(78.5,15.3)(95.1,30.9)
\bezier{41}(57.1,18.5)(72.5,33.8)(95.1,30.9)
\bezier{41}(0.0,60.0)(9.7,79.4)(0.0,100.0)
\bezier{41}(0.0,60.0)(- 9.7,79.4)(0.0,100.0)
\bezier{41}(-57.1,18.5)(-78.5,15.3)(-95.1,30.9)
\bezier{41}(-57.1,18.5)(-72.5,33.8)(-95.1,30.9)
\end{picture}
}
\begin{capt}
A 2-connected 4-regular eulerian graph without removable
circuit.\labl{fig1}
\end{capt}
\vspace{5pt}
\end{figure}%

The fact that the counterexample in Figure~\ref{fig1} contains multiple
edges, was shown to be unavoidable by the following result.

\begin{theoremplus}{{\sc Jackson} \litref{jac}}
Let~$G$ be a 2-connected simple graph with minimum degree $k\geq4$ and let
$e\in\EG$. Then there exists a removable circuit~$C$ in~$G$ of length at
least $k-1$ and such that $e\notin\EC$.\label{th-jac}
\end{theoremplus}

\noindent
In fact, a similar result for arbitrary connectivity can be derived from an
older result of W.~Mader~\litrefplus{mad}{Satz~1}. We state only the
corollary here.

\begin{theoremplus}{{\sc Mader} \litref{mad}}
Let~$G$ be a $k$-connected simple graph with minimum degree at least $k+2$.
Then~$G$ contains a circuit~$C$ such that $G-\EC$ is
$k$-connected.\label{th-mad}
\end{theoremplus}

\noindent
A result with a somewhat different flavor was obtained by C.~Thomassen and
B.~Toft.

\begin{theoremplus}{{\sc Thomassen \& Toft} \litref{thotof}}
Let~$G$ be a 2-connected simple graph with minimum degree at least~4.
Then~$G$ contains an induced circuit~$C$ such that $G-\VC$ is connected and
$G-\EC$ is 2-connected.\label{th-thotof}
\end{theoremplus}

\noindent
Theorems~\ref{th-jac}--\ref{th-thotof} all show that a 2-connected {\it
simple\/} graph with minimum degree at least~4 contains a removable
circuit. But the problem remains to find sufficient conditions such that
this conclusion holds for nonsimple graphs. Since all known examples of
2-connected graphs with minimum degree at least~4 and containing no
removable circuit contain the Petersen graph as a minor, the following
conjecture was made in~\litref{jac}.

\begin{conjectureplus}{{\sc Jackson} \litref{jac}}
Let~$G$ be a 2-connected graph with minimum degree at least~4 and
containing no Petersen minor. Then~$G$ contains a removable
circuit.\label{con-jac}
\end{conjectureplus}

\noindent
The special case of Conjecture~\ref{con-jac} for planar graphs was proved
in~\litref{flejac}.

\begin{theoremplus}{{\sc Fleischner \& Jackson} \litref{flejac}}
Let~$G$ be a planar 2-connected graph with minimum degree at least~4.
Then~$G$ contains a removable circuit.\label{th-flejac}
\end{theoremplus}

\noindent
In this paper we will present a proof of Conjecture~\ref{con-jac}. In fact,
we will prove the following stronger result.

\begin{theorem}
Let~$G$ be a 2-connected graph with minimum degree at least~4 and
containing no Petersen minor. Then~$G$ contains~2 edge-disjoint removable
circuits.\label{th-main}
\end{theorem}

\noindent
Theorem~\ref{th-main} follows from an even slightly stronger result, the
exact statement of which can be found in Section~\ref{sec-general}.

The remainder of this paper is organized as follows. In the next section,
we prove a a special case of our main result regarding eulerian graphs
containing no Petersen minor. The general case is proved in
Section~\ref{sec-general}. Section~\ref{sec-remarks} contains some general
remarks, possible extensions and related open problems.

\section{The eulerian case}\label{sec-euler}

The goal of this section is to prove the following result, which is an
important step toward the proof of the general theorem.

\begin{theorem}
Let~$G$ be a 3-connected eulerian graph having no Petersen minor. Then
there exist two edge-disjoint removable circuits in~$G$, each having length
at least~3.\label{th-eu}
\end{theorem}

\noindent
A {\it circuit decomposition\/} of~$G$ is a set of circuits in~$G$ whose
edge sets partition~$\EG$. A {\it hypergraph~$\H$} is a set of
vertices~$V(\H)$ together with a multiset~$E(\H)$ of {\it hyperedges\/}.
Each hyperedge is a nonempty subset of~$V(\H)$. For $A,B\se V(\H)$ we
denote by $[A,B]_\H$ the set of hyperedges in~$\H$ with at least one vertex
in each of~$A$ and~$B$. A hypergraph $\H=(V,E)$ is {\it$k$-edge
connected\/} if for every partition~$(A,B)$ of~$V$ into two nonempty parts
$|[A,B]_\H|\geq k$. If $v\in V$, then $\H-v$ denotes the hypergraph with
vertex set $V\sm\{v\}$ and hyperedge set $\{\,e\sm\{v\}\mid e\in E(\H)$ and
$|e\sm\{v\}|\ge1\,\}$.

\begin{lemma}
Let~$\H$ be a hypergraph of order at least~2. Let $k\geq1$. If~$\H$ is
$k$-edge connected, then there exist two vertices $v_1,v_2$ in~$\H$ such
that both $\H-v_1$ and $\H-v_2$ are $\lceil\half\,k\rceil$-edge
connected.\label{lem-hypgr}
\end{lemma}

\begin{proof}
For $|V(\H)|=2$, the result follows immediately from the definition of
edge-connectivity. Suppose $|V(\H)|\geq3$ and that there exists $v\in
V(\H)$ such that $\H-v$ is not $\lceil\half\,k\rceil$-edge connected. Then
there is a partition~$(A,B)$ of $V(\H)\sm\{v\}$ into nonempty parts such
that $|[A,B]_\H|\leq\lceil\half\,k\rceil-1$. Let~$\H_A$ denote the
hypergraph obtained from~$\H$ by identifying all vertices in $B\cup\{v\}$
with a new vertex~$b$. More precisely, $V(\H_A)=A\cup\{b\}$ and
$E(\H_A)=\{\,e\in E(\H)\mid e\se A\,\}\cup \{\,(e'\cap A)\cup\{b\}
	\mid e'\in [A,B\cup\{v\}]_\H\,\}$. It is straightforward to check
that~$\H_A$ is a $k$-edge connected hypergraph. Since $|V(\H_A)|<|V(\H)|$,
we can inductively find two vertices~$x,y$ in~$V(\H_A)$ such that both
$\H_A-x$ and $\H_A-y$ are $\lceil\half\,k\rceil$-edge connected. We may
assume $x\neq b$, hence $x\in A$. We claim that $\H-x$ is
$\lceil\half\,k\rceil$-edge connected. Suppose this is not true. Then there
is a partition~$(A',B')$ of $V(\H)\sm\{x\}$ into nonempty parts such that
$|[A',B']_\H|\leq\lceil\half\,k\rceil-1$. We may assume $v\in A'$. Set
$B^*=B\cap B'$ and suppose $B^*\neq\emptyset$. By the choice of $A,B,A',B'$
we have $|[A,B^*]_\H|\leq\lceil\half\,k\rceil-1$ and
$|[A',B^*]_\H|\leq\lceil\half\,k\rceil-1$. Since $A\cup A'=V(\H)\sm B^*$,
this implies $|[B^*,V(\H)\sm B^*]_\H|\leq2\,(\lceil\half\,k\rceil-1)\leq
k-1$, contradicting the fact that~$\H$ is $k$-edge connected. Thus we have
$B^*=\emptyset$, hence $B'\subseteq A$. But then $|[B',V(\H_A-x)\sm
B']_{\H_A}|=|[B',A']_\H|\leq\lceil\half\,k\rceil-1$, contradicting
that~$\H_A-x$ is $\lceil\half\,k\rceil$-edge connected. This shows that
$\H-x$ is $\lceil\half\,k\rceil$-edge connected. Similarly, there is a
vertex $x'\in B$ such that $\H-x'$ is $\lceil\half\,k\rceil$-edge
connected, which proves the lemma.
\end{proof}

\begin{lemma}
Let~$G$ be a 3-connected graph containing a circuit decomposition~$\L$ in
which every circuit has length at least~3. Then there exist two circuits
in~$\L$ that are removable in~$G$.\label{lem-eurem}
\end{lemma}

\begin{proof}
We define the hypergraph~$\H_\L$ as follows. Set $V(\H_\L)=\L$ and
$E(\H_\L)=\{\,e_v\mid v\in\VG\,\}$, where $e_v=\{\,C\in\L\mid v\in\VC\,\}$.
Since~$G$ is 3-connected and~$\L$ contains no circuits of length~2, $\H_\L$
is 3-edge connected. Since~$G$ is 3-connected, $\L$ contains at least~2
circuits, hence~$\H_\L$ contains at least~2 vertices. So by
Lemma~\ref{lem-hypgr}, there exist two circuits $C_1,C_2$ in~$\L$ such that
$\H_\L-C_1$ and $\H_\L-C_2$ are 2-edge connected. We will show that this
implies that $G-E(C_1)$ and $G-E(C_2)$ are 2-connected. Suppose that
$G-E(C_1)$ is not 2-connected. Then we can partition the edges
of~$G-E(C_1)$ into two parts~$A,B$ such that $|V(G[A])\cap V(G[B])|\leq1$.
Thus for any circuit~$C$ in $\L\sm\{C_1\}$ we have $\EC\se A$ or $\EC\se
B$. This induces a partition of $V(\H_\L-C_1)$ into two parts such that at
most one hyperedge of $\H_\L-C_1$ intersects both parts, contradicting that
$\H_\L-C_1$ is 2-edge connected. Similarly, $G-E(C_2)$ is 2-connected. Thus
$C_1,C_2\in\L$ are both removable in~$G$.
\end{proof}

\noindent
The following result is a special case of the main result
in~\litref{alsgodzha}.

\begin{theoremplus}{{\sc Alspach, Goddyn \& Zhang} \litref{alsgodzha}}
Let~$G$ be a 2-connected eulerian graph containing no Petersen minor.
Assume further that every edge in~$G$ has multiplicity at most~2. Then
there exists a circuit decomposition~$\L$ of~$G$ such that every circuit
in~$\L$ has length at least~3.\label{th-eucov}
\end{theoremplus}

\noindent
We now can give the proof of Theorem~\ref{th-eu}.

\begin{proofplus}{Theorem~\ref{th-eu}}
Let~$G$ be a 3-connected eulerian graph having no Petersen minor. First
suppose~$G$ contains edges of multiplicity at least~3. Since~$G$ is
3-connected and eulerian, the end vertices of these edges have degree at
least~6. So if we remove two edges from an edge of multiplicity at least~3,
the remaining graph is still 3-connected and eulerian. Moreover, a
removable circuit in the smaller graph is certainly removable in the
original graph. So we can assume that~$G$ has only edges of multiplicity~1
or~2. By Theorem~\ref{th-eucov}, there exists a circuit decomposition~$\L$
of~$G$ such that every circuit in~$\L$ has length at least~3. By
Lemma~\ref{lem-eurem}, there are two circuits in~$\L$ that are removable
in~$G$, proving the theorem.
\end{proofplus}

\begin{remark}
By applying and extending the ideas used in the proofs of the
Claims~\ref{cl-1},~\ref{cl-2}, and~\ref{cl-3} in the proof of
Theorem~\ref{th-mainstr} below, we may replace in Theorem~\ref{th-eu} the
hypothesis that~$G$ is 3-connected with the weaker hypothesis that~$G$ is
2-connected with minimum degree at least~4.\label{rem-eul}
\end{remark}

\section{The general case}\label{sec-general}

In order to eliminate the minimum degree condition in
Theorem~\ref{th-main}, we extend slightly the definition of a removable
circuit; a circuit~$C$ in~$G$ is {\it removable\/} if $G-E(C)$ is the union
of a 2-connected graph with a (\,possibly empty\,) set of isolated
vertices. A {\it digon\/} is a circuit of length two. A digon~$C$ in~$G$ is
{\it lonely\/} if exactly two edges in~$G$ join the two vertices of~$C$. A
circuit is {\it good\/} in~$G$ if it is removable in~$G$ and not a lonely
digon.

The following result immediately implies Theorem~\ref{th-main}.

\begin{theorem}
Let~$G$ be a 2-connected graph different from a circuit and having no
Petersen minor. Suppose~$G$ has exactly $k\in\{0,1\}$ vertices of degree~3.
Then there exist $2-k$ edge-disjoint good circuits
in~$G$.\label{th-mainstr}
\end{theorem}

\noindent
We denote by~$d_G(v)$ the degree of a vertex~$v$ in graph~$G$, and denote
by~$v_i(G)$ the number of vertices in~$G$ having degree~$i$. An {\it edge
cut\/} is the set of edges~$\delta(X)$ having exactly one end vertex
in~$X$, for some $X\se\VG$ with $\emptyset\neq X\neq\VG$; a {\it$k$-edge
cut\/} is an edge cut having cardinality~$k$. Where convenient, we
sometimes identify a circuit by its edge set.

\begin{proofplus}{Theorem \ref{th-mainstr}}
Suppose the theorem is false, and let~$H$ be a counterexample for
which~$|E(H)|$ is minimum.

\newpage

\begin{claim}
$H$ has no 2-edge cut.\label{cl-1}
\end{claim}

\begin{proofopen}
Suppose that $\delta(X_1)=\{e,f\}$ is a 2-edge cut in~$H$. Since~$H$ is
2-connected and not a circuit, $e$ and~$f$ are not parallel. Thus the
graph~$H'$ obtained from~$H$ by contracting~$e$ is loopless and satisfies
the hypothesis of the theorem with $v_3(H')\leq v_3(H)$. By the minimality
of~$H$, $H'$ has $2-v_3(H')$ edge-disjoint good circuits. Expansion of~$e$
transforms these circuits into at least $2-v_3(H)$ edge-disjoint circuits
which are each removable in~$H$. Since~$H$ is a counterexample, one of
these circuits, say~$C_1$, is a lonely digon in~$H$. This can happen only
if each of the two edges~$g,h$ of~$C_1$ induce a triangle with $\{e,f\}$
and $e\cap f$ is a vertex of degree~2 in~$H$. Thus $D_1=\{e,f,g\}$ is a
circuit which is good in~$H$. As~$H$ is a counterexample, we have
$v_3(H)=0$ and thus~$H'$ has a second removable circuit which corresponds
to a removable circuit~$C_2$ in~$H$. The circuit~$C_2$ is edge-disjoint
from~$C_1$ and cannot be a lonely digon. If~$C_2$ is edge-disjoint
from~$D_1$, then we are done. So we may assume that~$C_2$ contains~$e$
and~$f$. But now $C_2-\{e,f\}+g$ is a good circuit in~$H$ edge-disjoint
from~$D_1$, a contradiction.
\end{proofopen}

\noindent
Note that in particular Claim~\ref{cl-1} implies that~$H$ has no vertex of
degree~2.

\begin{claim}
$H$ has no pair $y\in\VH$, $e\in E(H)$ such that $H-y-e$ is
disconnected.\label{cl-2}
\end{claim}

\begin{proofopen}
Suppose that $y,e$ is such a pair. Let $X_1,X_2\se\VH$ be such that
$|X_1|,|X_2|\geq2$, $X_1\cup X_2=\VH$, $X_1\cap X_2=\{y\}$, and~$e$ is the
unique edge in~$H$ with an end vertex in $X_1\sm\{y\}$ and an end vertex in
$X_2\sm\{y\}$. By Claim~\ref{cl-1}, $H[X_1]$ and~$H[X_2]$ contain at
least~2 edges. For $i=1,2$, let~$x_i$ denote the end vertex of~$e$
in~$X_i$, and define~$H_i$ to be the graph obtained from~$H[X_i]$ by adding
a new vertex~$u_i$ and two new edges~$u_iy$ and~$u_ix_i$. By
Claim~\ref{cl-1}, at least two edges join~$y$ to other vertices in~$X_i$,
so $d_H(y)\ge4$ and $d_{H_i}(y)\ge3$, $i=1,2$. To obtain a contradiction,
it suffices to show for $i=1,2$ that if no vertex in $V(H_i)\sm\{y\}$ has
degree~3 in~$H_i$, then~$H[X_i]$ contains a circuit which is good in~$H$.
Suppose $v_3(H_i)=0$. Since~$H$ is 2-connected, $H_i$ is 2-connected and
satisfies the hypothesis of the theorem. By the minimality of~$H$, $H_i$
has~2 edge-disjoint good circuits. One of these two circuits does not
contain~$u_i$, and is therefore removable in~$H$. By construction of~$H_i$,
this circuit is not a lonely digon and is thus good in~$H$, a
contradiction. Thus we may assume $v_3(H_i)=1$ and $d_{H_i}(y)=3$. By the
minimality of~$H$, $H_i$ has a good circuit. Since this circuit does not
contain~$y$, it is removable in~$H$. Again, by construction of~$H_i$, this
circuit is a good circuit in~$H$, a contradiction.
\end{proofopen}

\begin{claim}
$H$ is 3-connected.\label{cl-3}
\end{claim}

\begin{proofopen}
Suppose $\{x,y\}$ is a vertex cut in~$H$. Let $X_1,X_2\se\VH$ be such that
$|X_1|,|X_2|\ge3$, $X_1\cup X_2=\VH$, $X_1\cap X_2=\{x,y\}$, and no edge
of~$H$ has an end vertex in $X_1\sm\{x,y\}$ and an end vertex in
$X_2\sm\{x,y\}$. Applying Claim~\ref{cl-2}, at least two edges join~$x$ to
a vertex in $X_i\sm\{x,y\}$, $i=1,2$. A similar statement holds for~$y$.
Let~$H'$ be the graph obtained from~$H$ by deleting all edges joining~$x$
to~$y$. Then $d_{H'}(x),d_{H'}(y)\ge4$ and so $v_3(H')=v_3(H)$. The
hypothesis of the theorem is satisfied by~$H'$. If $H'\ne H$, then by
minimality, there are $2-v_3(H)$ edge-disjoint good circuits in~$H'$. These
circuits are also good in~$H$, a contradiction. Thus we have shown that
\begin{semieq}
$H$ has no edge joining~$x$ to~$y$.\label{2}
\end{semieq}
For $i=1,2$, we define~$H_i$ to be the graph obtained from~$H[X_i]$ by
adding two new edges $e_i,f_i$, each joining~$x$ to~$y$. For $i=1,2$ we
have $d_{H_i}(x),d_{H_i}(y)\ge4$, so~$H_i$ satisfies the hypothesis of the
theorem, and has strictly fewer edges than~$H$ has. Furthermore,
$v_3(H_1)+v_3(H_2)=v_3(H)\le1$, so we may assume $v_3(H_1)=0$ and
$v_3(H_2)=v_3(H)$. Thus~$H_i$ has $2-v_3(H_i)$ good circuits, $i=1,2$. We
have three observations regarding these $4-v_3(H)$ circuits in
$H_1\cup H_2$. First, by~\eqref{2}, none of these circuits contains more
than one edge from $\{e_1,f_1,e_2,f_2\}$. Secondly, if any one of these
circuits does not contain any of $e_1,f_1,e_2,f_2$, then that circuit is
also good in~$H$. Thirdly, if one of these circuits, say~$D_1$, contains
exactly one of $e_1,f_1$ and another of these circuits, say~$D_2$, contains
exactly one of $e_2,f_2$, then $D_1\cup D_2-\{e_1,f_1,e_2,f_2\}$ is good
in~$H$. Applying these three observations to the $4-v_3(H)$ circuits
obtained above, one can construct in all cases $2-v_3(H)$ edge-disjoint
good circuits in~$H$, achieving the desired contradiction.
\end{proofopen}

\noindent
In what follows, an edge $e=uv$ of~$H$ is called an {\it $(a,b)$-edge\/} if
$d_H(u)=a$ and $d_H(v)=b$.

\begin{claim}
$H$ has no $(a,b)$-edge with $a,b\ge5$.\label{cl-5}
\end{claim}

\begin{proofopen}
If~$e$ is such an edge, then, since~$H$ is 3-connected, $H-e$ satisfies the
hypothesis with $v_3(H-e)=v_3(H)$. By the minimality of~$H$, $H-e$ has
$2-v_3(H-e)$ edge-disjoint good circuits. Each of these circuits is also
good in~$H$, a contradiction.
\end{proofopen}

\newpage

\begin{claim}
$H$ has no edge of multiplicity greater than~2.\label{cl-4}
\end{claim}

\begin{proofopen}
Suppose that $u,v\in\VH$ are joined by at least three edges. By
Claim~\ref{cl-3}, $u$ and~$v$ each have at least two neighbors in
$\VH\sm\{u,v\}$, so $d_H(u),d_H(v)\ge5$, contradicting Claim~\ref{cl-5}.
\end{proofopen}

\begin{claim}
$H$ has no $(3,b)$-edge with $b\ge5$.\label{cl-6}
\end{claim}

\begin{proofopen}
If $e=uv$ is such an edge and $d_H(u)=3$, then $H-e$ satisfies the
hypothesis with $v_3(H-e)=v_3(H)-1=0$. By minimality, $H-e$ has two good
circuits. At least one of these circuits does not contain~$u$; this circuit
is good in~$H$, a contradiction.
\end{proofopen}

\begin{claim}
$H$ has no $(3,4)$-edge.\label{cl-7}
\end{claim}

\begin{proofopen}
Suppose $e=uv$ is such an edge where $d_H(u)=3$. Then $H-e$ satisfies the
hypothesis with $v_3(H-e)=v_3(H)=1$. By minimality, $H-e$ has a good
circuit~$C$. If~$C$ does not contain~$u$, then~$C$ is good in~$H$, a
contradiction. Thus we assume $u\in\VC$. We distinguish two cases.

\smallskip
{\sl Case 1\,:\mbox{ \ }$C$ contains a vertex~$w$ with $d_H(w)\ge5$.}\\*
Let~$P$ be a $u,w$-path in~$C$ and assume that~$w$ has been chosen such
that every vertex in $V(P)\sm\{u,w\}$ has degree~4 in~$H$. Since~$C$ is
removable in $H-e$, and therefore removable in~$H$, the graph $H'=H-E(P)$
is 2-connected and satisfies the hypothesis of the theorem with
$v_3(H')=v_3(H)-1=0$. By the minimality of~$H$, $H'$ contains two
edge-disjoint good circuits. Since $d_{H'}(u)=2$, one of these two
circuits, say~$C_1$, does not contain~$u$. One easily checks that~$C_1$ is
a good circuit in~$H$.

\smallskip
{\sl Case 2\,:\mbox{ \ }Every vertex in $\VC\sm\{u\}$ has degree~4
in~$H$.}\\*
Let $f=ux$ be an edge of~$C$ incident with~$u$ and let~$P$ be the path
$C-f$. Again the graph $H'=H -E(P)$ satisfies the hypothesis of the
theorem, but now $v_3(H')=v_3(H)=1$. By the minimality of~$H$, $H'$ has a
good circuit~$C_1$. Since $d_{H'}(x)=3$ and $d_{H'}(u)=2$, $C_1$ does not
contain~$x$ and therefore~$C_1$ does not contain~$u$. This implies
that~$C_1$ is a good circuit in~$H$.

\smallskip
In either case we contradict~$H$ being a counterexample, proving
Claim~\ref{cl-7}.
\end{proofopen}

\newpage

\begin{claim}
$H$ is 4-regular.\label{cl-8}
\end{claim}

\begin{proofopen}
By Claims \ref{cl-1},~\ref{cl-6} and~\ref{cl-7}, $H$ has minimum degree~4
and thus $v_3(H)=0$. Suppose~$e$ is a $(4,b)$-edge with $b\ge5$. Then $H-e$
satisfies the induction hypothesis with $v_3(H-e)=1$, so $H-e$ contains a
good circuit~$C$. One easily checks that~$C$ is good in~$H$. We aim to find
two edge-disjoint good circuits in~$H$. It is possible that neither of them
will equal~$C$. We consider three cases.

\smallskip
{\sl Case 1\,:\mbox{ \ }$C$ contains two distinct vertices $v,w$ with
$d_H(v),d_H(w)\ge5$.}\\*
Let~$P$ be a $v,w$-path in~$C$ and assume that all vertices in
$V(P)\sm\{v,w\}$ have degree~4 in~$H$. Since~$C$ is removable in~$H$, the
graph $H'=H-E(P)$ satisfies the hypothesis of the theorem with
$v_3(H')=v_3(H)=0$. By the minimality of~$H$, $H'$ has two edge-disjoint
good circuits, and these two circuits are also edge-disjoint and good
in~$H$.

\smallskip
{\sl Case 2\,:\mbox{ \ }$C$ contains exactly one vertex~$w$ with
$d_H(w)\ge5$.}\\*
Let $e=wv$ be an edge of~$C$ incident with~$w$ and let $P=C-e$. Then
$H-E(P)$ satisfies the hypothesis of the theorem with $v_3(H')=v_3(H)+1=1$.
Thus~$H'$ contains a good circuit~$C'$, and this circuit is also good
in~$H$. Since $d_{H'}(v)=3$, $C'$ does not contain~$e$, and so~$C'$ is edge
disjoint from~$C$. Hence~$C$ and~$C'$ are edge-disjoint good circuits
in~$H$.

\smallskip
{\sl Case 3\,:\mbox{ \ }All vertices in~$C$ have degree~4 in~$H$.}\\* Let
$H'=H-\EC$. Since~$C$ is removable in~$H$, $H'$ is 2-connected and
satisfies the hypothesis with $v_3(H')=v_3(H)=0$. Thus~$H'$ has two
edge-disjoint good circuits $C_1, C_2$. We claim that one of these is
removable, and hence good in $H$. As $C_1$,~$C_2$ and~$C$ are edge-disjoint
in~$H$, and $d_H(v)=4$ for each $v\in\VH$, each vertex in~$C$ is belongs to
at most one of $C_1,C_2$. Since~$C$ is not a lonely digon, Claim~\ref{cl-4}
implies that $C$ has length at least~3. Therefore either~$C_1$ or~$C_2$,
say~$C_1$, satisfies $|\VC\sm V(C_1)|\ge\lceil\half\,|\VC|\rceil\ge2$. Thus
there are at least two distinct vertices in $C$ which belong to the
non-trivial 2-connected component of $H'-E(C_1)$. It follows that
$H-E(C_1)$ has exactly one non-trivial component, and this component is
2-connected. Thus~$C_1$ is removable in~$H$ as claimed, and $C,C_1$ are
edge-disjoint good circuits in~$H$.

\smallskip
In each case we have contradicted~$H$ being a counterexample, and
Claim~\ref{cl-8} is proved.
\end{proofopen}

\noindent
The theorem now follows immediately from Claims~\ref{cl-3} and~\ref{cl-8}
and Theorem~\ref{th-eu}.
\end{proofplus}

\section{Remarks}\label{sec-remarks}

This section contains some relevant examples, conjectures and extensions.

\subsection{Some examples}

The connectivity requirement in Lemma~\ref{lem-eurem} is necessary. For
example, the graph of Figure~\ref{fig2}
\begin{figure}[htb]
\vspace{10pt}
\centerline{
\setlength{\unitlength}{0.15mm}%
%Doubled Petersen with doubled spokes
%Has a faithful circuit cover, but no removable circuit
\begin{picture}(438.6,278.2)(-119.3,-139.1)
\linethickness{1.1\unitlength}
\put(-113.3,82.3){\vertex}\put(-113.3,-82.3){\vertex}
\put(43.3,-133.1){\vertex}\put(140.0,0.0){\vertex}
\put(43.3,133.1){\vertex}
%
\put(313.3,82.3){\vertex}\put(313.3,-82.3){\vertex}
\put(156.7,-133.1){\vertex}\put(60.0,0.0){\vertex}
\put(156.7,133.1){\vertex}
%
\put(-48.5,35.3){\vertex}\put(-48.5,-35.3){\vertex}
\put(18.5,-57.1){\vertex}\put(18.5,57.1){\vertex}
%
\put(248.5,35.3){\vertex}\put(248.5,-35.3){\vertex}
\put(181.5,-57.1){\vertex}\put(181.5,57.1){\vertex}
%
\put(-113.3,82.3){\line(0,-1){164.6}}
\bezier{165}(-113.3,-82.3)(-35.0,-107.7)(43.3,-133.1)
\bezier{165}(43.3,-133.1)(91.65,-66.55)(140.0,0.0)
\bezier{165}(140.0,0.0)(91.65,66.55)(43.3,133.1)
\bezier{165}(43.3,133.1)(-35.0,107.7)(-113.3,82.3)
%
\put(313.3,82.3){\line(0,-1){164.6}}
\bezier{165}(313.3,-82.3)(235.0,-107.7)(156.7,-133.1)
\bezier{165}(156.7,-133.1)(108.35,-66.55)(60.0,0.0)
\bezier{165}(60.0,0.0)(108.35,66.55)(156.7,133.1)
\bezier{165}(156.7,133.1)(235.0,107.7)(313.3,82.3)
%
\bezier{114}(-48.5,35.3)(5.75,17.75)(60.0,0.0)
\bezier{114}(60.0,0.0)(5.75,-17.75)(-48.5,-35.3)
\bezier{114}(-48.5,-35.3)(-15.0,10.9)(18.5,57.1)
\put(18.5,57.1){\line(0,-1){114.2}}
\bezier{114}(18.5,-57.1)(-15.0,-10.9)(-48.5,35.3)
%
\bezier{114}(248.5,35.3)(194.25,17.75)(140.0,0.0)
\bezier{114}(140.0,0.0)(194.25,-17.75)(248.5,-35.3)
\bezier{114}(248.5,-35.3)(215.0,10.9)(181.5,57.1)
\put(181.5,57.1){\line(0,-1){114.2}}
\bezier{114}(181.5,-57.1)(215.0,-10.9)(248.5,35.3)
%
\bezier{82}(-113.3,82.3)(-88.3,46.9)(-48.5,35.3)
\bezier{82}(-113.3,82.3)(-71.9,69.5)(-48.5,35.3)
\bezier{82}(-113.3,-82.3)(-88.3,-46.9)(-48.5,-35.3)
\bezier{82}(-113.3,-82.3)(-71.9,-69.5)(-48.5,-35.3)
\bezier{82}(43.3,-133.1)(17.4,-98.5)(18.5,-57.1)
\bezier{82}(43.3,-133.1)(43.8,-89.9)(18.5,-57.1)
\bezier{82}(43.3,133.1)(17.4,98.5)(18.5,57.1)
\bezier{82}(43.3,133.1)(43.8,89.9)(18.5,57.1)
%
\bezier{82}(313.3,82.3)(288.3,46.9)(248.5,35.3)
\bezier{82}(313.3,82.3)(271.9,69.5)(248.5,35.3)
\bezier{82}(313.3,-82.3)(288.3,-46.9)(248.5,-35.3)
\bezier{82}(313.3,-82.3)(271.9,-69.5)(248.5,-35.3)
\bezier{82}(156.7,-133.1)(182.6,-98.5)(181.5,-57.1)
\bezier{82}(156.7,-133.1)(156.2,-89.9)(181.5,-57.1)
\bezier{82}(156.7,133.1)(182.6,98.5)(181.5,57.1)
\bezier{82}(156.7,133.1)(156.2,89.9)(181.5,57.1)
\end{picture}
}
\begin{capt}
A 2-connected graph containing circuit decompositions in which every
circuit has length at least~3, but containing no removable circuit of
length at least~3.\labl{fig2}
\end{capt}
\vspace{5pt}
\end{figure}%
has four distinct circuit decompositions into circuits of length at least
three. In each of these decompositions~$\L$, the hypergraph~$\H_\L$ is a
circuit with multiple edges so no circuit in~$\L$ is removable. In fact,
the graph has no removable circuits at all except for lonely digons.

Conversely, Figure~\ref{fig3}
\begin{figure}[htb]
\vspace{10pt}
\centerline{
\setlength{\unitlength}{0.15mm}%
%Doubled Petersen with doubled spokes
%Has no faithful circuit cover,but a removable circuit
\begin{picture}(455.3,278.2)(-119.3,-139.1)
\linethickness{1.1\unitlength}
\put(-113.3,82.3){\vertex}\put(-113.3,-82.3){\vertex}
\put(43.3,-133.1){\vertex}\put(43.3,133.1){\vertex}
%
\put(86.7,82.3){\vertex}\put(86.7,-82.3){\vertex}
\put(243.3,-133.1){\vertex}\put(340.0,0.0){\vertex}
\put(243.3,133.1){\vertex}
%
\put(-48.5,35.3){\vertex}\put(-48.5,-35.3){\vertex}
\put(18.5,-57.1){\vertex}\put(18.5,57.1){\vertex}
%
\put(151.5,35.3){\vertex}\put(151.5,-35.3){\vertex}
\put(218.5,-57.1){\vertex}\put(218.5,57.1){\vertex}
\put(260.0,0.0){\vertex}
%
\put(-113.3,82.3){\line(0,-1){164.6}}
\bezier{165}(-113.3,-82.3)(-35.0,-107.7)(43.3,-133.1)
\bezier{165}(43.3,133.1)(-35.0,107.7)(-113.3,82.3)
%
\linethickness{4.4\unitlength}
\bezier{165}(86.7,-82.3)(165.0,-107.7)(243.3,-133.1)
\linethickness{1.1\unitlength}
\bezier{165}(243.3,-133.1)(291.65,-66.55)(340.0,0.0)
\bezier{165}(340.0,0.0)(291.65,66.55)(243.3,133.1)
\linethickness{4.4\unitlength}
\bezier{165}(243.3,133.1)(165.0,107.7)(86.7,82.3)
%
\linethickness{1.1\unitlength}
\bezier{114}(-48.5,-35.3)(-15.0,10.9)(18.5,57.1)
\put(18.5,57.1){\line(0,-1){114.2}}
\bezier{114}(18.5,-57.1)(-15.0,-10.9)(-48.5,35.3)
%
\bezier{114}(151.5,35.3)(205.75,17.75)(260.0,0.0)
\bezier{114}(260.0,0.0)(205.75,-17.75)(151.5,-35.3)
\linethickness{4.4\unitlength}
\bezier{114}(151.5,-35.3)(185.0,10.9)(218.5,57.1)
\bezier{114}(218.5,-57.1)(185.0,-10.9)(151.5,35.3)
%
\linethickness{1.1\unitlength}
\bezier{82}(-113.3,82.3)(-88.3,46.9)(-48.5,35.3)
\bezier{82}(-113.3,82.3)(-71.9,69.5)(-48.5,35.3)
\bezier{82}(-113.3,-82.3)(-88.3,-46.9)(-48.5,-35.3)
\bezier{82}(-113.3,-82.3)(-71.9,-69.5)(-48.5,-35.3)
\bezier{82}(43.3,-133.1)(17.4,-98.5)(18.5,-57.1)
\bezier{82}(43.3,-133.1)(43.8,-89.9)(18.5,-57.1)
\bezier{82}(43.3,133.1)(17.4,98.5)(18.5,57.1)
\bezier{82}(43.3,133.1)(43.8,89.9)(18.5,57.1)
%
\bezier{82}(86.7,82.3)(111.7,46.9)(151.5,35.3)
\linethickness{4.4\unitlength}
\bezier{82}(86.7,82.3)(128.1,69.5)(151.5,35.3)
\linethickness{1.1\unitlength}
\bezier{82}(86.7,-82.3)(111.7,-46.9)(151.5,-35.3)
\linethickness{4.4\unitlength}
\bezier{82}(86.7,-82.3)(128.1,-69.5)(151.5,-35.3)
\bezier{82}(243.3,-133.1)(217.4,-98.5)(218.5,-57.1)
\linethickness{1.1\unitlength}
\bezier{82}(243.3,-133.1)(243.8,-89.9)(218.5,-57.1)
\linethickness{4.4\unitlength}
\bezier{82}(243.3,133.1)(217.4,98.5)(218.5,57.1)
\linethickness{1.1\unitlength}
\bezier{82}(243.3,133.1)(243.8,89.9)(218.5,57.1)
\bezier{82}(340.0,0.0)(299.0,13.9)(260.0,0.0)
\bezier{82}(340.0,0.0)(299.0,-13.9)(260.0,0.0)
%
\bezier{268}(-48.5,35.3)(85.0,46.2)(218.5,57.1)
\bezier{268}(-48.5,-35.3)(85.0,-46.2)(218.5,-57.1)
%
\bezier{67}(43.3,133.1)(65.0,107.7)(86.7,82.3)
\bezier{67}(43.3,-133.1)(65.0,-107.7)(86.7,-82.3)
%
\end{picture}
}
\begin{capt}
A 2-connected graph containing no circuit decomposition in which all
circuits have length at least~3, but containing a removable circuit
(\,shown in bold\,) of length at least~3.\labl{fig3}
\end{capt}
\vspace{5pt}
\end{figure}%
depicts an eulerian graph which has a removable circuit of length at least
three, even though every circuit decomposition must use a lonely digon.

If~$G$ is a graph having no {\it good\/} circuit (\,in the sense of
Theorem~\ref{th-mainstr}\,), then we may obtain a graph having no removable
circuit at all by replacing all lonely digons with two lonely digons which
are ``in series'', in the manner of the graph of Figure~\ref{fig1}. An
alternative view is to replace each lonely digon in~$G$ with an edge of
weight~2. This raises a more general problem.

\begin{problem}
Which 2-connected edge-weighted graphs~$(G,p)$,
$p:E\rightarrow\{1,2,\ldots\}$, have a circuit~$C$ such that
$G-(E(C)\cap p^{-1}(1))$ is 2-connected\,?\label{qu-ew}
\end{problem}

\noindent
A {\it faithful circuit cover\/} of an edge-weighted graph~$(G,p)$ is a list of
circuits such that each $e\in\EG$ is in exactly~$p(e)$ of the circuits in
the list. A strengthened form of Lemma~\ref{lem-eurem} holds here. We omit
the proof as it is similar to that of Lemma~\ref{lem-eurem}, with regard to
Remark~\ref{rem-eul}, and using the more general statement of
Theorem~\ref{th-eucov} found in~\litref{alsgodzha}.

\begin{lemma}
Suppose~$(G,p)$ has a faithful circuit cover, where~$G$ is 2-connected and has no
Petersen minor. Then~$(G,p)$ has a faithful circuit cover $(C_1,C_2,\ldots,C_k)$
such that, for each $i=1,2,\ldots,k$, $C_1\cup C_2\cup\cdots\cup C_i$ is a
2-connected subgraph of~$G$.\label{lem-circ}
\end{lemma}

\noindent
This result cannot be extended to graphs which have Petersen minors, as
demonstrated by the graph of Figure~\ref{fig4}.
\begin{figure}[htb]
\vspace{10pt}
\centerline{
\setlength{\unitlength}{0.15mm}%
% Two Petersen's with a bridge connected
% No faithful circuit cover which allows removing circuit one by one
\begin{picture}(578.2,265.3)(-139.1,-119.3)
\linethickness{1.1\unitlength}
\put(-82.3,-113.3){\vertex}\put(82.3,-113.3){\vertex}
\put(133.1,43.3){\vertex}\put(0.0,140.0){\vertex}
\put(-133.1,43.3){\vertex}
%
\put(-35.3,-48.5){\vertex}\put(35.3,-48.5){\vertex}
\put(57.1,18.5){\vertex}\put(0.0,60.0){\vertex}
\put(-57.1,18.5){\vertex}
%
\put(-82.3,-113.3){\line(1,0){164.8}}
\bezier{165}(82.3,-113.3)(107.7,-35.0)(133.1,43.3)
\bezier{165}(133.1,43.3)(66.55,91.65)(0.0,140.0)
\bezier{165}(0.0,140.0)(-66.55,91.65)(-133.1,43.3)
\bezier{165}(-133.1,43.3)(-107.7,-35.0)(-82.3,-113.3)
%
\bezier{114}(-35.3,-48.5)(-17.75,5.75)(0.0,60.0)
\bezier{114}(0.0,60.0)(17.75,5.75)(35.3,-48.5)
\bezier{114}(35.3,-48.5)(-10.9,-15.0)(-57.1,18.5)
\put(-57.1,18.5){\line(1,0){114.2}}
\bezier{114}(57.1,18.5)(10.9,-15.0)(-35.3,-48.5)
%
\put(0.0,60.0){\line(0,1){80}}
%
\linethickness{4.4\unitlength}
\bezier{41}(-82.3,-113.3)(-58.8,-80.9)(-35.3,-48.5)
\bezier{41}(82.3,-113.3)(58.8,-80.9)(35.3,-48.5)
\bezier{41}(133.1,43.3)(95.1,30.9)(57.1,18.5)
\bezier{41}(-133.1,43.3)(-95.1,30.9)(-57.1,18.5)
%
\linethickness{1.1\unitlength}
\put(217.7,-113.3){\vertex}\put(382.3,-113.3){\vertex}
\put(433.1,43.3){\vertex}\put(300.0,140.0){\vertex}
\put(166.9,43.3){\vertex}
%
\put(264.7,-48.5){\vertex}\put(335.3,-48.5){\vertex}
\put(357.1,18.5){\vertex}\put(300.0,60.0){\vertex}
\put(242.9,18.5){\vertex}
%
\put(217.7,-113.3){\line(1,0){164.8}}
\bezier{165}(382.3,-113.3)(407.7,-35.0)(433.1,43.3)
\bezier{165}(433.1,43.3)(366.55,91.65)(300.0,140.0)
\bezier{165}(300.0,140.0)(233.45,91.65)(166.9,43.3)
\bezier{165}(166.9,43.3)(192.3,-35.0)(217.7,-113.3)
%
\bezier{114}(264.7,-48.5)(282.25,5.75)(300.0,60.0)
\bezier{114}(300.0,60.0)(317.75,5.75)(335.3,-48.5)
\bezier{114}(335.3,-48.5)(289.1,-15.0)(242.9,18.5)
\put(242.9,18.5){\line(1,0){114.2}}
\bezier{114}(357.1,18.5)(310.9,-15.0)(264.7,-48.5)
%
\put(300.0,60.0){\line(0,1){80}}
%
\linethickness{4.4\unitlength}
\bezier{41}(217.7,-113.3)(241.2,-80.9)(264.7,-48.5)
\bezier{41}(382.3,-113.3)(358.8,-80.9)(335.3,-48.5)
\bezier{41}(433.1,43.3)(395.1,30.9)(357.1,18.5)
\bezier{41}(166.9,43.3)(204.9,30.9)(242.9,18.5)
%
\linethickness{1.1\unitlength}
\put(0.0,60.0){\line(1,0){300}}
\put(0.0,140.0){\line(1,0){300}}
\end{picture}
}
\begin{capt}
A 2-connected edge-weighted graph (\,thin edges have weight~1, bold edges
have weight~2\,) having a faithful circuit cover, but no faithful circuit cover that
satisfies the properties in Lemma~\protect\ref{lem-circ}.\labl{fig4}
\end{capt}
\vspace{5pt}
\end{figure}%
However, it could be the case that the conclusion holds true for all
3-connected weighted graphs~$(G,p)$ which have a faithful circuit cover.

\subsection{Petersen Conjectures}

We denote by~$\P$ the 4-regular multigraph obtained from Petersen's graph
by duplicating each of the five edges in one of its 1-factors. It is clear
that~$\P$ plays a central role in the examples in the previous subsection.
This observation and a lack of counterexamples tempt us to venture the
following.

\begin{conjecture}
If~$G$ is a 3-connected graph with minimum degree at least~4 and~$G$ has no
removable circuit different from a lonely digon, then~$G$ is isomorphic
to\/~$\P$ or may be obtained from copies of\/~$\P$ via repeated
applications of the graph composition operation depicted in
Figure~\ref{fig5}.\label{con-pete}
\end{conjecture}

%\noindent
%An example of such a composition operation is depicted in
%Figure~\ref{fig5}. At this time we know of no other such operation which
%preserves 3-connectivity.

\begin{figure}[htb]
\vspace{10pt}
\centerline{
\setlength{\unitlength}{0.15mm}%
% My feeble attempt at a picture
\begin{picture}(810,195)(-380,-115)
\linethickness{1.1\unitlength}
% G_1
\put(-330,0){\oval(100,160)}
\put(-220,0){\line(-2,1){80}}\put(-220,0){\line(-2,-1){80}}
\bezier{100}(-300,0)(-270,12)(-220,0)
\bezier{100}(-300,0)(-270,-12)(-220,0)
\put(-220,0){\vertex}
\put(-300,-40){\vertex}\put(-300,0){\vertex}\put(-300,40){\vertex}
% G_2
\put(-70,0){\oval(100,160)}
\put(-180,0){\line(2,1){80}}\put(-180,0){\line(2,-1){80}}
\bezier{100}(-180,0)(-130,12)(-100,0)
\bezier{100}(-180,0)(-130,-12)(-100,0)
\put(-180,0){\vertex}
\put(-100,-40){\vertex}\put(-100,0){\vertex}\put(-100,40){\vertex}
% G
\put(170,0){\oval(100,160)}\put(380,0){\oval(100,160)}
\put(200,40){\line(1,0){150}}\put(200,-40){\line(1,0){150}}
\bezier{150}(200,0)(275,20)(350,0)\bezier{150}(200,0)(275,-20)(350,0)
\put(200,-40){\vertex}\put(200,0){\vertex}\put(200,40){\vertex}
\put(350,-40){\vertex}\put(350,0){\vertex}\put(350,40){\vertex}
% Labels
\put(-300,-110){\makebox(0,0){$G_1$}}
\put(-100,-110){\makebox(0,0){$G_2$}}
\put( 275,-110){\makebox(0,0){$G$}}
\put(30,0){\vector(1,0){40}}\put(30,-4){\line(0,1){8}}
\
\end{picture}
}
\begin{capt}
If neither~$G_1$ nor~$G_2$ has a removable circuit different from a lonely
digon, then neither has~$G$.
\labl{fig5}
\end{capt}
\vspace{5pt}
\end{figure}%

An apparently weaker conjecture seems to contain much of the difficulty of
Conjecture~\ref{con-pete}. This unpublished conjecture was posed by
Goddyn~\litref{godlec}, and is weaker than a conjecture of Fleischner and
Jackson (\,see Conjecture~12 in~\litref{fle}\,).

Let~$\sigma$ be a permutation of $\{1,\ldots,n\}$. A {\it$\sigma$-prism\/}
is the graph obtained from two disjoint circuits $(v_1v_2\cdots v_nv_1)$,
$(u_1u_2\cdots u_nu_1)$ by adding a digon between vertices $v_i$ and
$u_{\sigma(i)}$, for $i=1,\ldots,n$.

\begin{conjecture}
Let~$H$ be a $\sigma$-prism with $n\ge2$ having no removable circuit
different from a digon. Then $H\cong\P$.\label{con-prism}
%Let~$H$ be a 4-regular graph which can be edge-decomposed into two
%Hamilton circuits,~$C$ and~$D$. Suppose that $H-E(Z)$ has a cut-vertex, for
%any circuit~$Z$ whose edges alternate between~$C$ and~$D$. Then~$H$ is
%isomorphic with~$K_5$.
\end{conjecture}

\noindent
%To see how Conjecture \ref{con-prism} follows from
%Conjecture~\ref{con-pete}, we obtain from~$H$ a ``generalized prism''~$G_H$
%by expanding each vertex of~$H$ into a digon in such a way that~$E(C)$
%and~$E(D)$ induce vertex-disjoint circuits in the resulting 4-regular
%graph. For example, if $H=K_5$ and~$C,D$ are circuits of length~$5$, then
%$G_H\cong\P$.
Conjecture \ref{con-prism}, which we call the ``Prism Conjecture'', is
known to hold true whenever the underlying simple graph of~$H$ is 3-edge
colorable or has no Petersen minor~\litref{alsgodzha}. Little else appears
to be known regarding Conjecture~\ref{con-prism}.

\subsection{Complexity}

Determining whether a graph contains a Petersen minor can be done in
polynomial time~\litref{seyrob}, so there exists a polynomial time
algorithm to decide whether a given graph satisfies the hypothesis of
Theorem~\ref{th-mainstr}. By our results we know that such a graph contains
a removable circuit. On the other hand, the complexity of the following
problem is unknown.

\begin{trivlist}\item[]
\wideitem{\bf(P1)}\sl
Given a 2-connected graph~$G$ with minimum degree at least~4 and containing
no Petersen minor, find a circuit~$C$ such that $G-E(C)$ is 2-connected.
\end{trivlist}

\noindent
This is in contrast to the published proofs of Theorems~\ref{th-jac},
\ref{th-thotof} and~\ref{th-flejac}, all of which translate to
polynomial time algorithms for finding removable circuits.

It is the application of Theorem~\ref{th-eucov} which hinders a conversion
of the proof of Theorem~\ref{th-mainstr} into a polynomial algorithm
for~(P1). More precisely, the proof of Theorem~\ref{th-mainstr} entails a
polynomial reduction of~(P1) to the following construction problem for
Theorem~\ref{th-eucov}.

\begin{trivlist}\item[]
\wideitem{\bf(P2)}\sl
Given a 3-connected 4-regular graph~$G$ containing no Petersen minor, find
a decomposition of~$G$ into circuits of length at least~3.
\end{trivlist}

\noindent
However, (P2) is of unknown complexity~\litref{alsgodzha}. Circumventing
this problem appears to require a completely different proof of
Theorem~\ref{th-eu}.

\subsection{Extension to matroids}

J.~Oxley proposed the following problem in~\litref{oxl} (\,see this book
for definitions and notation\,). The {\it cogirth\/} of a matroid~$M$ is
the minimum cardinality of a cocircuit in~$M$.

\begin{problemplus}{{\sc Oxley} \litrefplus{oxl}{(14.4.8)}}
Let~$M$ be a simple connected binary matroid having cogirth at least~4.
Does~$M$ have a circuit~$C$ such that $M\sm C$ is
connected\,?\label{qu-mat}
\end{problemplus}

\noindent
For graphic matroids, Problem~\ref{qu-mat} is answered in the affirmative
by any of the Theorems~\ref{th-jac} to~\ref{th-thotof}. In fact, the
condition ``having cogirth at least~4'' translates to the condition ``is
4-edge connected'' for graphs, which means that the conditions in
Problem~\ref{qu-mat} for graphs are more restrictive than those in
Theorem~\ref{th-jac}.

For cographic matroids, Problem~\ref{qu-mat} translates as follows. A
circuit~$T$ in $M^*(G)$ corresponds to a {\it bond\/} (\,a minimal edge
cut\,) in~$G$. The matroid $M^*(G)\sm T$ is connected if and only if either
$|E(G\contr T)|=1$ or $G\contr T$ is loopless and 2-connected.
Here~$G\contr T$ denotes the graph obtained from~$G$ by contracting all
edges in~$T$, but not deleting any resulting multiple edges and loops.

\begin{problem}
Let~$G$ be a 2-connected, 3-edge connected graph with girth at least~4.
Does~$G$ contain a bond~$B$ such that $G\contr B$ is
2-connected\,?\label{con-ox}
\end{problem}

\noindent
The answer to Problem~\ref{con-ox} (\,and Problem~\ref{qu-mat}\,) is ``no''
in general. The following counterexample, due to M.~Lemos, was communicated
to us by J.~Oxley in December, 1995. Let~$H$ be the complete bipartite
graph with vertex partition $(X_1,X_2)$ where $|X_1|=|X_2|=5$. For $i=1,2$
and for each 3-subset $S\se X_i$, we add to~$H$ two new vertices~$x_S,y_S$,
and add a new edge joining each of the six pairs in $\{x_S,y_S\}\times S$.
Contracting any bond in the resulting graph results in a graph which is not
2-connected.

Extending the main result of this paper to matroids entails removing the
word ``simple'' from Problem~\ref{qu-mat}, and removing the requirement
``3-edge connected'' from Problem~\ref{con-ox}. Here, there is a much
smaller cographic counterexample which seems to play a role analogous to
that played by the graph~$\P$ in the graphic case.

Let~$B$ be a bond of cardinality six in~$K_5$, and let~$G$ be the graph
obtained from~$K_5$ by duplicating each edge in $E(K_5)-B$ and then
subdividing both edges of each resulting digon exactly once. Then~$G$ is
2-connected with girth at least~4, but contracting any bond of~$G$ leaves a
graph which is not 2-connected.

This example inspires the following.

\begin{conjecture}
Let~$G$ be a 2-connected graph with girth at least~4 and having no minor
isomorphic with~$K_5$. Then~$G$ contains a bond~$B$ such that $G\contr B$
is 2-connected.\label{con-us}
\end{conjecture}

\noindent
More generally, we ask the following.

\begin{question}
What is the largest minor-closed class of matroids such that every
connected matroid $M$ in this class having cogirth at least~4 has a circuit
$C$ such that $M\sm C$ is connected\,?\label{qu-minmat}
\end{question}

\noindent
There is a construction similar to the one preceding
Conjecture~\ref{con-us} which involves the dual Fano~$F^*_7$ (\,this
time~$B$ is a cocircuit of size~4 and we perform a series and parallel
extension on the elements of $F^*_7-B$\,). Also, the uniform
matroid~$U_{2,5}$ has no removable circuit. This suggests that $M^*(K_5)$,
$F^*_7$,~$U_{2,5}$ and Petersen's graph should be excluded minors for
Question~\ref{qu-minmat}. This list appears to be related to the list of
excluded minors for binary matroids having the ``circuit cover property''
as given in~\litref{fugod}.

The ``dual'' problems, obtained by replacing ``circuit'' with ``cocircuit''
in Problems~\ref{qu-mat} and~\ref{qu-minmat}, appear to have a completely
different quality. For example, P.~Seymour
(\,see~\litrefplus{oxl1}{Lemma~6}\,) has shown that a connected binary
matroid~$M$ of girth and cogirth at least~3 has a cocircuit~$B$ such that
$M\sm B$ is connected.

\newpage

\section*{References}

\begin{list}{{[\arabic{lit}]}}{\usecounter{lit}%
	\setlength{\leftmargin}{0.75cm}%
	\setlength{\itemsep}{\smallskipamount}%
	\setlength{\parsep}{\parskip}%
	\setlength{\topsep}{\smallskipamount}}
\item
{\sc B. Alspach, L. Goddyn, and C.-Q. Zhang,}
Graphs with the circuit cover property,
{\sl Trans.\ Amer.\ Math.\ Soc.\/}~{\bf344}
(1994) 131--154.\label{alsgodzha}

\item
{\sc H. Fleischner,}
Some blood, sweat, but no tears in Eulerian graph theory,
{\sl Congressus Numerantium\/}~{\bf63}
(1988) 8--48.\label{fle}

\item
{\sc H. Fleischner and B. Jackson,}
Removable cycles in planar graphs,
{\sl J.~London Math.\ Soc.~(2)\/}~{\bf31}
(1985) 193--199.\label{flejac}

\item
{\sc X.~Fu and L.~A.~Goddyn,}
Matroids with the circuit cover property,
Submitted to
{\sl European J.~Combin.\/}\label{fugod}

\item
{\sc L.~A.~Goddyn,}
Cycle double covers--current status and new approaches,
Contributed lecture, Cycle Double Cover Conjecture Workshop, IINFORM,
Vienna, January 1991.\label{godlec}

\item
{\sc A.M. Hobbs,}
Personal communication (1995).\label{hob}

\item
{\sc B. Jackson,}
Removable cycles in 2-connected graphs of minimum degree at least four,
{\sl J.~London Math.\ Soc.~(2)\/}~{\bf21}
(1980) 385--392.\label{jac}

\item
{\sc W. Mader,}
Kreuzungsfreie $a,b$-Wege in endlichen Graphen,
{\sl Abh.\ Math.\ Sem.\ Univ.\ Hamburg\/}~{\bf42}
(1974) 187--204.\label{mad}

\item
{\sc J.G. Oxley,}
Cocircuit coverings and packings for binary matroids,
{\sl Math.\ Proc.\ Camb.\ Phil.\ Soc.}~{\bf83}
(1978) 347--351.\label{oxl1}

\item
{\sc J.G. Oxley,}
``Matroid theory'',
Oxford University Press, Oxford (1992).\label{oxl}

\item
{\sc N. Robertson,}
Letter to A.M.~Hobbs. Dated August~25, 1975.\label{rob}

\item
{\sc P. Seymour and N. Robertson,}
Graph minors. XIII\,. The disjoint paths problem,
{\sl J.~Combin.\ Theory Ser.~B\/}~{\bf63}
(1995) 65--110.\label{seyrob}

\item
{\sc C. Thomassen and B. Toft,}
Non-separating induced cycles in graphs,
{\sl J.~Combin.\ Theory Ser.~B\/}~{\bf31}
(1981) 199--224.\label{thotof}

\end{list}
\end{document}

%%%%%%%%%%     End of LaTeX - file     %%%%%%%%%%