% % December, 1991 % \documentstyle[art10,amssymbols]{article}% \newcommand{\C}{{\bf C}}% \newcommand{\SS}{{\bf S}}% \newcommand{\M}{{\bf M}}% \newcommand{\B}{{\bf B}}% \newcommand{\F}{{\bf F}}% \newcommand{\bs}{\backslash} \newcommand{\se}{\subseteq} % Uncomment the following 4 lines if AMS fonts are avail. \newcommand{\QQ}{{\Bbb Q}}% \newcommand{\QQP}{{\Bbb Q}_{\geq 0} }% \newcommand{\ZZ}{{\Bbb Z}}% \newcommand{\ZZP}{{\Bbb Z}_{\geq 0} }% % Comment out the following 4 lines if AMS fonts are avail. % \newcommand{\QQ}{\mbox{\boldmath$\cal Q$}}% % \newcommand{\QQP}{{\QQ}_{\geq 0} }% % \newcommand{\ZZ}{\mbox{\boldmath $\cal Z$}}% % \newcommand{\ZZP}{{\ZZ}_{\!\geq 0} }% \newtheorem{lemma}{\sc Lemma}[section]% \newtheorem{theorem}[lemma]{\sc Theorem}% \newtheorem{proposition}[lemma]{\sc Proposition}% \newtheorem{corollary}[lemma]{\sc Corollary}% \newtheorem{claim}[lemma]{\sc Claim}% \newtheorem{conjecture}[lemma]{\sc Conjecture}% \newtheorem{remark}[lemma]{\sc Remark}% \newtheorem{note}[lemma]{\sc Note}% \newtheorem{algorithm}[lemma]{\sc Algorithm}% \newtheorem{example}[lemma]{\sc Example}% \newtheorem{observation}[lemma]{\sc Observation}% \newtheorem{definition}[lemma]{\sc Definition}{}% \newtheorem{numbered}[lemma]{}% \newenvironment{proof}{\noindent {\sc Proof.}}{$\Box$\par\medskip}% \date{Dec. 6, 1991} \title{Cones, Lattices and Hilbert Bases of Circuits and Perfect Matchings} \author{Luis A. Goddyn \thanks{Supported by the National Sciences and Engineering Research Council operating grant \#A-4699 and SFU's President's Research Grant \#A-2326.}\\ Department of Mathematics and Statistics\\ Simon Fraser University } \begin{document} \maketitle \begin{abstract} There have been a number of results and conjectures regarding the cone, the lattice and the integer cone generated by the (real-valued characteristic functions of) circuits in a binary matroid. In all three cases, one easily formulates necessary conditions for a weight vector to belong to the set in question. Families of matroids for which such necessary conditions are sufficient have been determined by Seymour; Lov\'asz, Seb\H{o} and Seress; Alspach, Fu, Goddyn and Zhang, respectively. However, circuits of matroids are far from being well understood. Perhaps the most daunting (and important) problem of this type is to determine whether the circuits of a matroid form a {\em Hilbert basis}. That is, for which matroids does the integer cone coincide with those vectors which belong to both the cone and the lattice? Additionally, all of the above questions have been asked with regard to perfect matchings in graphs. We present a survey of this topic for circuits in matroids, and also for perfect matchings in graphs. There are some striking similarities, especially with regard to the role that Petersen's graph plays in both of these subjects. A possible explanation is that much of the theory of perfect matchings is captured by the circuits of certain 1-element extensions of graphic matroids called {\em grafts}. For example, a possible extension to the class of grafts of the following result would imply the Four-color theorem: {\em The circuits of a graph form a Hilbert basis if and only if the graph has no Petersen minor}. \end{abstract} \section{Introduction and Notations} A fruitful setting for studying a combinatorially defined collection of subsets of a ground set $E$ is to consider the corresponding collection of real-valued characteristic functions. This observation underlies much of the theory of polyhedral combinatorics and integer programming. Our aim is to compare the collection of circuits in a matroid with the collection of perfect matchings in a graph by considering properties of their characteristic functions. For $S \subseteq E$ we denote by $\chi ^ S$ the $\{0,1\}$-characteristic vector of $S$ in $\QQ^E$. For any collection $\SS$ of such subsets of $E$, we define the {\em linear hull, cone, lattice} and {\em integer cone} of $\SS$ as follows. \begin{eqnarray*} Lin.Hull\,(\SS) & := & \{ \sum_{S \in \SS} \alpha_S \chi^S : \alpha_S \in \QQ \}\\ Cone\,(\SS) & := & \{ \sum_{S \in \SS} \alpha_S \chi^S : \alpha_S \in \QQP\}\\ Lat\,(\SS) & := & \{ \sum_{S \in \SS} \alpha_S \chi^S : \alpha_S \in \ZZ \}\\ Int.Cone\,(\SS) & := & \{ \sum_{S \in \SS} \alpha_S \chi^S : \alpha_S \in \ZZP\} \end{eqnarray*} We have the following four containments. \[ Int.Cone\,(\SS) \begin{array}{rcl} \subset & \!\!\! Cone\,(\SS) \!\!\!& \subset \\ \subset & \!\!\! Lat\,(\SS) \!\!\! & \subset \end{array} Lin.Hull\,(\SS) .\] Throughout this paper $\SS$ shall be either the collection $\C = \C(M)$ of circuits in a matroid $M = (E,\C)$ on the ground set $E$, or the collection of perfect matchings (1-factors) $\M = \M(G)$ in a graph $G = (V,E)$. It can be argued that the integer cone is the most interesting of the four sets defined above. A vector $p$ belongs to $Int.Cone\,(\SS)$ if and only if there is a list of subsets in $\SS$ such that each $e \in E$ belongs to precisely $p(e)$ members of the the list. Such a list is often called a {\em cover} of the weighted set $(E,p)$. If $p$ is the constant unit vector $\bf 1$, then a cover of $(E,p)$ is a {\em decomposition} of $E$ into subsets from $\SS$. A cover of $(E,{\bf 2})$ is often called a {\em double cover} of $E$. When $\SS = \C$, we are in the area of {\em circuit covers} and {\em circuit decompositions}, where numerous papers \cite{Als,Ber,Bon2,Cat,Fan1,Fan2,Fle2,Fu,God1,Hag,Jac1,Jae2,Jam1,Jam2,Jam3,Sey1,Tar1,Tar2,Zha1,Zha3} have been written, especially for graphic matroids. Many of these papers are concerned with circuit covers which have additional conditions on parameters such as the number of circuits in the cover, or the total length of the circuits. Here, we are concerned only with the existence of circuit covers of fixed vectors $p$. Where $\SS = \M$, we are studying {\em perfect matching covers} of graphs. The case $p= \bf 1$ is concerned with {\em 1-factorizations} of graphs, where we have the classical {\em Four-color Theorem} and the stronger {\em $4$-flow conjecture} of Tutte \cite{Tut2}. For $p=\bf 2$ we have {\em perfect matching double covers} with unsolved conjectures of Fulkerson \cite{Ful} and Seymour \cite{Sey6}. \vspace{2mm} Although combinatorially less interesting, the cone and the lattice of $\SS$ are generally easier to determine than the integer cone. For example, the both the cone and the lattice generated by (characteristic vectors of) perfect matchings in a graph have been well characterized \cite{Edm1,Lov1}, whereas it is {\em NP-hard} to determine whether {\bf 1} belongs to the integer cone of perfect matchings of a cubic graph \cite{Hol}. The study of the cone and the lattice is further motivated by the formula % \begin{equation}\label{HilbertIneq} Int.Cone\,(\SS) \se Cone\,(\SS) \cap Lat\,(\SS) \end{equation} % which provides necessary conditions for a vector $p$ to belong to the integer cone of $\SS$. Understandably, it is of special interest to know when equality holds in (\ref{HilbertIneq}). % \begin{definition}\label{HilbertBasis} A set of vectors $\SS$ for which equality holds in {\rm (\ref{HilbertIneq})} is called a {\em Hilbert basis}. \end{definition} % This concept is closely related to {\em total dual integrality}, and has been studied by various authors \cite{Gil,Coo,Sch,Seb1}. In our setting, the {\em Hilbert basis problem} is to determine classes of matroids and graphs for which $\C$ and $\M$ form Hilbert bases. This problem will be addressed in Sections \ref{IntCone} and \ref{MIntCone}, respectively. It must be emphasised that the cone and the lattice of $\SS$ are worthy of independent study. For example, the characterizations of both the cone \cite{Edm1} and the lattice \cite{Lov1} of perfect matchings are landmarks in graph theory. Both the cone and the lattice of circuits in a graph have simpler descriptions \cite{Sey1} than those of perfect matchings. However, they easily become intractable for more general classes of matroids. For example, determining whether a vector belongs to the cone of circuits in a cographic matroid is NP-complete \cite{Karz}. Those who work with either circuits or perfect matchings agree that Petersen's graph plays an anomalous role. (This is particularly evident when considering the Hilbert basis problem.) This observation suggests that these two areas may be related. In fact, connections between circuits and perfect matchings in graphs are already well established. For example, the Chinese Postman problem \cite{Edm2} is closely related to both matchings and Euler tours. As another example, the Four-color theorem is equivalent to the statement that any bridgeless planar graph is the union of two subgraphs, each of which is the edge-disjoint union of circuits. One can not say, however, that such connections satisfactorily explain the predominating role of Petersen's graph. In Section \ref{CircMat}, we describe another connection between circuits and perfect matchings, which is expressed via certain 1-element extensions of graphic matroids called {\em grafts}. It is through the integer cone of circuits in grafts that we see a possible explanation of the role of Petersen's graph in the theory of circuits and perfect matchings. \vspace{2mm} We shall assume basic familiarity with graphs and matroids as in \cite{Bon1} and \cite{Wel}. Thus a {\em bridge} or {\em coloop} of a matroid $M=(E,\C)$ is any element contained in no circuit. Two non-bridge elements are {\em in series} or {\em coparallel} if no circuit contains exactly one of them. Recall that ``coparallel'' is an equivalence relation on $E$. A {\em bond} or {\em cocircuit} is a minimal subset of $E$ intersecting all bases of $M$. The {\em dual}, $M^*$ of $M$ has ground set $E$ and its circuits are the bonds of $M$. If $G=(V,E)$ is a graph then $M(G)$ denotes the matroid on $E(G)$ whose circuits are the polygons in $G$. For binary matroids (including graphs) a {\em cycle} is any (element-) disjoint union of circuits in $M$, including the empty cycle. Thus a cycle in a graph is the edge set of any subgraph whose vertices all have even degree. A matroid is {\em binary} if it is isomorphic to a set of vectors with linear dependence over GF(2) or, equivalently, if it has no $U_4^2$-minor (that is, no minor isomorphic to $U_4^2$, the {\em uniform} matroid of rank 2 on 4 elements). The cycles of a binary matroid under the symmetric difference operator $\Delta$ form a vector space of dimension $|E| - rank(M)$ in GF$(2)^E$ called the {\em cycle space} of $M$. Dually, {\em parallel} elements, {\em loops} and {\em cocycles} in $M$ are are defined to be coparallel elements, coloops and cycles in $M^*$, respectably. A cocycle is sometimes called a {\em cut}. Where convenient, we identify a subset of $E$ with its characteristic vector, a graph $G$ with its matroid $M(G)$, and a subset of edges of a graph with the subgraph it induces. \section{The Cone and Lattice of Circuits}\label{ConeLat} Although there is no known non-trivial characterization of $Cone\,(\C), Lat\,(\C)$, and $Int.Cone\,(\C)$ for general matroids, the linear hull of circuits has an easy description. Any vector in $Lin.Hull\,(\C)$ must clearly be zero on bridges and constant on coparallel classes. In fact, these two conditions characterize the linear hull. % \begin{proposition}\label{LinHull} For any matroid $M=(E,\C)$, $Lin.Hull\,(\C)=\{p \in \QQ^E : p(e)=0$ for any bridge $e$, and $p(f)=p(g)$ for $f,g$ coparallel \}. \end{proposition} % \begin{proof} Let $[e]$ denote the set of elements which are coparallel with $e$. It is enough to show that, for any element $e$ in a bridgeless matroid, $\chi^{[e]} \in Lin.Hull\,(\C)$. We use the following observation of Seymour, \cite[(3.2)]{Sey2}. \begin{observation} \label{unicone} If $M$ is bridgeless then ${\bf 1} \in Cone\,(\C)$. \end{observation} \noindent (Here ${\bf 1}= \chi ^ E$ is the vector of ones.) As $M$ is bridgeless, so is $M \bs [e]$, hence $ \chi^E , \chi ^ {E \bs [e]} \in Cone\,(\C). $ Subtracting, we have $\chi^{[e]} \in Lin.Hull\,(\C)$. \end{proof} We now examine the cone of circuits. Since no circuit in a matroid meets a bond in exactly one element, any weight vector $p \in Cone\,(\C)$ must be {\em balanced}. That is, no element in $M$ has more than half the total weight of any bond containing it. Seymour \cite{Sey2} has characterized those matroids for which the cone of circuits is precisely the set of non-negative balanced vectors. % \begin{theorem}\label{Cone} For any matroid $M=(E,\C)$, $Cone\,(\C) \se \{p \in \QQP^E : p(e) \le p(B \bs e)$ for all $e \in B$, for all bonds $B$\}, with equality if and only if $M$ has no minor isomorphic to any of $U^2_4$, $M^*(K_5)$, $F^*_7$, or $R_{10}$. $\Box$ \end{theorem} % (As usual, $p(S)$ denotes $\sum_{e \in S} p(e)$ for any $S \se E$.) A matroid for which equality holds in Theorem \ref{Cone} is said to have the {\em Sums of Circuits Property}. In particular, all graphs have the Sums of Circuits Property \cite{Sey1}. It follows from Theorem \ref{Cone} (and is not difficult to show directly) that the Sums of Circuits Property is preserved under taking minors. To see that each of the four obstructing minors (see \cite{Sey2} or \cite{Sey7} for their definitions) do not have this property consider the following four weight vectors $p \in \QQP^E$. \begin{description} \item[$U^{2}_4$:] $\;\;p(e_0)=2$ for some fixed $e_0 \in E$ and $p(e)=1$ for the remaining 3 elements. \item[$M^*(K_5)$:] $p(e)=1$ for all edges $e$ in some fixed subgraph of $K_5$ isomorphic to $K_{2,3}$ and $p(e)=2$ for the remaining 4 edges. \item[$F^*_7$:] $\;p(e)=1$ for all elements $e$ in some fixed 4-circuit and $p(e)=2$ for the remaining 3 elements. \item[$R_{10}$:] $p(e)=3$ for all elements $e$ in some fixed 3-subset of elements not contained in any 4-circuit, and $p(e)=1$ for the remaining 7 elements. \end{description} One easily checks that each of these vectors is balanced. To show that they are not in $Cone\,(\C)$ we use {\em Farkas' Lemma}. That is, we describe a weight vector $s \in \QQ^E$ which has positive inner product with $p$, but for which each circuit in the matroid has non-positive weight. For $U^2_4$ we take $s(e_0)= 2$ and $s(e)= -1$ for the remaining 3 elements. In each of the other three examples we take $s(e)= -1$ if $p(e)=1$ and $s(e)=1$ otherwise. It appears unlikely that there is a good description of $Cone\,(\C)$, even for cographic matroids, as it is known \cite{Karz} that the membership problem for the cone of bonds in $K_n$ is {\em NP-hard}. Some work \cite{Dez} has been done toward finding facets of this cone. \vspace{2mm} Likewise, the lattice of circuits appears to be difficult to characterize for general matroids. Indeed it is not easy to imagine non-trivial necessary conditions for a vector to belong to $Lat\,(\C)$. The situation is better, although not yet settled, for binary matroids. In a binary matroid $M$, any circuit intersects any bond in an even number of elements. Thus for a weight vector to belong to $Lat\,(\C)$, it is necessary that $p$ be {\em eulerian}, that is, $p$ must be integer-valued and each bond in $M$ must have even total weight. This condition turns out to be sufficient for an important class of binary matroids. % \begin{proposition}\label{Lat} For any binary matroid $M \! =(E,\C)$, $Lat(\C) \se Lin.Hull(\C)$ $\cap \{p \in \ZZ^E : p(B)$ is even for all bonds $B\}$, with equality if $M$ has no $F^*_7$-minor. \end{proposition} % \begin{proof} Assume that $M$ has no $F^*_7$-minor and that it contains neither bridges nor two elements in series. Let $p$ be an integer weight vector such that each bond has even weight. The set $F$ of edges having odd weight belongs to the cycle space of $M$ since $F$ is orthogonal to every bond (over GF(2)). It suffices to show that $2 \chi^{\{e\}} \in Lat\,(\C)$ for any $e \in E$, since this would imply that the even-valued vector $p+ \chi^F$ --- and hence $p$ --- belongs to $Lat\,(\C)$. To this end, we need only find two circuits $C_1 , C_2$ such that $C_1 \cap C_2 = \{ e \}$, whereby $2 \chi^{\{e\}} = \chi^{C_1} + \chi^{C_2} - \chi^{C_1 \Delta C_2}$. The existence of $C_1, C_2$ follows, for graphs, from Menger's theorem and, in general, from a theorem of Seymour \cite{Sey3} which states that all binary matroids with no $F^*_7$-minor have the {\em Integer Max-Flow Min-Cut Property}. \end{proof} A matroid for which equality holds in Proposition \ref{Lat} is said to have the {\em Lattice of Circuits Property}. In particular, all graphic and cographic matroids, and indeed all regular matroids have the Lattice of Circuits Property, as do all matroids with the Sums of Circuits Property. Unlike the Sums of Circuits Property, the class of matroids with the Lattice of Circuits Property is not is not closed under taking minors (although it is closed under element-contraction). For example, although $F^*_7$ does not have the Lattice of Circuits Property, exactly one of the two 1-element extensions of $F^*_7$ does. Very recently, Lov\'asz, Seb\H{o} and Seress \cite{Lov3} have characterized the class of binary matroids with the Lattice of Circuits Property. We shall state their result without proof. We need a definition. In \cite{Sey2} Seymour defines, for $k = 1,2,3$, the {\em $k$-sum} of two binary matroids $M_1, M_2$ to be the matroid on $E(M_1) \Delta E(M_2)$ whose circuits are all subsets of the form $C_1 \Delta C_2$ where $C_i \in \C(M_i)$, $i=1,2$. In particular, $k=1$ if $E(M_1) \cap E(M_2) = \emptyset$; $k=2$ if $E(M_1) \cap E(M_2)$ consists of a single element which is not a loop in each $M_i$; and $k=3$ if $E(M_1) \cap E(M_2)$ is a circuit of cardinality 3 in each $M_i$. % \begin{definition} Any matroid which can be obtained from copies of the Fano plane $F_7$ via 1-, 2- and 3-sums shall be called a {\em Fano-cycle}. \end{definition} % \begin{theorem} \label{LatProp} {\rm \cite{Lov3}} A binary matroid $M$ has the Lattice of Circuits Property if and only if the dual matroid $M^*$ contains no Fano-cycle as a submatroid. $\Box$ \end{theorem} % \begin{example} \label{AS23} The {\em affine geometry} AG$(2,3)$ is a Fano-cycle of cardinality $8$, since it is the $3$-sum of two Fano planes. As AG$(2,3)$ is self dual, Theorem \ref{LatProp} asserts that AG$(2,3)^* \cong$ AG$(2,3)$ does not have the Lattice of Circuits Property. Indeed this follows directly from the fact all circuits in AG$(2,3)$ have cardinality four. \end{example} % In general, the lattice of circuits in a binary matroid can be arbitrarily ``sparse''. % \begin{example} \label{PG2m} The binary projective geometry of dimension $m$, PG$(2,m)$, is the binary matroid represented by the $2^{m+1}-1$ non-zero binary $(m+1)$-tuples. For example, PG$(2,2) \cong F_7^*$. For $0 \le k \le m$, a {\em $k$-flat} is any submatroid of PG$(2,m)$ which is isomorphic to PG$(2,k)$. The cocircuits of PG(2,$m$) are precisely the complements of its $(m-1)$-flats, and thus have cardinality $2^m$. It follows that any vector in lattice of cocircuits of PG$(2,m)$ (that is, $Lat(\C ($PG$(2,m)^*)$) has total weight divisible by $2^m$. In fact, $p \in Lat\,(\C ($PG$(2,m)^*)$ if and only if $p(S)$ is divisible by $2^k$, for every $k$-flat $S$ of PG$(2,m)$, $0 \le k \le m$ {\rm \cite{Lov3}}. \end{example} \section{Hilbert Bases of Circuits}\label{IntCone} The {\em circuit cover problem} is to determine whether a given weight vector belongs to the integer cone of circuits of a given matroid. We are interested in finding classes of matroids for which this the circuit cover problem can be solved. Having seen that the cone and the lattice of circuits are often characterizable, we are naturally led to the Hilbert basis problem for circuits (recall Definition \ref{HilbertBasis}). That is, we would like to determine those matroids $M$ for which $(M,p)$ has a circuit cover for all $p \in Cone\,(\C) \cap Lat\,(\C)$. The circuits of a matroid do not always form a Hilbert basis. % \begin{example}\label{P_10} Let $P_{10}$ denote Petersen's graph and let $p_{10}$ denote the weight vector which takes the value $2$ on some fixed 1-factor of $P_{10}$, and $1$ on the complementary 2-factor. One easily checks that $p_{10}$ is balanced and eulerian, and hence belongs to $Cone\,(\C) \cap Lat\,(\C)$, by Theorems \ref{Cone} and \ref{Lat}. However, $p_{10} \not\in Int.Cone\,(\C)$ since $p_{10} - \chi ^ C \not\in Cone\,(\C)$, for all $C \in \C$. \end{example} % Every matroid for which we know that $\C$ does not form a Hilbert basis contains Petersen's graph as a minor. On this flimsy evidence one might propose the following. % \begin{conjecture}\label{noP10} If a matroid contains no $P_{10}$-minor then $\C$ forms a Hilbert basis. \end{conjecture} % As we shall see, progress has been made toward this conjecture, but mostly for graphs and other binary matroids. We direct the reader's attention to the strikingly similar Conjecture \ref{MnoP10} regarding perfect matchings in graphs. A basic problem with dealing with Conjecture \ref{noP10} is that we do not know $Cone\,(\C)$ for general matroids. Thus it makes sense restrict our attention to matroids for which this cone has a nice description, namely, the matroids with the Sums of Circuits Property. Recall from Theorems \ref{Cone} and \ref{Lat} that, for such matroids, the cone (lattice) of circuits is precisely the set of balanced (eulerian) weight vectors. In 1979, Seymour verified Conjecture \ref{noP10} for planar graphs by showing that every balanced, eulerian edge-weighted planar graph has a circuit cover. In 1981, Seymour \cite{Sey2} characterized the matroids with the Sums of Circuits Property and, in the same paper, proposed that Conjecture \ref{noP10} holds for such matroids. Recently, Alspach, Goddyn and Zhang \cite{Als}, shed Seymour's planarity restriction, and verified Conjecture \ref{noP10} for the class of graphic matroids. Using this result, and Seymour's matroid decomposition theorems, Fu and Goddyn \cite{Fu} have since shown that the conjecture holds for all matroids with the Sums of Circuits Property. We state this result in an alternate form. We say that a matroid has the {\em Circuit Cover Property\/} if the integer cone of circuits is precisely the set of balanced and eulerian weight vectors. Thus, any matroid with the Sums of Circuits Property has the Circuit Cover Property exactly when its circuits form a Hilbert basis. % \begin{theorem}\label{CCP} A matroid has the Circuit Cover Property if and only if it has no minor isomorphic to any of $U^2_4$, $M^*(K_5)$, $F^*_7$, $R_{10}$, $M(P_{10})$. $\Box$ \end{theorem} % Perhaps the most relevant aspect of Theorem \ref{CCP} is that planarity restrictions on graphs have been dropped. The literature abounds with graph properties which are known to hold for planar graphs, and which are conjectured to hold for wider classes of graphs. Such problems include classical ``nuts'' such as the {\em circuit double cover conjecture} and Tutte's {\em Nowhere-zero flow} conjectures. Thus it is of interest whenever a planarity restriction can be dropped (or relaxed) from the hypothesis of a known theorem. For example, Theorem \ref{CCP} has already been used to extend results involving Even Circuit Decompositions \cite{Zha3} and Compatible Circuit Decompositions of Eulerian graphs \cite{Zha2} from the class of planar graphs to the class of graphs with no $K_5$-minor. We refer the interested reader to \cite{Als} for more applications Theorem \ref{CCP}. Little is known about the integer cone of circuits in non-binary matroids. As observed by Seb\H{o} \cite{Seb1}, the circuits of uniform matroids $U_n^k$ do indeed form a Hilbert basis. This follows from the fact that the circuits of $U_n^k$ are precisely the bases of $U_n^{k+1}$ (when $k r$, $R \cup \{ k \}$ is good (for the class of graphs) if and only if $R$ is good. \end{proposition} % \begin{proof} The ``only if'' part is trivial. Conversely, suppose that $R$ is good and let $p' \in R'^E \cap Cone\,(\C) \cap Lat\,(\C)$, where $R' := R \cup \{ k \}$. As $p'$ is eulerian, the set $F$ of elements having weight $k$ form a cycle. Clearly, $p := p' - (k-r) \chi^F$ belongs to $R^E$ and is eulerian. We claim that $p$ is balanced. Suppose not. Then for some cocircuit $B$ and some $e \in B$ we have $p(e) > p(B \bs \{ e \} )$ whereas $p'(e) \le p'(B \bs \{ e \} )$. As $|F \cap B|$ is even, this implies $| F \cap B \bs \{ e \} | \ge 2$ and $e \not \in F$. From this we have $\max R \ge p(e) > p(B \bs \{ e \} ) \ge 2r$, contradicting the hypothesis and proving the claim. Thus, $p \in Int.Cone\,(\C)$. Since $\chi ^F \in Int.Cone\,(\C)$, we have $p' \in Int.Cone\,(\C)$. \end{proof} In particular, $\{ 2,3 \}$ is good if and only if the circuit double conjecture is true. We recall that the range $\{ 1,2 \}$ is bad. For larger consecutive pairs we have the following. % \begin{proposition}\label{ConsecutiveGood} For the class of graphs, the range $\{ k, k+1 \}$ is good for all $k \ge 3$. \end{proposition} % \begin{proof} When $k$ is even, this follows from Propositions \ref{CrC} and \ref{OneOdd}. It suffices to prove the cases $k=3$ and $k=5$, since ${\bf 4} \in Int.Cone\,(\C)$ for any bridgeless graph. For these two cases we use refined versions of the results of Jaeger and Fan mentioned in the proof of Proposition \ref{CrC}. Jaeger \cite{Jae1} actually proved that any bridgeless graph contains $7$ cycles $C_1 , \ldots ,C_7$ such that every edge is contained in exactly $4$ of them. If $p \in \{ 3,4 \} ^E \cap Cone\,(\C (G)) \cap Lat\,(\C (G))\/$ then $G$ is bridgeless and the set $F$ of edges having weight $3$ form a cycle. We consider the $7$ cycles of the form $F \Delta C_i$. Since $7 = 3+4$ one easily sees that any edge in $F$ is contained in exactly $3$ of these cycles and that any edge in $E \bs F$ is contained in exactly $4$ of them. As each cycle decomposes into circuits, we have $p \in Int.Cone\,(\C)$. The proof for $k=5$ is exactly analogous, using the fact $11=5+6$ and Fan's observation \cite{Fan2} that any bridgeless graph contains $11$ cycles such that every edge is contained in exactly $6$ of them (actually, Fan shows that only $10$ cycles are needed, but we may take the empty cycle to be the eleventh). \end{proof} We remark that the this proof works equally well for any regular matroid which has a nowhere-zero 6-flow. Little more is known about good and bad ranges. Indeed, it is frightfully easy to pose difficult conjectures. One which is most likely to be true, but for which I know of no proof is the following. % \begin{conjecture}\label{CertainlyTrue} For some $k \ge 2$, the range $\{ k,k+2 \}$ is good for the class of graphs. \end{conjecture} This conjecture has a very different flavor between odd and even values of $k$. At the other extreme, the boldest conjecture of this type that one can possibly make is the converse of Proposition \ref{BadRanges}. % \begin{conjecture}\label{bold} A range $R$ is good (for the class of graphs) if and only if $\{1,k \} \not \se R$, for all $k \ge 2$. \end{conjecture} % The following table summarizes results regarding good and bad ranges for the class of graphic matroids. \begin{center} \begin{tabular}{c|c|l} {\em Range} & {\em Status} & {\em Comments} \\ \hline $\{ 2 \}$ & Good? & Conjecture \ref{CDC} \\ $\{ k \}$, $k \not = 2$& Good & Proposition \ref{CrC}\\ $\{ 1,k \}$, $k \ge 2$ & Bad & Proposition \ref{BadRanges}\\ $\{ 2, 3 \}$ & Good? & Equivalent to Conjecture \ref{CDC}\\ $\{ k,k+1 \}$, $k \ge 3$ & Good & Proposition \ref{ConsecutiveGood}\\ $\{ k,k+2 \}$, $k \ge 2$ & Good? & Conjecture \ref{CertainlyTrue}\\ $\{ 2k \colon k \in \ZZP \}$ & Good?? & Conjecture \ref{EvenGood}\\ $\ZZP \bs \{ 1 \}$ & Good???? & Conjecture \ref{bold} \end{tabular} \end{center} Perhaps some study into good and bad ranges of cographic matroids is warranted. Here we suspect that all ranges are good for this class of matroids. % \begin{conjecture}\label{BondHilbert} The bonds of any graph form a Hilbert basis. \end{conjecture} % As $M(P_{10})$ is not cographic, this conjecture would follow immediately from Conjecture \ref{noP10}. However, this has only yet been verified for the class of cographic matroids with no $M^*(K_5)$-minor \cite{Fu}. Again, the major problem is our lack of knowledge about the cone of cuts in graphs \cite{Dez}. In contrast to the graphic matroids, it is easy to show that any range of cardinality $1$ is good for the class of cographic matroids (see \cite{Jam1}). On the other hand, one cannot use flow theory to prove statements such as Proposition \ref{ConsecutiveGood} for the class of cographic matroids, since the chromatic number (which is the dual flow number) of graphs is not bounded. We conclude this section by pointing out that I know of no reason why Conjecture \ref{bold} cannot be extended to the class of all matroids. Further, it is possible to formulate a common generalization to the bold Conjectures \ref{noP10} and \ref{bold}, although it is probably imprudent to speculate further on the matter. Still, it would be very interesting to find any example of a matroid with a weight vector in $ Cone\,(\C) \cap Lat\,(\C) \bs Int.Cone\,(\C)$ which is not based on Petersen's graph (as in Proposition \ref{BadRanges}). \section{Cone and Lattice of Perfect Matchings}\label{MConeLat} Let $\M$ denote the set of perfect matchings (as subsets of edges) in a graph $G = (V,E)$. As with circuits in graphs, each of $Lin.Hull\,(\M)$, $Cone\,(\M)$ and $Lat\,(\M)$ has been well characterized, and there exist polynomial-time membership tests for these three subsets of $R^E$. These results are more complicated than the corresponding ones for circuits, and we shall only state them roughly. We refer the reader to \cite{Edm1,Lov1} for further details. One begins by ``preprocessing'' the fixed graph $G$. First, those edges of $G$ which are contained in no perfect matchings are deleted. Then we perform a {\em brick decomposition} on the resulting graph as follows. A {\em tight cut} is a edge cut which intersects each perfect matching in exactly one edge. For example, any {\em trivial} edge cut (that is, an edge cut in which one of its two {\em shores} contains a single vertex) is tight. Any non-trivial tight cut yields two proper minors of $G$ obtained by contracting each of the shores of the cut. In a brick decomposition, non-trivial tight cuts are recursively found in each of these minors. A similar reduction is performed whenever one of the minors has a vertex-cut of cardinality less than three. Any multiple edge occurring in a minor is replaced with a single edge. (If $G$ is edge-weighted then this new edge is assigned the total weight of the parallel class it replaces.) The result of a brick decomposition of $G$ is a list of simple 3-connected non-bipartite minors which contain no non-trivial tight cuts. Each member of this list is called a {\em brick} of $G$. It turns out that this list of bricks is independent (up to re-ordering and isomorphism) of the particular tight-cut decomposition chosen for $G$. Lov\'asz \cite{Lov1} points out that a list of bricks for $G$ can be obtained in polynomial time. % \begin{theorem}\label{MLinHull} For any graph $G$ containing an even number of vertices, \newline $Lin.Hull\,(\M)=\{p \in \QQ^E : \exists r \in \QQ,\; p(B)=r$, for all trivial cuts and tight cuts $B$ encountered during a brick decomposition of $G\}$. $\Box$ \end{theorem} % The cone of perfect matchings follows from Edmonds' well known characterization \cite{Edm1} of the convex hull. An {\em odd cut} is an edge cut such that both of its shores contain an odd number of vertices. % \begin{theorem}\label{MCone} For any graph $G$ containing an even number of vertices, \newline $Cone\,(\M)=\{p \in \QQP^E : \exists r \in \QQ,\; p(B)=r$, for all trivial cuts $B$, and $p(B') \ge r$ for all odd cuts $B'\}$. $\Box$ \end{theorem} % The lattice of perfect matchings was characterized by Lov\'asz \cite{Lov1}. Here, bricks of $G$ which are isomorphic to Petersen's graph $P_{10}$ play a central role. We recall that any brick resulting from a brick decomposition of a weighted graph $(G,p)$ naturally inherits a weight function, which we shall also denote by $p$. % \begin{theorem}\label{MLat} For any graph $G$ containing an even number of vertices, \newline $Lat\,(\M)= Lin.Hull\,(\M) \cap \{p \in \ZZ^E : p(C_5)$ is even, for every circuit $C_5$ of length five contained in any brick of $G$ isomorphic to $P_{10}\}$. $\Box$ \end{theorem} % In particular, the lattice of perfect matchings is just the set of integer vectors contained in the linear hull, provided that $G$ has no $P_{10}$-minors. This fact was observed for cubic graphs by Seymour \cite{Sey6}. The necessity of the condition on $p(C_5)$ in Theorem \ref{MLat} follows from the observation that each of the 6 perfect matchings of $P_{10}$ intersect $C_5$ in an even number of edges. In summary, given any weighted graph $(G,p)$, one can determine in polynomial time whether $p$ belongs to the cone, the lattice or the linear hull of perfect matchings in $G$. \section{Perfect Matching Covers} \label{MIntCone} Some well-known results and conjectures address the {\em Perfect Matching Cover Problem}, the problem of determining whether a particular integer vector belongs to $Int.Cone\,(\M)$. We recall the necessary condition that the vector in question belongs to $Cone\,(\M) \cap Lat\,(\M)$, and that $\M(G)$ is said to form a Hilbert basis if this condition is also sufficient. For uniform vectors $\bf k$ with $k>0$, ${\bf k} \in Cone\,(\M)$ if and only if, for some $r \ge 1$, $G$ is an $r$-regular graph with an even number of vertices such that all odd cuts have size at least $r$. Following Seymour \cite{Sey6}, we call such graphs {\em $r$-graphs}. For example, a cubic graph is a $3$-graph if and only if it is bridgeless. We note that, for any $r$-graph, ${\bf 2} \in Lat\,(\M)$. Furthermore, if an $r$-graph has no $P_{10}$-brick then ${\bf 1} \in Lat\,(\M)$. We also note that ${\bf 1} \in Int.Cone\,(\M)$ if and only if the graph has a 1-factorization. Unlike circuit covers, Perfect Matching Cover Problems can often be reduced to problems regarding uniform weight vectors by adding parallel edges to graphs. For example, we have the following. % \begin{observation}\label{MReduceTo1} Let $\cal G$ be any family of graphs containing no $P_{10}$-minors, and which closed under duplicating edges. Then $\M(G)$ forms a Hilbert basis for every $G \in \cal G$ if and only if ${\bf 1} \in Int.Cone\,(\M (H))$ for every $r$-graph $H \in \cal G$. \end{observation} % \begin{proof} The ``only if'' direction follows immediately from the fact that ${\bf 1} \in Cone\,(\M(H)) \cap Lat\,(\M(H))$ for any $r$-graph $H \in \cal G$. For the converse, let $p \in Cone\,(\M(G)) \cap Lat\,(\M(G))$ where $G \in \cal G$. In $(G,p)$, every trivial bond has weight $r$ for some $r \in \ZZP$. Let $H$ be the $r$-regular graph obtained from $G$ by replacing each edge $e$ by $p(e)$ parallel edges. As $G \in \cal G$, so is $H$. Since $p \in Cone\,(\M(G))$, ${\bf 1} \in Cone\,(\M(H))$ so $H$ is an $r$-graph. By hypothesis, ${\bf 1} \in Int.Cone\,(\M(H))$. As any perfect matching in $H$ corresponds to one in $G$, we have $p \in Int.Cone(\M(G))$. \end{proof} % Much of the work that has been done regarding perfect matching covers of $r$-graphs deals with the case $r=3$. Indeed, Seymour \cite[(3.5)]{Sey6} has proposed that this is really the only interesting case. % \begin{conjecture}\label{3-graph} If $r \ge 4$ then any $r$-graph has a perfect matching whose deletion yields an $(r-1)$-graph. \end{conjecture} % This conjecture is not yet known to be true for any $r \ge 4$. Using the above terminology, we list some known results and conjectures regarding perfect matchings % \begin{theorem}\label{4CT} {\rm (Four-color theorem)} For any planar $3$-graph, ${\bf 1} \! \in \! Int.Cone\,(\M)$. $\Box$ \end{theorem} % I do not know the origin of the following natural generalization, though it is implied by Conjecture (7.3) in \cite{Sey8}. % \begin{conjecture}\label{4CTgeneral} For any planar $r$-graph with $r \ge 0$, ${\bf 1} \in Int.Cone\,(\M)$. \end{conjecture} % The case $r=4$ of this conjecture has been has been investigated by Jaeger and others (see \cite{Jae3,Jae4}), and is known to imply the Four-color Theorem. By Observation \ref{MReduceTo1}, Conjecture \ref{4CTgeneral} is equivalent to the assertion that the perfect matchings of any planar graph form a Hilbert basis. Another well-known strengthening of the Four-color Theorem is still open \cite{Tut2}. % \begin{conjecture}\label{4-flow} {\rm (Tutte's 4-flow conjecture for cubic graphs)} For any $3$-graph which has no $P_{10}$-minor, ${\bf 1} \in Int.Cone\,(\M)$. \end{conjecture} % By replacing ``$3$-graph'' by ``$r$-graph'' in Tutte's conjecture, Lov\'asz \cite{Lov3} proposed a very strong conjecture which would imply Conjectures \ref{4CTgeneral} and \ref{4-flow} and the Four-color Theorem. % \begin{conjecture}\label{MnoP10} If a graph contains no $P_{10}$-minor then its perfect matchings form a Hilbert basis. \end{conjecture} % We note that this conjecture would hold true provided both Conjecture \ref{4-flow} and Conjecture \ref{3-graph} were true. Little is known about whether $\M(G)$ forms a Hilbert basis when $G$ contains a $P_{10}$-minor. It is perhaps surprising that the perfect matchings of $P_{10}$ form a Hilbert basis; this fact follows from the observation that the six perfect matchings in $P_{10}$ are linearly independent in $\QQ ^ E$. However, $\M$ is not always a Hilbert basis. % \begin{example} Let $P_{10}+e$ denote the (unique) graph obtained from $P_{10 }$ by joining any two non-adjacent vertices with a new edge $e$. Let $p$ be the weight function which takes the value $0$ on $e$ and takes the value $1$ elsewhere. As $P_{10}+e$ is a brick different from $P_{10}$, it follows that $p \in Cone\,(\M) \cap Lat\,(\M)$. However, $p \not \in Int.Cone\,(\M)$, since this would imply that $P_{10}$ has a 1-factorization. Thus $\M (P_{10}+e)$ is not a Hilbert basis. \end{example} % Clearly, $\M$ is not a Hilbert basis for any graph containing $P_{10}+e$ as a subgraph. \vspace{4mm} Seymour \cite{Sey6} proposed the following analog of the Circuit Double Cover Conjecture. % \begin{conjecture}\label{Fulk} {\rm (Perfect Matching Double Cover Conjecture)} \,For any $r$-graph, ${\bf 2} \in Int.Cone\,(\M)$. \end{conjecture} % The special case $r=3$ of Conjecture \ref{Fulk} was first proposed by Fulkerson \cite{Ful} and is still open. Incidently, Fulkerson's conjecture is equivalent to a strengthening of Jaeger's observation as referred to in the proof of Theorem \ref{ConsecutiveGood}. % \begin{conjecture}\label{FulkEquiv} Any bridgeless graph contains exactly 6 cycles such that any edge is contained in 4 of them. \end{conjecture} % The equivalence of these two conjectures becomes evident for cubic graphs when one considers that the complement of a perfect matching is a cycle. By ``blowing up'' vertices, one can see that Conjecture \ref{FulkEquiv} holds for all graphs provided it holds for cubic graphs. Unlike the case with circuit covers, the Perfect Matching Cover Problem has not been solved for larger uniform vectors $\bf k$, $k>2$. By the fact ${\bf 1} \in Cone\,(\M)$ for any $r$-graph we have that, for any $r$-graph $G$, there exists $k \ge 1$ such that ${\bf k} \in Int.Cone\,(\M)$. However, it is not known whether $k$ can be picked independently of $G$. This gives the following weak Fulkerson-type conjecture. % \begin{conjecture}\label{FulkWeak} There exists $k \ge 2$ such that, for any $r$-graph $G$, ${\bf k} \in Int.Cone\,(\M(G))$. \end{conjecture} % An even weaker conjecture was proposed by B. Jackson \cite{Jac2}. % \begin{conjecture}\label{FulkVeryWeak} There exists $k \ge 2$ such that any $r$-graph contains $k+1$ perfect matchings with empty intersection. \end{conjecture} % A form of Jaeger's 8-flow theorem states that any bridgeless cubic graph $G$ is the union of 3 of its cycles. In fact, one can modify Jaeger's proof to ensure that at least one of the three cycles is a 2-factor of $G$. If one can show that all three cycles can be chosen to be 2-factors then, by taking complements, Conjecture \ref{FulkVeryWeak} will have been proven for $r=3$ and $k=2$. Jackson \cite{Jac2} asked the following question. Can one show that at least two of the three cycles are 2-factors of $G$? Surely, this very special consequence of Fulkerson's conjecture must be true. \section{Circuits, Perfect Matchings and Grafts}\label{CircMat} The vague similarities between circuits and perfect matchings might be explained by considering certain 1-element extensions of graphic matroids. % \begin{definition} Let $A=A(G)$ denote the vertex-edge $\{ 0,1 \}$-valued incidence matrix of a connected graph $G$. Thus the columns of $A$ represent the graphic binary matroid $M(G)$ of rank $|V(G)|-1$ with linear independence over {\rm GF(2)}. Let $T \se V$ and let $\tau$ denote the $\{ 0,1 \}$-valued column vector which is the characteristic vector of $T$. Then $[A \: \tau ]$ represents a binary matroid of rank $|V(G)|-1$ on the ground set $E \cup \{ \tau \}$, which we denote by $G_T$. Following Seymour {\rm \cite{Sey7}}, we call the matroid $G_T$ a {\em graft}. \end{definition} % Grafts are precisely the binary 1-element extensions of graphic matroids. A graft $G_T$ is interesting only when $|T|$ is even, since $\tau$ is otherwise a coloop in $G_T$. If $|T|=0$ then $\tau$ is a loop in $G_T$. If $|T|=2$ then $G_T \cong G+e$ where $e$ is a new edge joining the vertices in $T$. For larger subsets $T$, grafts can be non-graphic and even non-regular. Seymour \cite[p. 339]{Sey7} shows how the matroids $F_7, F_7^*, M^*(K_5), M^*(K_{3,3})$ and $R_{10}$ are all grafts $G_T$, where $G$ has at most 7 vertices. For $T \se V$, a {\em $T$-join} is any subset $S \se E(G)$ such that $T=\{ v\in V\colon v$ is incident with an odd number of non-loop edges in $S\}$ (in some papers, $T$-joins are also required to be acyclic). A {\em $T$-cut} is an edge-cut in $G$ which contains an odd number of vertices of $T$ on each shore. $T$-joins and $T$-cuts are closely related to matchings and have been studied by various authors \cite{Kor,Fra,Lov4,Sch,Seb2,Seb3,Seb4,Seb5,Sey6,Edm2}. One easily checks that, when $|T|$ is even, the cycles of a graft $G_T$ are precisely the cycles of $G$, together with sets of the form $\{\tau\} \cup J$ where $J$ is any $T$-join in $G$. The cocycles of $G_T$ are precisely the cuts of $G$ which are not $T$-cuts, together with the sets of the form $\{\tau\} \cup B$ where $B$ is any $T$-cut in $G$. If $T=V$ and $G$ has a perfect matching, then then the circuits of $G_T$ which contain $\tau$ and which have minimum cardinality are precisely the subsets of the form $\{\tau\} \cup F$ where $F \in \M(G)$. In this way, we obtain a connection between $\C(G_T)$ and $\M(G)$. In particular, the Uniform Perfect Matching Cover Problem for graphs may be posed as a Circuit Cover Problem for grafts. % \begin{example}\label{grafteg} Let $k\ge 1$ and $r \ge 3$. Let $G$ be any $r$-regular graph, and set $T=V$. Consider the weight function $p$ on the graft $G_T$ where $p(\tau)=rk$, and $p(e)=k$ for all $e \in E(G)$. If $p$ is a non-negative linear combination of circuits in $\C(G_T)$ then all circuits having positive coefficients must be of the form $\tau \cup F$, $F \in \M(G)$. This gives us the following facts. \begin{enumerate} \item $p \in Int.Cone\,(\C(G_T))$ if and only if\/ ${\bf k} \in Int.Cone\,(\M(G))$. \item $p \in Cone\,(\C(G_T))$ if and only if\/ ${\bf k} \in Cone\,(\M(G))$. \item $p \in Lat\,(\C(G_T))$ if\/ ${\bf k} \in Lat\,(\M(G))$. \end{enumerate} In particular, $p \in Cone\,(\C(G_T))$ if and only if $G$ is an $r$-graph, and $p \in Lat\,(\C(G_T))$ if either $k$ is even or $G$ has no $P_{10}$-brick. \end{example} % As it is NP-hard to decide whether ${\bf 1} \in Int.Cone\,(\M)$ for $3$-graphs \cite{Hol}, Example \ref{grafteg} implies that determining whether a vector is in the integer cone of circuits is NP-hard for the class of grafts. However, the complexity of the latter problem remains unknown when ``grafts'' is replaced by ``graphs''. Example \ref{grafteg} also serves to connect two of the main conjectures presented earlier in this paper. We have seen that Conjecture \ref{noP10} holds for the class of graphs. We shall see that if this conjecture were to hold true for the class of grafts, then the Four-color Theorem would follow, as well as many of the open problems discussed in Section \ref{MIntCone}. We begin with a curious property of Petersen's graph. In general, if a graft $G_T$ contains a graphic matroid $M(H)$ as a minor, then one cannot deduce that $G$ contains $M(H \bs e)$ as a minor, for some $e \in E(H)$. For example, let $G$ be the polygon of length four, and let $T$ be a pair of non-adjacent vertices in $G$. Then $G_T / \tau \cong H$ where $H$ is the graph consisting of two digons joined at a vertex. However, one easily sees that $H \bs e$ is not a minor of $G$ for any $e \in V(H)$. If $H$ is Petersen's graph, however we have a different story. Note that $P_{10} \bs e$ is independent of $e$ up to isomorphism. % \begin{lemma}\label{P10property} If a graft $G_T$ contains $M(P_{10})$ as a minor, then $G$ contains $P_{10} \bs e$ as a minor. \end{lemma} % \begin{proof} Suppose that $G_T /S \bs R \cong P_{10}$ where $S,R$ are disjoint subsets of $E(G) \cup \{\tau\}$. If $\tau \not \in S \cup R$ then, as in \cite[(10.2)]{Sey5}, $G_T \bs R / S \cong (G \bs R / S)_{T'}$ for some $T' \se V(G \bs R / S)$. Deleting any element from $(G \bs R / S)_{T'}=P_{10}$ yields $P_{10} \bs e$ so, in particular, $P_{10} \bs e \cong (G \bs R / S)_{T'} \bs \tau = G \bs R / S$ and we are done. If $\tau \in R$ then $P_{10} \cong G_T \bs R / S = G \bs (R-\{\tau\}) / S$ is a minor of $G$, and again we are done. Thus we assume that $\tau \in S$. Here we have $G_T \bs R / (S - \{\tau\}) \cong G'_{T'}$ where $G' = G \bs R / (S - \{\tau\})$ and $T'$ is some subset of $V(G')$. It remains to show that $G'$ contains $P_{10} \bs e$ as a minor given that $G'_{T'} / \tau \cong P_{10}$. Suppose that $G'$ contains a bridge $f \in E(G)$. Then, in $G'_{T'}$, either $f$ is a bridge or $f$ is coparallel with $\tau$. In the first case, $f$ is also a bridge of $G'_{T'} / \tau \cong P_{10}$, a contradiction. In the second case we have $P_{10} \cong G'_{T'} / \tau \cong G'_{T'} / f \cong (G' /f )_{T''}$ for some $T'' \se V(G'/f)$. Deleting any element from $(G' /f )_{T''}$ yields $P_{10} \bs e$ so, in particular, $P_{10} \bs e \cong (G' /f )_{T''} \bs \tau = G'/f$. Thus $P_{10} \bs e$ is a minor of $G'$, provided $G'$ contains a bridge. Thus we assume that $G'$ is a 2-edge-connected graph with 15 edges. We claim that $G' = P_{10}$ and hence that $G$ has a $P_{10}$-minor. It is well known that Petersen's graph is the only 2-edge connected graph on at most 15 edges which is not the union of two of its cycles (this property is equivalent to having a 4-{\em nowhere-zero flow}). Suppose that $G' \not\cong P_{10}$. Then $G'$ is the the union of two of its cycles, say $E(G') = C_1 \cup C_2$. Since both the extension and contraction operations preserve cycles in a matroid, both $C_1$ and $C_2$ are cycles in $G'_{T'} / \tau$, and their union is all of $G'_{T'} / \tau \cong P_{10}$. This contradiction establishes our claim and completes the proof. \end{proof} % \begin{theorem}\label{noP104CT} If Conjecture \ref{noP10} holds for grafts then Conjecture \ref{MnoP10} holds for graphs which have no minor isomorphic to $P_{10} \bs e$. \end{theorem} % \begin{proof} Suppose that $\C(G_T)$ forms a Hilbert basis for any graft $G_T$ having no $P_{10}$-minor. By Observation \ref{MReduceTo1}, it suffices to show that ${\bf1} \in Int.Cone\,(\M(G))$ for any $r$-graph $G$ which has no minor isomorphic to $P_{10} \bs e$. Let $(G_T,p)$ be the weighted graft obtained from $G$ as in Example \ref{grafteg} with $k=1$. By {\em 1}.\ of the example, we need to show that $p \in Int.Cone\,(\C(G_T))$. By {\em 2}.\ and {\em 3}., $p \in Cone\,(\C(G_T)) \cap Lat\,(\C(G_T))$, so it suffices to show that $\C (G_T)$ forms a Hilbert basis. This follows from the hypothesis since, by Lemma \ref{P10property}, $G_T$ does not contain a $P_{10}$-minor. \end{proof} % Theorem \ref{noP104CT} demonstrates both the relevance and the ominous difficulty of Conjecture \ref{noP10}. Were it to hold for grafts, the Four-color Theorem and the stronger Conjecture \ref{4CTgeneral} would be immediate corollaries. It would be nice if the forbidden-minor restriction in the conclusion of Theorem \ref{noP104CT} could be be dropped. This would make Tutte's 4-flow Conjecture (\ref{4-flow}) a consequence of Conjecture \ref{noP10}. To drop this restriction only requires an argument for those graphs $G$ which have a $P_{10} \bs e$-minor, but no $P_{10}$-minor. Although we are tantalizingly close to such a result, a new idea may be needed, since there exists a $3$-graph which contains no $P_{10}$-minor although the graft $G_T$ (with $T=V(G)$) does. It remains to address the problem of characterizing the cone, the lattice and the integer cone of circuits in grafts. It seems unlikely that the lattice and the cone have simple descriptions, as grafts have neither the Lattice of Circuits nor the Sums of Circuits property (recall Theorems \ref{Cone}, \ref{Lat}). Indeed, $F_7^* \cong G_T$ where $G = K_{3,2}$, $T=V(G) - {v}$, and $v$ is a vertex of degree 3. The smallest $3$-graph $G$ for which $G_T$ contains a $F_7^*$-minor (where $T=V(G)$) is the triangular prism (the complement of a circuit of length 6). It is interesting that this graph arizes as an anomaly in matching theory, particularly with regard to ear-decompositions (see, for example \cite[(3.2), (3.3)]{Lov1}). The complexity of the cone and the lattice of circuits in grafts is also attested by the effort that was required to characterize the special cases $Cone\,(\M(G))$ and $Lat\,(\M(G))$ (Theorems \ref{MCone} and \ref{MLat}). On the other hand this success in matching theory, and our increasing understanding of $T$-joins \cite{Seb2,Seb3} is encouraging. The circuits of grafts are not impossibly complicated. For example, the lattice is fairly tame in that grafts cannot contain the dual of the projective geometry PG(2,$m$) as a minor, for any $m >2$ (see Example \ref{PG2m}). The cone of circuits is especially worthy of further investigation. Indeed, it is far more important to know the cone than the lattice when investigating whether circuits form a Hilbert basis. It is reasonable to guess that this class of matroids will predominate much of the future research on circuits in matroids. \subsection*{Acknowledgement} I wish to thank Bill Jackson, Andr\'as Seb\H{o}, and Paul Seymour for their valuable suggestions and stimulating discussions. \begin{thebibliography}{99} \bibitem{Als} {\sc B. R. Alspach, L. A. Goddyn and C-Q Zhang,} Graphs with the circuit cover property, {\em Trans. Amer. Math. Soc.}, submitted. \bibitem{Ber} {\sc J. C. Bermond, B. Jackson and F. Jaeger,} Shortest coverings of graphs with cycles, {\em J. Combin. Theory Ser. B} {\bf 35} (1983), 297-308. \bibitem{Bon1} {\sc J. A. Bondy and U. S. R. Murty,} ``Graph Theory with Applications'' North Holland, New York, 1980. \bibitem{Bon2} {\sc J. A. Bondy,} Small cycle double covers of graphs, {\em in} ``Cycles and Rays'', G. Hahn, G. Sabidussi and R. Woodrow, eds., {\em Nato ASI Series C}, vol. 301, Klummer Academic Publishers, Dordrecht/Boston/London, 1990, pp. 21-40. \bibitem{Cat} {\sc P. Catlin,} Double cycle covers and the Petersen graph, {\em J. Graph Theory} {\bf 13} (1989), 465-483. \bibitem{Coo} {\sc W. Cook, J. Fonloupt and A. Schrijver, } An integer analogue of Carath\'eodory's Theorem, {\em J. Combin. Theory Ser. B} {\bf 40} (1986), 63-70. \bibitem{Dez} {\sc M. Deza and M. Laurent,} New results on facets of the cut cone, {em in} ``Integer Programming and Combinatorial Optimization (IPCO) Proceedings'', R. Kannan, W. R. Pulleyblank, Eds., University of Waterloo Press, Waterloo, 1990, pp.171-184. \bibitem{Edm1} {\sc J. Edmonds,} Maximum matching and a polyhedron with (0,1) vertices, {\em J. Res. Nat. Bur. Standards B} {\bf 69} (1965), 125-130. \bibitem{Edm2} {\sc J. Edmonds and E. L. Johnson,} Matching, Euler-Tours, and the Chinese Postman, {\em Math. Programming} {\bf 5} (1973), 88-124. \bibitem{Fan1} {\sc G. Fan,} Covering weighed graphs by even subgraphs, {\em J. Combin. Theory Ser. B} {\bf 49} (1990), 137-141. \bibitem{Fan2} {\sc G. Fan,} Integer flows and cycle covers, {\em J. Combin. Theory Ser. B}, to appear. \bibitem{Fle2} {\sc H. Fleischner and A. Frank,} On circuit decompositions of planar Eulerian graphs, {\em J. Combin. Theory Ser. B} {\bf 50} (1990), 245-253. \bibitem{Fra} {\sc A. Frank,} Conservative weightings and ear-decompositions of graphs. {\em in} ``Integer Programming and Combinatorial Optimization (IPCO) Proceedings'', R. Kannan, W. R. Pulleyblank, Eds., University of Waterloo Press, Waterloo, 1990, pp.217-230. \bibitem{Fu} {\sc X. Fu and L. A. Goddyn,} Matroids with the circuit cover property, in preparation. \bibitem{Ful} {\sc D. R. Fulkerson,} Blocking and antiblocking pairs of polyhedra, {\em Math. Programming} {\bf 1} (1971), 168-194. \bibitem{Gil} {\sc F. R. Giles and W. R. Pulleyblank,} Total dual integrality and integer polyhedra, {\em Linear Algebra and Its Applications} {\bf 25} (1979), 191-196. \bibitem{God1} {\sc L. A. Goddyn,} Cycle double covers of graphs with Hamilton paths, {\em J. Combin. Theory Ser. B} {\bf 46} (1989), 253-254. \bibitem{God2} {\sc L. A. Goddyn,} ``Cycle Covers of Graphs'', Ph. D. Thesis, Dept. of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada, 1988. \bibitem{Hag} {\sc G. Haggard,} Loops in duals, {\em Amer. Math. Monthly} {\bf 87} (1980), 654-656. \bibitem{Hol} {\sc I. Holyer,} The NP-completeness of edge-coloring, {\em SIAM J. Comput.} {\bf 10} (1981), 718-720. \bibitem{Jac1} {\sc B. Jackson,} Shortest circuit covers and postman tours in graphs with a nowhere zero 4-flow, {\em SIAM J. Discrete Math.}, submitted. \bibitem{Jac2} {\sc B. Jackson,} personal communication. \bibitem{Jae1} {\sc F. Jaeger,} Flows and generalized coloring theorems in graphs, {\em J. Combin. Theory Ser. B} {\bf 26} (1979), 205-216. \bibitem{Jae2} {\sc F. Jaeger,} A survey of the cycle double cover conjecture, {\em in} ``Cycles in Graphs'', B. R. Alspach and C. D. Godsil, Eds., Annals Disc. Math., Vol. 27, pp. 1-12, North-Holland, Amsterdam/New York/Oxford, 1985. \bibitem{Jae3} {\sc F. Jaeger and H. Shank,} On the edge-coloring problem for a class of 4-regular maps. {\em J. Graph Theory}, {\bf 5} (1981), 269-275. \bibitem{Jae4} {\sc F. Jaeger and G. Koester,} Vertex signatures and edge-4-colorings of 4-regular plane graphs. {\em J. Graph Theory}, {\bf 14} (1990), 399-403. \bibitem{Jam1} {\sc U. Jamshy and M. Tarsi,} Cycle covering of binary matroids, {\em J. Combin. Theory Ser. B} {\bf 46} (1989), 154-161. \bibitem{Jam2} {\sc U. Jamshy, A. Raspaud and M. Tarsi}, Short circuit covers for regular matroids with a nowhere zero 5-flow, {\em J. Combin. Theory Ser. B} {\bf 42} (1987), 354-357. \bibitem{Jam3} {\sc U. Jamshy and M. Tarsi,} Short cycle covers and the cycle double cover conjecture, {\em J. Combin. Theory Ser. B}, submitted. \bibitem{Karz} {\sc R. Karzanov,} Metrics and undirected cuts, {\em Math. Programming} {\bf 32} (1985), 183-198. \bibitem{Kor} {\sc E. Korach,} ``Packing of T-cuts and Other Aspects of Dual Integrality'', Ph. D. Thesis, Dept. of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada, 1982. \bibitem{Lov1} {\sc L. Lov\'asz,} Matching structure and the matching lattice, {\em J. Combin. Theory Ser. B} {\bf 43} (1987), 187-222. \bibitem{Lov3} {\sc L. Lov\'asz, A. Seb\H{o}, \'A. Seress,} Personal communication, \bibitem{Lov4} {\sc L. Lov\'asz,} 2-matchings and 2-covers of hypergraphs, {\em Acta Math. Acad. Sci. Hung.} {\bf 26} (1975), 433-444. \bibitem{Sch} {\sc A. Schrijver,} On total dual integrality, {\em Linear Algabra and Its Applications} {\bf 38} (1981), 27-32. \bibitem{Seb1} {\sc A. Seb\H{o},} Hilbert bases, Carath\'eodory's theorem and combinatorial optimization, {\em in} ``Integer Programming and Combinatorial Optimization (IPCO) Proceedings'', R. Kannan, W. R. Pulleyblank, Eds., University of Waterloo Press, Waterloo, 1990, pp.431-456. \bibitem{Seb2} {\sc A. Seb\H{o},} Undirected distances and the postman-structure of graphs. {\em J. Combin. Theory Ser. B} {\bf 49} (1990), 10-39. \bibitem{Seb3} {\sc A. Seb\H{o},} Finding the $t$-join structure of graphs. {\em Math. Programming} {\bf 36} (1986), 123-134. \bibitem{Seb4} {\sc A. Seb\H{o},} The Schrijver system of odd join polyhedra, {\em Combinatorica} {\bf 8} (1986), 103-116. \bibitem{Seb5} {\sc A. Seb\H{o},} A quick proof of Seymour's theorem on $t$-joins, {\em Discrete Mathematics} {\bf 64} (1987), 101-103. \bibitem{Sey1} {\sc P. D. Seymour,} Sums of circuits, {\em 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{Sey2} {\sc P. D. Seymour,} Matroids and multicommodity flows, {\em Europ. J. Combinatorics} {\bf 2} (1981), 257-290. \bibitem{Sey3} {\sc P. D. Seymour,} Matroids with the max-flow min-cut property. {\em J. Combin. Theory Ser. B} {\bf 23} (1977), 189-222. \bibitem{Sey5} {\sc P. D. Seymour,} Nowhere-zero 6-flows, {\em J. Combin. Theory Ser. B} {\bf 30} (1981), 130-135. \bibitem{Sey6} {\sc P. D. Seymour,} On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte. {\em Proc. London Math. Soc.} (3) {\bf 38} (1979), 423-460. \bibitem{Sey7} {\sc P. D. Seymour,} Decomposition of regular matroids. {\em J. Combin. Theory Ser. B} {\bf 28} (1980), 305-359. \bibitem{Sey8} {\sc P. D. Seymour,} On Tutte's extension of the Four-Colour Problem {\em J. Combin. Theory Ser. B} {\bf 31} (1981), 82-94. \bibitem{Sze} {\sc G. Szekeres,} Polyhedral decompositions of cubic graphs, {\em J. Austral. Math. Soc.} {\bf 8} (1973), 367-387. \bibitem{Tar1} {\sc M. Tarsi,} Nowhere zero flows and circuit covering in regular matroids, {\em J. Combin. Theory Ser. B} {\bf 39} (1985), 346-352. \bibitem{Tar2} {\sc M. Tarsi,} Semi-duality and the cycle double cover conjecture, {\em J. Combin. Theory Ser. B} {\bf 41} (1986), 332-340. \bibitem{Tut2} {\sc W. T. Tutte,} On the algebraic theory of graph colorings, {\em J. Combin. Theory} {\bf 1} (1966), 15-50. \bibitem{Wel} {\sc D. Welsh,} ``Matroid Theory'', Academic Press, San Francisco, 1976. \bibitem{Zha1} {\sc C-Q Zhang,} Minimum coverings and integer flows, {\em J. Graph Theory}, to appear. \bibitem{Zha2} {\sc C-Q Zhang,} On compatible cycle decompositions of eulerian graphs, preprint. \bibitem{Zha3} {\sc C-Q Zhang,} On even cycle decompositions of eulerian graphs, preprint. \end{thebibliography} \end{document}