% Nov 19942
%

\documentstyle[art10,amssymbols]{article}

\setlength{\textwidth}{6.4in}
\setlength{\textheight}{8.7in}
\setlength{\oddsidemargin}{0.0 in}
\setlength{\evensidemargin}{0.0 in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\flushbottom

%
% Uncomment the following to put the number first in theorem environments
% Modify the font etc of #2 and #1 as desired.
%
\makeatletter
\def\@begintheorem#1#2{\trivlist \item[\hskip \labelsep{\sc\bf #2\ #1}]\it}
\def\@opargbegintheorem#1#2#3{\trivlist
      \item[\hskip \labelsep{\sc\bf #2\ #1\ (#3)}]\it}
\makeatother

% Comment out the following for hardcopy printing
%\setlength{\textheight}{7.9in}

\renewcommand{\baselinestretch}{1.38}\small\normalsize

\input{psfig}

\newcommand{\ZZ}{{\Bbb Z}}%
\newcommand{\QQ}{{\Bbb Q}}%
\newcommand{\CC}{{\cal C}}%
\newcommand{\HH}{{\cal H}}%
\newcommand{\se}{{\subseteq}}%
\newcommand{\bs}{{\backslash}}%
\newcommand{\case}[2]{{\left\{\begin{array}{ll} #1\\#2 \end{array}\right.}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\es}{\emptyset}
\newcommand{\lfig}[3]{\begin{figure}[htb]\par\centerline{ \
     \psfig{silent=,file=#1}}\caption{#2}\label{#3}\par\end{figure}}%

\begin{document}

\newcommand{\sd}{\mbox{$\bigtriangleup$}}%
%\let\sd\bigtriangleup
\renewcommand{\sl}{{\mbox{\rm sl}}}%
\renewcommand{\L}{{\bf L}}%

\newcommand{\neccond}
	{\ref{nonneg int}, \ref{eulerian} and \ref{balanced}}

\newtheorem{theorem}             {Theorem}[section]%
\newtheorem{lemma}      [theorem]{Lemma}           %
\newtheorem{proposition}[theorem]{Proposition}     %
\newtheorem{corollary}  [theorem]{Corollary}       %
\newtheorem{numbered}   [theorem]{\hspace{3em}}    %
\newtheorem{remark}     [theorem]{Remark}          %
\newtheorem{problem}    [theorem]{Problem}         %

\newenvironment{proof}{\noindent{\sc Proof.}}{\hspace*{\fill}\raisebox{-.2ex}{$\Box$}\vspace{2ex}\par}
%\newcommand{\noproof}{\vspace{-\baselineskip}\hspace*{\fill}\raisebox{1.8ex}{$\Box$}\vspace{2ex}\par}%
\newcommand{\noproof}{\vspace{-\baselineskip}\vspace{-1.3ex}\hspace*{\fill}{$\Box$}\vspace{2ex}\par}%
 



\title{Matroids with the Circuit Cover Property}

\author{
Xudong Fu\\
{\normalsize Department of Computer Science}\\
{\normalsize University of Toronto}\\
{\normalsize Toronto, ON}\\
{\normalsize \tt fu@theory.utoronto.ca}
\and
Luis A. Goddyn\thanks{Support from the National Sciences and
Engineering Research Council is gratefully acknowledged.} \\
{\normalsize Department of Mathematics and Statistics}\\
{\normalsize Simon Fraser University}\\
{\normalsize Burnaby, BC}\\
{\normalsize \tt goddyn@math.sfu.ca}
}
\date{March 23, 1995}

%\begin{document}

\maketitle

% \newpage
% 
% {\bf Proposed running head:} Circuit Cover Property.
% 
% \vspace{0.5 in}
% {\bf All correspondence and proofs should be sent
% to the second author:}
% \begin{center}
% Luis A. Goddyn \\
% {\normalsize Department of Mathematics and Statistics}\\
% {\normalsize Simon Fraser University, Burnaby, BC}\\
% {\normalsize CANADA, V5A 1S6}\\
% {\normalsize \tt goddyn@math.sfu.ca}
% \end{center}
% 
% 
% {\bf Keywords:}  matroids, circuit covers, cycle covers,
% Hilbert base, sums of circuits, bond covers, cut covers
% 
% {\bf AMS Classifications:}  05B35, ( 05C38, 05C70, 90C10 )
% 
% This article is available as a \LaTeX\ file.


\begin{abstract}
We verify a conjecture of P. Seymour
({\it Europ. J. Combinatorics\/} {\bf 2}, p.\ 289)
regarding circuits of a binary matroid.
A {\it circuit cover\/} of a integer-weighted matroid $(M,p)$ is a
list of circuits of $M$ such that each element $e$ is in exactly $p(e)$
circuits from the list.
We characterize those binary matroids for which two obvious necessary
conditions for a weighting $(M,p)$ to have a circuit cover are also 
sufficient.
\end{abstract}

\vspace{1in}
{\bf Keywords:}  matroids, circuit covers, cycle covers,
Hilbert base, sums of circuits, bond covers, cut covers
 
\vspace{3ex}
{\bf AMS Classifications:}  05B35, ( 05C38, 05C70, 90C10 )

\newpage

\section{Introduction}
In this paper, we verify a conjecture of P. Seymour
\cite[(16.5)]{Sey2} which regards
covering the elements of a binary matroid with circuits. 
We give a forbidden-minor characterization
of those matroids which have a certain
``Circuit Cover Property''.
The special case regarding graphic matroids,
solved in \cite{Als}, has had a number of implications
for problems such as the Cycle Double Cover Conjecture,
the Chinese Postman Problem, and Eulerian Decompositions
%
%FIX
%
\cite{FanZha,GHM,Jac,Zha4,Zha1,Zha2,Zha3}.
%
%
%
We extend this result to the class of 
binary matroids by applying some fairly standard matroid
decomposition techniques.
This strategy involves
verifying the conjecture for certain small matroids,
and demonstrating that the relevant properties
are preserved under matroid sums.
The most involved single step (Lemma \ref{V8* CCP})
requires checking that the bonds of
a particular graph of order eight satisfy the conjecture.
We assume familiarity with basic matroid theory such as
%in \cite{Oxl,Wel}.
in \cite{Oxl}.

Let $M$ be a binary matroid on ground set
$E= E(M)$ and let $p : E \rightarrow \ZZ$.
A {\it circuit cover\/} of the weighed matroid $(M,p)$ is a list of
circuits of $M$ such that each element $e$ is contained in exactly
$p(e)$ circuits in the list.
If $(M,p)$ has a circuit cover, then
the following three {\it admissibility conditions\/}
must hold for any $e \in E$ and any cocircuit $B$.

\begin{numbered}\label{nonneg int}
\vspace{-0.05in}
%The weight function $p$ is nonnegative integer valued.
$p(e) \in \ZZ_+$
\end{numbered}
\begin{numbered}\label{eulerian}
\vspace{-0.1in}
%The total weight $p(B)$ of any cocircuit $B$ is even.
$p(B) \equiv 0 \! \pmod 2$
\end{numbered}
\begin{numbered}\label{balanced}
\vspace{-0.1in}
%No element has more than half the total weight of any
%cocircuit containing it.  That is,
%$p(e) \le p(B-e)$ for any cocircuit $B$ and any element $e \in B$.
If $e \in B$, then $p(e) \le p(B-e)$.
\end{numbered}
%
(Here, $\ZZ_+$ denotes the non-negative integers.
For $S \se E$ we write $p(S)$ for $\sum_{e \in S} p(e)$,
and $S-e$ for $S-\{e\}$.)
The necessity of these conditions follows from
the fact that, in a binary matroid,
any circuit meets each cocircuit 
in an even number of elements.
We say that $(M,p)$ is {\it eulerian\/} if it satisfies \ref{eulerian}
for all cocircuits $B$,
$(M,p)$ is {\it balanced\/} if it satisfies \ref{balanced}
for all pairs $(B,e)$,
and $(M,p)$ is {\it admissible\/} if it satisfies
\neccond\ for all pairs $(B,e)$.
A binary matroid $M$ has the {\it circuit cover property\/}
if $(M,p)$ has a circuit cover for every
admissible weight function $p$.

\begin{theorem}[Main Theorem] \label{main thm}
Let $M$ be a binary matroid.  Then $M$ has the circuit cover property if and 
only if $M$ has no minor isomorphic to any of
$F_7^*$, $R_{10}$, $M^*(K_5)$ or
$M(P_{10})$.
\end{theorem}

We describe here these matroids and some terminology.
%using notation as in \cite{Sey2}. 
If $M$ is a matroid then $M^*$ denotes its dual. 
For any graph $G=(V,E)$, $M(G)$ denotes the matroid on
$E(G)$ whose circuits are the edge sets of
{\it polygons\/} (simple closed walks) in $G$. 
The dual matroid $M^*(G)$ has as circuits the edge sets of
{\it bonds\/} (minimal edge cuts) in $G$. 
Matroids of the form $M(G)$ ($M^*(G)$) for some graph $G$ are
said to be {\it graphic\/} ({\it cographic\/}).
%A matroid which is graphic and cographic is said to be {\it planar\/}.
The complete graph on $n$ vertices is denoted $K_n$,
complete bipartite graphs are denoted with $K_{s,t}$,
and Petersen's graph is denoted $P_{10}$. 
The {\it Wagner graph\/} $V_8$
(sometimes called the {\it M\"oebius ladder\/} of order eight)
is obtained from the polygon $v_0 v_1 \ldots v_7 v_0$
by adding four new edges of the form $v_i v_{i+4}$.
The {\it Fano\/} matroid $F_7$ is the binary matroid represented over
GF(2) by the seven non-zero binary 3-tuples. 
Thus the circuits of $F_7^*$ are precisely the $4$-arcs
of the projective plane PG(2,2).
We denote by $R_{10}$ the unique 10-element regular matroid which is
neither graphic nor cographic (see \cite{Sey2}).  This matroid is
conveniently represented by the edges of $K_5$, where $S \se E(K_5)$
is a circuit of $R_{10}$ if and only if $S$ induces in $K_5$ either
a polygon of length four or the complement of a polygon of length four.


As graphic matroids have no minors isomorphic to $F_7^*$, $R_{10}$ or
$M^*(K_5)$, the main theorem extends (and relies on)
the following result which was proved in \cite{Als}.

\begin{corollary}\label{AGZ1}
A graphic matroid $M(G)$
has the circuit cover property if and only if 
$G$ has no subgraph contractible to $P_{10}$.
\end{corollary}
\noproof

A circuit cover of a weighted cographic matroid $(M^*(G),p)$
corresponds to a covering of $E(G)$ with bonds.
Thus a graph $G$ has the {\it bond cover property\/} if $(G,p)$
has a bond cover for every $p: E(G) \rightarrow \ZZ_+$ such that
(the edge set of)
every polygon has even total weight and no edge has more
than half the total weight of any polygon containing it.
As none of $F_7^*$, $R_{10}$ and $M(P_{10})$ is cographic,
Theorem \ref{main thm} implies the following.

\begin{corollary}\label{bond cover prop}
A graph has the bond cover property if and only if it has
no subgraph contractible to $K_5$.
\end{corollary}
\vspace{\baselineskip}
\noproof


\section{Bad Minors}

Let $M$ be a matroid.
For $S \se E(M)$, the $(0,1)$-characteristic
vector in $\QQ^{E(M)}$ corresponding to $S$
is denoted with $\chi^S$.
A weighted matroid $(M,p)$ is {\it circuit minimal\/} if
$(M,p)$ is admissible, but
$(M,p-\chi^C)$ is not admissible for any circuit $C$ of $M$.
If $(M,p)$ is circuit minimal then $(M,p)$ has no circuit
cover, and $M$ does not have the circuit cover property.
A {\it $k$-circuit\/} is a circuit of cardinality $k$.

\begin{lemma}\label{bad minors}
None of 
$F_7^*$, $R_{10}$, $M^*(K_5)$ and $M(P_{10})$ has the
circuit cover property.
\end{lemma}

\begin{proof}
For each of these matroids we describe a circuit-minimal
weighting $p$.
%
\begin{description}
\item[$F_7^*$:]
Let $C$ be a fixed $4$-circuit of $F_7^*$.
Put $p(e) = 1$ for all $e \in C$,
and $p(e) = 2$ for the remaining $3$ elements in $F_7^*$.
%
\item[$R_{10}$:]
Let $S$ be any $3$-subset of elements
not contained in any $4$-circuit of $R_{10}$.
Put $p(e) = 3$ for all $e \in S$,
and $p(e) = 1$ for the remaining $7$ elements in $R_{10}$.
%
\item[$M^*(K_5)$:]
Let $T$ be six edges in $K_5$ which induce 
a subgraph isomorphic with $K_{2,3}$.
Put $p(e) = 1$ for all $e \in T$,
and $p(e) = 2$ for the remaining four edges in $K_5$.
%
\item[$M(P_{10})$:]
Let $F$ be the edges in a fixed $1$-factor of $P_{10}$.
Put $p(e) = 2$ for all $e \in F$,
and $p(e) = 1$ for the remaining $10$ edges in $P_{10}$.
\end{description}
%
It is routine to verify that 
all four weighted matroids are circuit minimal.
\end{proof}
%
\begin{remark}\label{cone check}\rm
There is an easy way to check that the first three of the
above four weighted matroids $(M,p)$ have no circuit cover.
In each case, we define a function $s$ on $E(M)$ via
\[
s(e)=\case{1 & \mbox{if $p(e) = 1$,}}{-1 & \mbox{otherwise.}}
\]
One easily checks that $s$ has negative inner product with
$p$ whereas $s(C)$ is non-negative for each circuit $C$ of $M$.
By Farkas' lemma
$p$ cannot be expressed as a linear combination of the vectors
$\{ \chi^C: \mbox{$C$ is a circuit in $M$}\}$
with nonnegative coefficients, whereas a circuit cover
corresponds to such a linear combination with nonnegative
integer coefficients.
This argument fails for $M(P_{10})$ since the weighting
described above is a nonnegative half-integral combination
of circuits.
\end{remark}

A {\it cycle\/} in a binary matroid $M$ is any disjoint union of
circuits in $M$. 
The cycles of $M$ form a subspace of
GF$(2)^{E(M)}$, called the {\it cycle space\/},
under the symmetric difference operator ``$\sd$''.
Clearly $(M,p)$ has a {\it cycle cover\/} if and only if it has a 
circuit cover.
The terms {\it cocycle\/} and {\it cocycle space\/}
are defined analogously.
If $(M,p)$ is a weighted matroid, then any minor  $M'$ of
$M$, induces a {\it weighted minor\/}
$(M',p\!\!\restriction_{E(M')})$,
which we often denote by $(M',p)$ where no confusion results.
As a further abuse, we may write
$e \in M$ and $p: M \rightarrow \ZZ$ instead of
$e \in E(M)$ and $p: E(M) \rightarrow \ZZ$.
We say that a cocycle $D$ is {\it balanced\/} in $(M,p)$
if $p(e) \le p(D-e)$ for all $e \in D$.

\begin{lemma}\label{closed under minors}
If a binary matroid $M$ has the circuit cover property then any
minor of $M$ also has the circuit cover property.
\end{lemma}
%
\begin{proof}
Assume $M$ has the circuit cover property and
let $f \in M$.
We show that both $M\bs f$ and $M/f$ have the
circuit cover property.
First, suppose that $(M\bs f,p)$ is admissible.
We extend the definition of $p$ to $M$ by setting
$p(f):=0$. 
Then $(M,p)$ is clearly admissible and thus
has a circuit cover $(C_i)$.
Since $p(f)=0$, $(C_i)$ is also a circuit cover of $(M\bs f)$,
so $M\bs f$ has the circuit cover property.

Now suppose that $(M/f,p)$ is admissible.
We may assume that $f$ is contained in some cocircuit of $M$,
since otherwise $f$ is a loop and $M/f = M\bs f$.
We extend $p$ to $E(M)$ by setting
$$p(f) := \min \{ p(B-f):
 B \mbox{ is a cocircuit in } M \mbox{ containing } f \}.$$
Let $B_0$ be a cocircuit in $M$ achieving this minimum.
We claim that $(M,p)$ is admissible.

Let $B$ be any cocircuit in $M$.
We may assume $f\in B$,
for otherwise $B$ is a cocircuit in $M/f$,
whence \ref{eulerian} and \ref{balanced} hold for $B$.
Since $B \sd B_0$ is a cocycle in $M$ not containing $f$,
$B \sd B_0$ is a cocycle in $M/f$,
so its total weight is even.
We have, modulo 2, that $p(B \sd B_0) \equiv p(B) + p(B_0)$,
so $p(B) \equiv p(B_0) = 2p(f) \equiv 0$.
Thus $(M,p)$ is eulerian.
%We now show that $B$ is balanced in $(M,p)$.
Let $e \in B$.
If $e \in B \cap B_0$, then we have $p(e) \le p(B_0-e) \le p(B-e)$,
by the choice of $B_0$.
If $e \in B-B_0$, then $B \sd B_0$ is a cocycle of $M/f$
containing $e$, and thus
$p(e) \le p(B \sd B_0 -e) \le 
          p(B-f) + p(B_0-f) -p(e) = p(B-f) + p(f) - p(e) = p(B-e)$.
Hence $(M,p)$ is balanced, and thus admissible.
Let $(C_i)$ be a circuit cover of $(M,p)$.  
Each $C_i - \{f\}$ is a cycle in $M/f$. 
Thus $(C_i - \{f\})$ is a cycle cover of $(M/f,p)$,
and $M/f$ has the circuit cover property.

\end{proof}

\section{Decomposition Theorems}

We derive here a decomposition theorem for the class of matroids
with which this paper is concerned.
Although we use the terminology of Truemper \cite{Tru},
it suits our purposes to define
matroid sums in terms of cycles and cocycles
(as in Seymour \cite{Sey3})
rather than the matrix operations of Truemper.
We refer the reader to Sections 8.5, 10.5 and 11.3
of \cite{Tru}, as well as to Section 12.4 of \cite{Oxl}.

Let $M_1$, $M_2$ be binary matroids whose ground sets $E_1$, $E_2$
may intersect.  We denote by $M_1 \sd M_2$ the matroid on
$E_1 \sd E_2$ whose cycles are all subsets of $E_1 \sd E_2$
of the form $C_1 \sd C_2$, where $C_i$ is a cycle in $M_i$,
$i=1,2$.
In particular, we define the following three {\it matroid sums\/}.
\be
\item
$M_1 \sd M_2$ is a {\it $1$-sum\/} of $M_1$ and $M_2$ if
$E_1 \cap E_2=\es$.
\item
$M_1 \sd M_2$ is a {\it $2$-sum\/} of $M_1$ and $M_2$ if
$E_1 \cap E_2=\{f\}$, where $f$ is neither a loop
nor a coloop of $M_1$ or $M_2$.
\item
$M_1 \sd M_2$ is a {\it Y-sum\/} of $M_1$ and $M_2$ if
$|E_1 \cap E_2| = 3$, where $Z := E_1 \cap E_2$
is a cocircuit of size $3$ in both $M_1$ and $M_2$,
and $Z$ contains no circuit of either $M_1$ or $M_2$. 
\ee

A matroid sum of $M_1$ and $M_2$ is said to be
{\it proper\/} if it contains proper minors isomorphic
with $M_1$ and $M_2$.
If $M$ and $M'$ are matroids, then an {\it $M'$ minor\/}
of $M$ is a minor of $M$ isomorphic with $M'$.
We state two classical decomposition results.
The first is due to Seymour
(see \cite[(11.3.16) and (11.3.19)]{Sey3}).
%
\begin{lemma}\label{no F7 decomp}
Every binary matroid with no $F^*_7$ minor
may be constructed recursively by means of proper
$1$-sums, $2$-sums and Y-sums,
starting from copies of
$F_7$, $R_{10}$, graphic, and cographic matroids.
\end{lemma}
\noproof
%
We note that a Y-sum can not involve a copy of either
$R_{10}$ or $F_7$ since neither matroid has a cocircuit
of cardinality three.
The second decomposition result is essentially
due to Wagner \cite{Wag}.
It is stated in dual form in \cite[(10.5.15)]{Tru}.
A matroid is {\it planar\/} if it is both graphic
and cographic.
%
\begin{lemma}\label{no K5 decomp}
Every cographic matroid with no $M^*(K_5)$ minor
may be constructed recursively by means of proper
$1$-sums, $2$-sums and Y-sums
starting from copies of $M^*(K_{3,3})$,
$M^*(V_8)$, and planar matroids.\hspace{9pt}~
\end{lemma}
\noproof
%
Seymour \cite[(6.10)]{Sey3} observes that 
$M^*(K_{3,3})$, which is a minor of $M^*(V_8)$,
may be dropped from the list of starting
minors provided we do not require the sums to be proper.
Indeed the following is easy to check.
%
\begin{proposition}\label{V8 proper}
Every proper minor of $M^*(V_8)$ is either
planar or is a Y-sum of two planar matroids.\hspace{9pt}~ 
\end{proposition}
\noproof
%
\begin{lemma}\label{CCP decomp}
Every binary matroid with no
$F_7^*$, $R_{10}$, $M^*(K_5)$ or $M(P_{10})$ minor
may be constructed recursively by means of 
$1$-sums, $2$-sums and Y-sums
starting from copies of
$F_7$, $M^*(V_8)$, and graphic matroids
containing no $M(P_{10})$ minor.
\end{lemma}
\begin{proof}
Let $M$ be a binary matroid with no minor isomorphic to $F_7^*$,
$R_{10}$, $M^*(K_5)$ or $M(P_{10})$.
We decompose $M$ via Lemma \ref{no F7 decomp},
obtaining a list $\L$ of matroids.  
Since the sums in Lemma \ref{no F7 decomp} are proper,
each matroid in $\L$ is one of following.
\begin{itemize}
\item $F_7$
\item cographic, with no $M^*(K_5)$-minor
\item graphic, with no $M(P_{10})$-minor.
\end{itemize}
We have used here that $M(P_{10})$ is not cographic and
$M^*(K_5)$ is not graphic.
We further decompose each cographic matroid in $\L$
by applying Lemma \ref{no K5 decomp}.
Finally we apply Proposition \ref{V8 proper}
to eliminate copies of $M^*(K_{3,3})$ and 
obtain our final decomposition.
As planar matroids are graphic and have no $M(P_{10})$-minor,
each matroid in the final decomposition is of the required type.
\end{proof}

\section{Preservation under sums}

We show here that the circuit cover property is preserved
by $1$-sums, $2$-sums and Y-sums. 
We note that the operation that is dual to the Y-sum,
called $\sd$-sum by Truemper \cite{Tru} and
used by Seymour \cite{Sey3,Sey2},
does not preserve the circuit cover property.
For example, $F_7$ has the circuit cover property
(Lemma \ref{F7 CCP}),
whereas any $\sd$-sum of two copies of $F_7$ has an $F^*_7$ minor.
However, the proof of Lemma \ref{sum preserve} below
has a similar flavour to (7.2) and (7.3) of \cite{Sey2}.
%
We first state an observation of Seymour
\cite[p. 319]{Sey3}.
\begin{lemma}\label{cocycles of a sum}
Let $M$ be a $1$-sum, $2$-sum or Y-sum of binary matroids
$M_1$ and $M_2$.  Then the cocycles of $M$ are precisely
the subsets of $E_1 \sd E_2$
of the form $B_1 \sd B_2$,
where $B_i$ is a cocycle of $M_i$, $i=1,2$.
\end{lemma}
\noproof
%
\begin{lemma}\label{sum preserve}
Suppose $M$ is a $1$-sum, $2$-sum or Y-sum of binary matroids
$M_1$ and $M_2$,
where both $M_1$ and $M_2$ have the circuit cover property.
Then $M$ has the circuit cover property.
\end{lemma}
%
\begin{proof}
We omit the $1$-sum case as its proof is almost trivial.
Let $M$ be a $2$-sum of $M_1$ and $M_2$
where $M_1 \cap M_2 = \{ f \}$ and where
each $M_i$ has the circuit cover property.
We proceed by constructing an admissible weighting
$p_i$ of $M_i$, $i=1,2$.
Let $i \in \{ 1,2\}$.
Since $f$ is not a loop in $M_i$,
some cocircuit in $M_i$ contains $f$.
We choose such a cocircuit $D_i$ which minimizes $p(D_i-\{ f\})$,
and let $n_i$ denote this minimum.
We
assume without loss of
generality that $n_1 \le n_2$.
For $i = 1,2$ we define $p_i : M_i \rightarrow \ZZ $ by
$$
p_i (e) = \case{n_1  & \mbox{if } e=f}
			   {p(e) & \mbox{otherwise.}}
$$
 From this definition we immediately have
\begin{equation}
p_1(e) \le p_1(D_1 - \{e \}), \mbox{ for all } e \in D_1.
\end{equation}
We now show that each $(M_i,p_i)$ is admissible.
Let $i\in \{ 1,2\}$. 
By Lemma \ref{cocycles of a sum}
each cocircuit $D$ in $M_i$ not containing $f$ is a cocycle
in $M$.  Since $(M,p)$ is admissible and since $p$ and $p_i$
coincide on $D$, $D$ is balanced and eulerian in $(M_i,p_i)$.  
We assume now that $D$ is a cocircuit in $M_i$ containing $f$.
By Lemma \ref{cocycles of a sum},
$D \sd D_1$ is a cocycle of $M$,
so $D \sd D_1$ is balanced and has even total weight
in $(M,p)$.
Since $p_1(D_1)$ is even and
$p(D \sd D_1)\equiv p_i(D) + p_1(D_1) \!\!\!\pmod 2$,
it follows that $p_i(D)$ is even.
Let $e \in D$. 
If $e \in D \cap D_1$, then by (1) and the choice of $D_1$
$$p_i(e) = p_1(e) \le p_1(D_1 - \{ e\}) \le p_i(D-\{e\}).$$
If $e \in D - D_1$, then $e \in D_1 \sd D$ and
$$p_i(e) = p(e) \le p(D\sd D_1 - \{ e\}) \le 
		   p(D-\{f\})+p(D_1 -\{f\})-p(e) =
		   p_i(D-\{ f\}) + p_i(f)-p_i(e) = p_i(D-\{e \}).$$
Thus $(M_i,p_i)$ is admissible and, by hypothesis,
has a circuit cover $\L_i$, $i=1,2$.
We form a cycle cover of $(M,p)$ by ``pairing off''
the circuits in $\L_1$ which contain $f$ with those in $\L_2$
which contain $f$.
More precisely, we let $\L'_i$ be the sublist of $\L_i$
consisting of the $n_1$ circuits which contain $f$,
$i=1,2$,
and let $g:\L'_1 \rightarrow \L'_2$ be any bijection.
The list
$(\L_1 - \L'_1) \cup (\L_2 - \L'_2)\cup ( C \sd g(C) : C \in \L'_1)$
is a cycle cover of $(M,p)$.  Thus $M$ has the circuit
cover property.


We assume now that $M$ is a Y-sum of $M_1$ and $M_2$
where each $M_i$ has the circuit cover property.
Let $M_1 \cap M_2 = Z = \{ e_1,e_2,e_3 \}$
where $Z$ is a cocircuit in both $M_1$ and $M_2$.
Let $p$ be an admissible weighting of $M$.
Let $i \in \{1,2\}$ and $j \in \{ 1,2,3 \}$.
Since $Z$ contains no circuit of $M_i$,
$e_j$ is not a loop in $M_i/(Z-\{e_j\})$ and thus
there is a cocircuit $D$ in $M_i$ such that
$D \cap Z = \{ e_j \}$.
Let $d_{ij}$ be the minimum of $p(D-e_j)$ over all such
cocircuits $D$, and let $D_{ij}$ be a cocircuit attaining
this minimum.
For $j=1,2,3$, we define
$n_j := \min\{d_{1j}, d_{2j}\}$,
and let $D_j$ be a cocircuit in $\{D_{1j},D_{2j}\}$ with
$p(D_j -p) = n_j$.
Let $n := n_1+n_2+n_3$.
For $i = 1,2$ we define the weighting 
$p_i : M_i \rightarrow \ZZ $ by
$$
p_i (e) = \case{\min\{ n_j, n-n_j\} &
                 \mbox{if } e=e_j,\mbox{ for some }j\in\{1,2,3\}}
		 {p(e)              & \mbox{otherwise.}}
$$
We now show each $(M_i,p_i)$ is admissible.
Let $i \in \{ 1,2 \}$.
Let $D$ be any cocircuit of $M_i$.
We have four cases depending on $|Z \cap D|$.

Case $|Z \cap D|=3$:
Here $D=Z$.
By construction of $p_i$,
$Z$ is balanced in $(M_i,p_i)$.
Its weight, $p_i(Z)$, equals either $n$ or $2n - 2n_j$
for some $j \in \{1,2,3\}$, and thus $Z$ is eulerian provided
that $n$ is even.
By Lemma \ref{cocycles of a sum},
$D_1 \sd D_2 \sd D_3 \sd Z$ is a cocycle of $M$,
and so
$ n=n_1+n_2+n_3=p(D_1) +p(D_2) +p(D_3) -p(Z) \equiv
p(D_1 \sd D_2 \sd D_3 \sd Z) \equiv 0 \!\!\!\pmod 2$,
as required.

Case $|Z \cap D|=0$:
Here $Z$ is a cocycle of $M$, and is thus balanced and
eulerian in $(M_i,p_i)$.

Case $|Z \cap D|=1$:
By symmetry
we may assume $Z \cap D = \{ e_1 \}$.
If $p_i(e_1) = n_1$, then by the same argument as in the
$2$-sum case, $D$ is eulerian and balanced in $(M_i,p_i)$.
We assume that $p_i(e_1) = n_2 + n_3<n_1$, $p_i(e_2)=n_2$,
and $p_i(e_3) = n_3$.
We claim that neither $M_1$ nor $M_2$ contains both
$D_2$ and $D_3$. 
Otherwise, $D_2 \sd D_3 \sd D$ would be a cocycle in
$M_1$ or $M_2$ such that
$(D_2 \sd D_3 \sd D) \cap Z = \{e_1\}$.
This cocycle contains a cocircuit $D'_1$ with
$D'_1 \cap Z = \{e_1\}$.  
For $k=1,2$ we have
$$
p_k(D'_1 - \{e_1\}) \le p_k(D_2 - \{e_2\}) + p_k(D_3 - \{e_3\})
= n_2+n_3 < n_1
$$
contradicting the minimality of $n_1$ and proving our claim.
Hence exactly one of $D_2,D_3$, say $D_2$, belongs to $M_i$.
Now $D'_3 := D_2 \sd D \sd Z$ is a cocycle of $M_i$ with
$D'_3 \cap Z = \{e_3\}$.
Since $p_i(D'_3)$, $p_i(D_2)$ and $p_i(Z)$ are even, and
$p_i(D'_3) \equiv p_i(D_2)+p_i(D)+p_i(Z) \!\!\!\pmod 2$,
$p_i(D)$ is even.
We now show $D$ is balanced in $(M_i,p_i)$.
Let $e \in D$. If $e \in D \cap D_2$, then 
\begin{eqnarray*}
 p_i(e) & \le & p_i(D_2-\{e\})=p_i(D_2-\{e_2\})+p(e_2)-p_i(e) \\
  & = & n_2+n_2-p_i(e) \le 2(n_2+n_3) - p_i(e) = 2p_i(e_1)-p_i(e) \\
  & \le & p_i(D-\{e_1\})+p_i(e_1)-p_i(e)=p_i(D-\{e\}).
\end{eqnarray*}
If $e \in D - D_2$, then $e \in D'_3 = D_2 \sd D \sd Z$.
Since $D'_3 \cap Z = \{e_3\}$ and $p(e_3) = n_3$,
$D'_3$ is balanced and eulerian in $(M_i,p_i)$
as in the second sentence of this case.  Therefore
\begin{eqnarray*}
 p_i(e) & \le & p_i(D_2 \sd D \sd Z -\{e\})
		\le p_i(D-\{e_1\})+p(D_2 -\{e_2\})+p_i(e_3)-p_i(e) \\
  & = &  p_i(D-\{e_1\})+ p_i(e_1)- p_i(e) = p_i(D-\{e\}).
\end{eqnarray*}

Case $|Z \cap D|=2$:
We may assume that $D \cap Z = \{ e_1,e_2\}$ so that 
$D \sd Z$ is a cocycle of $M_i$ satisfying
$(D \sd Z) \cap Z = \{e_3\}$.
As in the previous case,
$p_i(D \sd Z)$ is even.
Since $p_i(Z)$ is even,
$p_i(D)$ is even. 
We now show that $D$ is balanced
in $(M_i,p_i)$
Let $e \in D$.  If $e \in D-\{e_1,e_2\}$, then $e \in D \sd Z$.
By the previous case
$D \sd Z$ is balanced in $(M_i,p_i)$ so
$$
p_i(e) \le p_i(D \sd Z -\{e\})
= p_i(D)- p_i(e_1)- p_i(e_2)+ p_i(e_3)-p_i(e) \le p_i(D-\{e\}).
$$
Lastly, we have
$$
p_i(e_1) \le p_i(e_2)+p_i(e_3)
\le p_i(e_2)- p_i(D-\{e_1,e_2\})= p_i(D-\{e_1\})
$$
and similarly $p_i(e_2) \le p_i(D-\{e_2\})$.

We have shown $(M_i,p_i)$ is admissible, $i=1,2$.
By hypothesis
$(M_i,p_i)$ has a circuit cover $\L_i$, $i=1,2$.
Each circuit in $\L_i$ which intersects $Z$ in $0$ or $2$
elements.
For $j=1,2,3$ we denote by $\L^j_i$ those circuits in 
$\L_i$ containing $Z-\{e_j\}$.
For any partition $\{j\} \cup \{k,\ell\}$ of $\{1,2,3\}$ we have
$|\L^k_1|+|\L^\ell _1| = p_1(e_j) = p_2(e_j) =|\L^k_2|+|\L^\ell _2|$,
and thus
$|\L^j_1| = |\L^j_2| = (p_1(e_k)+p_1(e_\ell)-p_1(e_j))/2$.
Similarly to the $2$-sum case, the circuits in
in $\L^j_1$ may be ``paired off''
with those in $\L^j_2$, $j=1,2,3$
in an obvious way to yield a circuit cover of
$(M,p)$.
Thus $(M,p)$ has the circuit cover property.
\end{proof}

\section{Good Matroids}\label{good ones}

It remains to show that each of the building blocks of
the decomposition of Lemma \ref{CCP decomp} has 
the circuit cover property.  
The first is due to Alspach, Goddyn and Zhang \cite{Als}.

\begin{lemma}\label{AGZ}
Graphic matroids containing no $M(P_{10})$ minor have the
circuit cover property.
\end{lemma}

We define a partial order on the set of weightings of
a matroid $M$.
For $p,q: M \rightarrow \ZZ$ we write
$p \preceq q$ if $p(e) \le q(e)$ for each $e \in M$.
A weighting $(M,p)$ is {\it positive\/}
if $p(e) \ge 1$ for all $e \in M$.
Let $B$ be a cocircuit in $M$ and let $e \in B$.
We define the {\it slack\/} of $(B,e)$ in $(M,p)$ by
$$
\sl(B,e) = \sl_p (B,e) := p(B-e) -p(e).
$$
Thus if $(M,p)$ is admissible, then $\sl(B,e)$ is a
nonnegative even integer.
The following is convenient for showing that a matroid
has the circuit cover property.
%
\begin{lemma}\label{sufficient for CCP}
Let $M$ be a matroid such that 
$M\bs e$ has the circuit cover property for all $e \in M$.
Suppose further that,
for any admissible positive weighting $(M,p)$,
there exists a circuit $C$ such that
for any cocircuit $B$ and $e \in B$,
%
\begin{equation}
\sl(B,e) \ge \case{ |C \cap B|   & \mbox{if $e \not\in C$}}
                  { |C \cap B|-2 & \mbox{if $e     \in C$.}}
\end{equation}
%
%$(M,p-\chi^C)$ is balanced. 
Then $M$ has the circuit cover property.
\end{lemma}
%
\begin{proof}
Suppose $M$ satisfies the hypothesis, but does not have the
circuit cover property.
Let $(M,p)$ be a $\preceq$-minimal admissible weighting
which has no circuit cover.
%and which is $\preceq$-minimal with respect to this property.
If $p(e) = 0$ for some $e \in M$, then the restriction
%of $p$ to $E(M)-\{e\}$ is an admissible weighting of $M\bs e$. 
$(M\bs e,p)$ is admissible.
By hypothesis
$(M\bs e,p)$ has a circuit cover. 
This circuit cover is also a circuit cover
of $(M,p)$, a contradiction.
%Thus we may assume $p$ is positive,
Thus $p$ is positive,
whence there exists a circuit $C$
satisfying (2) for every cocircuit $B$ and $e \in B$.
Let $p' := p - \chi^C$.
Since $(M,p)$ is eulerian and positive,
$(M,p')$ is eulerian and nonnegative valued.
For any $S \se E(M)$ we have
$p'(S) = p(S) - |C \cap S|$,
so (2) is equivalent to the statement
$p'(e) \le p'(B-e)$.
Thus $(M,p')$ is admissible and, by
minimality of $p$,
$(M,p')$ has a circuit cover.
Adjoining $C$ to this circuit cover yields
a circuit cover of $(M,p)$, a contradiction.
Thus $M$ has the circuit cover property.
\end{proof}

\begin{lemma}\label{F7 CCP}
The matroid $F_7$ has the circuit cover property.
\end{lemma}
\begin{proof}
We check that $F_7$ satisfies the hypothesis of
Lemma \ref{sufficient for CCP}.
For any $e \in F_7$, $F_7 \bs e \cong M(K_4)$
which has the circuit cover property by Lemma \ref{AGZ}.
Let $(F_7,p)$ be admissible and positive.
Let $a,b \in F_7$ be such that $p(e) \le p(b) \le p(a)$ for
all $e \in E-\{a,b\}$, and let $C$ be the unique circuit
of cardinality 3 containing $a$ and $b$.
Let $B$ be any cocircuit of $F_7$ and let $e \in B$. 
As $|C \cap B|$ is even and $|C|=3$,
$C \cap B$ contains either 0 or 2 elements.
Since $\sl(B,e) \ge 0$, (2) holds unless
$e \not\in C$ and
$|C \cap (B-e)| = 2$.
In this case $e$ is different from $a$ and $b$.
Every cocircuit of $F_7$ has cardinality $4$ so
$B-e$ contains $3$ elements of positive weight.
Since $|C-B|=1$, one of these $3$ elements
is either $a$ or $b$.
We have
$ \sl(B,e) = p(B-e)-p(e) \ge (p(b) + 2) - p(e) \ge  2 $
and (2) holds.
Thus $F_7$ has the circuit cover property.
\end{proof}

The following lemma completes the proof of the main theorem.
It is the most involved single step in its proof.  
The details are supplied in the next section.
%
\begin{lemma}\label{V8* CCP}
The matroid $M^*(V_{8})$
has the circuit cover property.
\end{lemma}

\section{Bond covers of $V_8$}

To minimize confusion
we use a separate terminology for graphs. 
A {\it cycle\/} in a graph $G$ is the edge set of a
simple closed walk in $G$.
An {\it edge cut\/} is the set $\delta(X)$
of edges with exactly one endpoint in $X$
for some $X \se V(G)$.
A {\it bond\/} is an minimal nonempty edge cut.
We say that $G$ has the {\it bond cover property\/}
if $M^*(G)$ has the circuit cover property.
The graph $V_8$ is obtained from the polygon
$v_0 e_0 v_1 e_1 \cdots e_6 v_7 e_7$ by adding
the edges $e_{04}$, $e_{15}$, $e_{26}$, $e_{37}$,
where each $e_{ij}$ has endpoints $v_i$ and $v_j$.
Each $e_i$ is called a {\it rim edge\/} whereas each
$e_{ij}$ is called a {\it spoke\/}.
The automorphism group of $V_8$ is the dihedral
group of order $16$.
Our aim is to show that $V_8$ has the bond cover
property.

If $G$ is a plane graph then $G$ has the bond cover property if
and only if the polygon matroid of its plane dual $G^*$ has the
the circuit cover property.  As planar graphs do not have
$P_{10}$ as a minor, Lemma \ref{closed under minors}
implies the following.
\begin{lemma}\label{planar}
Every planar graph has the bond cover property.
\end{lemma}
\noproof
Applying Lemmas \ref{V8 proper} and \ref{sum preserve},
we have the following.
%
\begin{lemma}\label{proper V8}
All proper minors of $V_8$ have the bond cover property.
\end{lemma}
\noproof
%
\vspace*{-1.9ex}
As in Section \ref{good ones}, we define
$$
\sl(C,e) := p(C-e) -p(e)
$$
for any cycle $C$ and $e \in C$.
We say that an edge weighted graph $(G,p)$ is
{\it bond admissible\/} if $(M^*(G),p)$ is admissible.
Thus $p: E(G) \rightarrow \ZZ_+$ is bond admissible if
for each cycle $C$ and $e \in C$,
$\sl(C,e)$ is a non-negative even integer.
A cycle $C$ in $(G,p)$ is
{\it balanced\/} if $\sl(C,e) \ge 0$ for all $e \in C$,
and is {\it tight\/} if $\sl(C,e) = 0$ for some $e \in C$.
If $\sl(C,e) = 0$, then
$e$ is called a {\it leader\/} of $C$.
If $G$ is simple and $p$ is positive and bond admissible,
then each tight cycle in $(G,p)$ has a unique leader.
A {\it chord\/} of a cycle $C$ is an edge in $E(G) - C$
such that both its endpoints are incident with an edge in $C$.
We recall that the symmetric difference of two cycles
in $G$ is an edge-disjoint union of cycles in $G$.
%
\begin{lemma}\label{slack sum}
Let $p$ be a positive weighting of a graph $G$.
Let $C, C'$ be cycles and $e,f$ be edges in $G$
such that $e \in C - C'$ and $f \in C \cap C'$.
Let $D$ be a cycle in $C \sd C'$ containing $e$.
Then $\sl(D,e) \le \sl(C,e) + \sl(C',f)$ with
equality if and only if $D = C \sd C'$ and 
$f$ is a chord of $D$.
\end{lemma}
\begin{proof}
Let $a = \sl(C,e)$ and $b = \sl(C',f)$.
We have 
$p(C \sd C' -e) = p(C-e-f) + p(C'-f) -2p(C\cap C' -f)$
and so
\begin{eqnarray*}
p(e) & =   & p(C-e) -a  =   p(C-e-f) -a + p(f) \\
     & =   & p(C-e-f) -a + p(C'-f)-b \\
     & =   & p(C \sd C' -e)+ 2p(C \cap C'-f) -a -b \\
     & \ge & p(D -e) -a -b.
\end{eqnarray*}
Since $p$ is positive, equality holds if and only if
$D = C \sd C'$, and $C \cap C' = \{f\}$.
\end{proof}
%
{\samepage
\begin{corollary}\label{chord}
Let $C$ be a cycle in $G$, $e \in C$ and let $f$ be a chord of $C$.
Let $C_e$ be the cycle in $C \cup \{ f\}$ containing both
$e$ and $f$, and let $C_f$ be the
cycle in $C \cup \{f\} - \{e\}$.
Then for any edge-weighting $p$ we have
$\sl(C,e) = \sl(C_e,e) + \sl(C_f,f)$.\hspace{9pt}~ 
\end{corollary}
\noproof

}

For any edge weighting $(V_8,p)$ we define the
{\it set of leaders\/}
$$
L = L(p) := \{ e \in E(V_8): e \mbox{ is the leader of some tight
cycle in }  (V_8,p)\}.
$$
%
\begin{lemma}\label{two leaders}
Let $(V_8,p)$ be positive and bond admissible. 
If $|C \cap L| \ge 2 $ for some tight cycle $C$,
then $(V_8,p)$ has a bond cover.
\end{lemma}
%
\begin{proof}
Let $e,f \in C \cap L$ and assume that $e$ is the
(unique) leader of $C$.  Then $f$ is the leader of 
some tight cycle $C'$ different from $C$.  
Since $p(f) < p(e)$, we have $e \not\in C'$.
Let $D$ be the cycle in $C \sd C'$ containing $e$.
As $D$ is a balanced in $(V_8,p)$, Lemma \ref{slack sum} gives
$ 0 \le \sl(D,e) \le \sl(C,e) + \sl (C',f) = 0$
so $D = C \sd C'$ is a tight cycle and $f$ is a chord of $D$.

Let $x,y$ be the endpoints of $f$.
Since every cycle in $V_8 \bs f$ is a cycle in $V_8$,
$(V_8 \bs f , p )$ is bond admissible.
By Lemma \ref{proper V8},
$(V_8 \bs f , p )$ has a bond cover
$\L'$.  
Let $\L''$ be the sublist consisting of those bonds
$\delta(X)$ in $\L'$ for which $ |X \cap \{x,y\}|=1$.
Let $\L$ be the list of bonds in $V_8$ obtained from
$\L'$ by adding the edge $f = xy$ to those bonds in $\L''$.
Since $D$ is tight, each bond in $\L'$ which contains
$e$ contains exactly one other edge in $D$, so
the number of bonds in $\L''$ is exactly
$p(C'-f) = p(f)$.  Thus $\L$ is a bond cover of $(V_8,p)$.
\end{proof}

We say that a bond $B$ in $(V_8,p)$ is {\it removable\/} if
$(V_8,p - \chi ^ B)$ is bond admissible.
In particular, any bond in a bond cover of $(V_8,p)$
is removable.
As in Lemma \ref{sufficient for CCP}, if $p$ is positive,
then a bond $B$ is removable 
if and only if for any cycle $C$ and $e \in C$,
$$
\sl(C,e) \ge \case{ |B \cap C|   & \mbox{if $e \not\in B$}}
                    { |B \cap C|-2 & \mbox{if $e     \in B$.}}
$$
We derive a sufficient condition,
depending only on the leaders $L(p)$,
for a bond to be removable in $(V_8,p)$.
%Although the third condition below is slightly daunting, it
%will rarely need to be checked.
A {\it $k$-cycle\/} is a cycle of cardinality $k$.
%
\begin{lemma}\label{sufficient for removable}
Let $(V_8,p)$ be positive and bond admissible.  Then a bond $B$
is removable provided all of the following hold.
\begin{enumerate}
   \item
   $L \subseteq B$
   \item
   For every $4$-cycle $C$ contained in $B$,
   we have $|C \cap L| \ge 2$.
   %$|C \cap L| \ge 2$ for all cycles $C$ of length
   %$4$ or $5$ such that $|C \cap B|=4$ 
   \item
   For every $5$-cycle $C$ such that $|C \cap B| = 4$, 
   we have
   $|C \cap L| \ge 2$ and
   there exists $f \in C \cap L$ such that
   every chordless cycle $C'$ containing $f$ satisfies
   $|C' \cap ( C \cup L)| \ge 2$.
   %cycles $C'$ containing $f$,
   %either $|C' \cap L| \ge 2$ or $|C' \cap C| \ge 2$.
   %If $C$ is a $5$-cycle such that $C-B = \{e\}$,
   %then there exists $f \in C \cap L$ such that for all
   %cycles $C'$ containing $f$,
   %either $|C' \cap L| \ge 2$ or $|C' \cap C| \ge 2$.
\end{enumerate}
\end{lemma}
%
\begin{proof}
Suppose that $B$ is not removable,
but that {\it 1., 2., and 3.\/}\ hold.
Let $p' = p - \chi ^ B$. 
Then some cycle is unbalanced in $(V_8,p')$.
Applying Corollary \ref{chord}, there exists an unbalanced
cycle $C$ in $(V_8,p')$ which is chordless.
Since every cycle in $V_8$ having cardinality greater than five
has a chord, we have $4 \le |C| \le 5$.
Since $C$ is balanced in $(V_8,p)$ but not in $(V_8,p')$,
$|B \cap C|$ equals either $2$ or $4$.
If $|B \cap C| = 2$, then $C$ is tight in $(V_8,p)$
and $B$ does not contain the leader of $C$,
contradicting {\it 1}.
Thus we have $4 = |C \cap B| \le |C| \le 5$.
By {\it 2.} and {\it 3.}, $|C \cap L| \ge 2$.
If $C$ were tight in $(V_8,p)$,
then $(V_8,p)$ would have a removable bond
by Lemma \ref{two leaders}.
Thus $C$ is not tight in $(V_8,p)$ whereas $C$ is unbalanced
in $(V_8,p')$.
Since $|C| \le 5$ this can happen only if $|C|=5$ and,
for some $e \in C$,
$C - B = \{e\}$ and $\sl_p(C,e) = 2$.
Let $f \in C\cap L$ be the edge specified in condition {\it 3}.
Applying Corollary \ref{chord},
$f$ is a leader of some chordless tight cycle $C'$.
Since $f \in C' \cap C \cap L$, condition {\it 3}.\ implies that
either $|C' \cap C| \ge 2$ or $|C' \cap L| \ge 2$.
Applying Lemma \ref{two leaders} to $C'$,
we may assume
$|C' \cap L| = 1$ and thus $|C' \cap C| \ge 2$.
If $e \in C'$, then 
$p(f) = p(C'-f) \ge p(e) = p(C-e)-2 \ge p(f)-2$
which is absurd.
Therefore $e \in C - C'$ and $f \in C \cap C'$.
Let $D$ be the cycle in $C \sd C'$ which contains $e$.
Applying Lemma \ref {slack sum} to $(V_8,p)$, we have
$ \sl(D,e) \le \sl(C,e) + \sl(C',f) = 2+0$.
Since $|C' \cap C| \ge 2$, we do not have equality here,
whence $\sl(D,e) = 0$.
Thus $e \in L- B$, contradicting {\it 1}.
\end{proof}
%
A {\it matching\/} is a set of edges such that no
two are adjacent.
%
\begin{lemma}\label{leaders matching}
Let $(V_8,p)$ be positive and bond admissible.
If $L$ is not a matching of cardinality at least two,
then $V_8$ has a removable bond.
\end{lemma}
\begin{proof}
Let $v \in V(V_8)$.
Every cycle intersects the star-bond $\delta(v)$
in at most two edges.
Therefore if $\delta(v)$ is not removable,
then there exists a tight cycle $C$ in $(V_8,p)$
which intersects $\delta(v)$
but whose leader is not contained in $\delta(v)$.
Since $v$ is arbitrary, we have $|L| \ge 2$.
Furthermore, if $v$ is incident with at least two edges in
$L$, then one of these two edges is in $C$,
since $v$ has degree three.
Thus $|C \cap L| \ge 2$ and 
by Lemma \ref{two leaders}, $(V_8,p)$ has a bond
cover.
\end{proof}

We now complete the proof of Theorem \ref{V8* CCP}.
By Lemmas \ref{sufficient for CCP} and \ref{proper V8}
it suffices to show the existence of a removable bond in 
any positive, bond admissible weighting $(V_8,p)$.
By Lemma \ref{leaders matching}
we may assume that 
$L(p)$ is a matching of cardinality at least two.
%It suffices to display, for each such matching $L$,
%a bond $B$ which satisfies
%the three conditions
%conditions {\it 1., 2.,} and {\it 3}.\
%of Lemma \ref{sufficient for removable}.
%
%We say that two subsets $S, S' \se E(V_8)$ are
%{\it equivalent\/} if some automorphism of $V_8$ maps
%$S$ to $S'$.
For $S \se E(V_8)$ we denote by $[S]$ the orbit of $S$
under the group of automorphisms of $V_8$.
Referring to Figure \ref{fig1},
we claim that for any matching $L$ in $V_8$ with $|L| \ge 2$,
there is a bond $B$
%equivalent with either
%$B_1$, $B_2$, $B_3$ or $B_4$
in either $[B_1]$, $[B_2]$, $[B_3]$ or $[B_4]$
satisfying
conditions {\it 1., 2.,} and {\it 3}.\
of Lemma \ref{sufficient for removable}.
%When checking these conditions, 
We note that condition {\it 2}.\ 
is vacuously true for 
$B_1$, $B_3$ and $B_4$,
and that condition {\it 3}.\ 
is vacuously true for
$B_1$, $B_2$ and $B_3$.
%
\lfig{9531-matroids-circuit-cover.fig1.eps}{Four bonds in $V_8$}{fig1}
%

If $L$ contains no rim edges and $|L| \le 3$,
then some bond in $[B_1]$ contains $L$,
and thus satisfies {\it 1., 2.,} and {\it 3}.
If $L$ consists of all four spokes in $V_8$,
then $B_2$ satisfies the three conditions.
%Condition {\it 2}.\ needs to be checked here since $B_2$
%contains a $4$-cycle.
%
If $L$ contains exactly one rim edge
then, since $L$ is a matching,
some bond in $[B_1]$ contains $L$ and is therefore
removable.
%
If $L$ contains exactly two rim edges and these two
edges are at distance $3$ ($4$) along the rim of
$V_8$, then some bond in $[B_1]$ ($[B_2]$)
again satisfies the three conditions, and hence is removable.
If $L$ contains exactly two edges at distance $2$
along the rim of $V_8$ then, since $L$ is a matching,
$|L|=2$ and a bond in $[B_3]$
contains $L$ and thus satisfies the three conditions.
%
If $L$ contains $3$ or $4$ rim edges,
then $L$ contains no spokes since $L$ is a matching.
If $L \se B_3$, then $B_3$ is removable
%since {\it 2}.\ and {\it3}.\ are vacuous.
so we may assume that $L = \{e_0, e_2, e_5\}$.
We claim that $B_4$ is removable in this case.
In this case
condition {\it 3}.\ must be checked with
$C = \{ e_2, e_3, e_4, e_5, e_{26} \}$;
here $e_5$ serves as the required edge $f$.
%
In all cases, there is a removable bond in $V_8$,
and thus $V_8$ has the bond cover property.



\section{Remarks}

Remark \ref{cone check} provides a good reason
that none of $F_7^*$, $R_{10}$, $M^*(K_5)$
has the circuit cover property;
each of these matroids has an admissible weighting which 
does not even have a ``fractional'' circuit cover.
This suggests that the admissibility conditions,
\ref{nonneg int}, \ref{eulerian}, \ref{balanced},
should be replaced with stronger ones.
Let $\CC = \CC(M)$ denote the set of circuits in matroid $M$.
Let $\QQ_+$ denote the non-negative rational numbers.
For any matroid $M$ we define the
{\it lattice\/}, the
{\it cone\/} and the 
{\it integer cone\/} of circuits in $M$ by
\begin{eqnarray*}
\ZZ(\CC) & := & \{ \sum_{C \in \CC} \alpha_C \chi^C:
               \alpha_C \in \ZZ \mbox{ for all } C \in \CC \}
	       \\
\QQ_+(\CC) & := & \{ \sum_{C \in \CC} \alpha_C \chi^C:
                 \alpha_C \in \QQ_+ \mbox{ for all } C \in \CC \}
		 \\
\ZZ_+(\CC) & := & \{ \sum_{C \in \CC} \alpha_C \chi^C:
                 \alpha_C \in \ZZ_+ \mbox{ for all } C \in \CC \}
\end{eqnarray*}
%
Thus $(M,p)$ has a circuit cover if and only if 
$p \in \ZZ_+(\CC)$.
For any matroid,
$$
\ZZ_+(\CC) \se \QQ_+(\CC) \cap \ZZ(\CC).
$$
If equality holds here, then we say that
$\CC$ forms a {\it Hilbert base}.
Let $\HH$ denote the class of matroids whose
circuits form a Hilbert base.
The following problem is raised in \cite{God}.
%
\begin{problem}\label{Hilbert problem}
Characterize the matroids in $\HH$.
%For which matroids do the circuits form a Hilbert base?
\end{problem}
%
It is known (see \cite{God, Lov}) that for any binary matroid $M$
with no $F_7^*$ minor,
a weighting $p: M \rightarrow \ZZ$ belongs to
$\ZZ(M)$ if and only if
\ref{eulerian} holds for all cocircuits $B$ and
\ref{balanced} holds for all cocircuits $B$ with $|B| \le 2$.
%
Seymour \cite{Sey2} showed that,
for all binary matroids with no $F_7^*$, $R_{10}$ or $M^*(K_5)$ minor,
a weighting $p: M \rightarrow \QQ_+$ belongs to
$\QQ_+(M)$ if and only if
\ref{balanced} holds for all cocircuits $B$.
Thus our main theorem partially answers the above problem.
%
\begin{corollary}\label{main restatement}
Let $M$ be a binary matroid with no
$F_7^*$, $R_{10}$ or $M^*(K_5)$ minor.
%Then the circuits in $M$ form a Hilbert base if and only if
Then $M \in \HH$ if and only if
$M$ has no $M(P_{10})$ minor.
\end{corollary}
\noproof
%
If $M$ contains a $F_7^*$, $R_{10}$ or $M^*(K_5)$ minor,
then our main theorem is no longer relevant since the cone
of circuits of $M$ is strictly contained in cone of non-negative
weights $p$ satisfying \ref{balanced}.
Indeed, it is $\cal NP$-hard to determine whether
$p \in \QQ_+(M)$, even if $M$ is cographic
$\cite{Hol}$.
Some further progress has been made
on Problem \ref{Hilbert problem}.
%has been made by M.\ Laurent and others. 
For example, the dual of any projective geometry PG$(n,q)$
(including $F_7^*= {\rm PG}^*(2,2)$)
belongs to $\HH$ since its circuits
are linearly independent in $\QQ^E$.
%A.\ Seb\H{o} has pointed out to me that
It follows from matroid partition theory (see \cite{CFS})
that the bases of a matroid form a Hilbert base,
and hence all uniform matroids belong to $\HH$.
M.\ Laurent \cite{Lau} has shown that $\HH$ contains
every proper minor of $M^*(K_6)$
whereas no cographic matroid containing
an $M^*(K_6)$ minor is in $\HH$.
As far we know, the following problem is open.
%
\begin{problem}\label{Hilbert minor problem}
Is the class of cographic matroids in $\HH$
closed under taking minors?
\end{problem}
%
\section*{Acknowledgement}
An early version of this paper appears in the first author's
Masters thesis~\cite{Fu}.  We would like to thank
B.~R.~Alspach for helpful comments on the thesis.

%References are double spaced for journal submission
\renewcommand{\baselinestretch}{1.6}\small\normalsize

\begin{thebibliography}{99}

\bibitem{Als}
{\sc B.~Alspach, L.~Goddyn and C-Q Zhang},
Graphs with the circuit cover property,
{\it Trans. Amer. Math. Soc.\/} {\bf 344} (1994), 131--154.

%\bibitem{Bjo}
%{\sc A.~Bj\"orner, M.~Las Vergnas, B.~Sturmfels,
%N.~White, G.~M.~Zieg\-ler},
%{\it Oriented Matroids,
%Encyclopedia of Mathematics and its Applications\/}
%{\bf 46}, Cambridge University Press, Cambridge (1993).
 
\bibitem{CFS}
{\sc W.~Cook, J.~Fonlupt, A.~Schrijver}
An integer analogue of Carath\'eodory's Theorem,
{\it J. Comb. Theory Ser. B\/} {\bf 40} (1986), 63--70.

\bibitem{FanZha}
{\sc G.~Fan and C-Q Zhang},
Circuit Decompositions of Eulerian Graphs,
{\it J. Comb. Theory Ser. B\/}, submitted.

\bibitem{Fu}
{\sc X-D Fu},
Matroids with the circuit cover property,
Masters thesis, Department of Mathematics and Statistics, 
Simon Fraser University, September, 1991.

\bibitem{God}
{\sc L.~Goddyn},
Cones, lattices and Hilbert bases of circuits and perfect
matchings.
{\it in\/} ``Graph Structure Theory'',
N.~Robertson, P.~Seymour, Eds.,
{\it Contemporary Mathematics\/} {\bf 147}, pp. 419--440.
American Mathematical Society, 1993.

\bibitem{GHM}
{\sc L.~Goddyn, J.~van den Heuvel, S.~McGuinness},
Removable circuits in multigraphs,
in preparation.

\bibitem{Hol}
{\sc I.~Holyer},
The NP-completeness of edge-coloring,
{\it SIAM J. Comput.\/} {\bf 10} (1981), 718--720.

\bibitem{Jac} 
{\sc B.~Jackson},
On circuit covers, circuit decompositions and Euler tours of graphs,
{\it in\/} ``Surveys in Combinatorics,''
(Keele Ed.), 
{\it London Math. Soc. Lecture Note Ser.\/} {\bf 187},
pp. 191--210
Cambridge Univ. Press, Cambridge, 1993. 

\bibitem{Lau}
{\sc M.~Laurent},
Hilbert bases of cuts,
Research report {\it LIENS -- 93 -- 9\/},
Laboratoire d'Informatique, URA 1327 du CNRS,
D\'epartement de Math\'ematiques et d'Informatique,
Ecole Normale Sup\'erieure, April 1993.

\bibitem{Lov}
{\sc L.~Lov\'asz, \'A.~Seress},
The cocycle lattice of binary matroids.
{\it Europ. J. Combinatorics\/} {\bf 14} (1993), 241--250.

\bibitem{Sey1}
{\sc P.~D.~Seymour},
Sums of circuits,
{\it in\/} ``Graph Theory and Related Topics'',
(J.~A.~Bondy and U.~S.~R.~Murty, Eds.), pp. 341--355,
Academic Press, New York/Berlin, 1979.
 
\bibitem{Sey3}
{\sc P.~D.~Seymour},
Decomposition of regular matroids,
{\it J. Combin. Theory Ser. B\/} {\bf 28} (1980), 305--359.

\bibitem{Sey2}
{\sc P.~D.~Seymour},
Matroids and multicommodity flows,
{\it Europ. J.  Combinatorics\/} {\bf 2} (1981), 257--290.

\bibitem{Tru}
{\sc K.~Truemper},
{\it Matroid Decomposition\/}, Academic Press, Boston (1992).

\bibitem{Oxl}
{\sc J.~G.~Oxley},
{\it Matroid Theory\/},
Oxford University Press, New York (1992).

\bibitem{Wag}
{\sc K.~Wagner},
Uber eine Eigenschaft der evenen Komplexe,
{\it Math. Ann.\/} {\bf 114} (1937), 570--590.
%
%\bibitem{Wel}
%{\sc D.~Welsh},
%{\it Matroid Theory\/},
%Academic Press, San Francisco (1976).

\bibitem{Zha4}
{\sc C-Q Zhang},
Cycle cover theorems and their applications,
{\it in\/} ``Graph Structure Theory,''
(N.~Robertson and P.~Seymour, Eds.),
{\it Contemporary Mathematics\/} {\bf 147} (1993), 405--418.

\bibitem{Zha1}
{\sc C-Q Zhang},
Cycle covers and cycle decompositions of graphs,
{\it Annals Discrete Math.\/} {\bf 55} (1993), 183--190.

\bibitem{Zha2}
{\sc C-Q Zhang},
On even circuit decompositions of eulerian graphs,
{\it J. Graph Theory\/} {\bf 18} (1994), 51--57.

\bibitem{Zha3}
{\sc C-Q Zhang},
Hamiltonian weights and unique 3-edge-colorings of cubic graphs,
{\it Journal of Graph Theory\/}, (to appear).

\end{thebibliography}
\end{document}