Cones, Lattices and Hilbert Bases of Circuits and Perfect Matchings

Luis A. Goddyn ^{∗} Department of Mathematics and Statistics Simon Fraser University

Dec. 6, 1991

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ász, Sebő 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 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 grafts. For example, a possible extension to the class of grafts of the following result would imply the Four-color theorem: The circuits of a graph form a Hilbert basis if and only if the graph has no Petersen minor.

1 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.

∗Supported by the National Sciences and Engineering Research Council operating grant #A-4699 and SFU’s President’s Research Grant #A-2326.

For S ⊆ E we denote by χ^{S} the {0, 1}-characteristic vector of S in ^{E}. For any collection S of such subsets of E, we define the linear hull, cone, lattice and integer cone of S as follows.

Lin.Hull (S) := {∑_{S∈S} α_{S}χ^{S} : α_{S} ∈ }
Cone (S) := {∑_{S∈S} α_{S}χ^{S} : α_{S} ∈ _{≥0}}
Lat (S) := {∑_{S∈S} α_{S}χ^{S} : α_{S} ∈ }
Int.Cone (S) := {∑_{S∈S} α_{S}χ^{S} : α_{S} ∈ _{≥0}}

We have the following four containments.

Int.Cone (S) \begin{matrix}⊂ & Cone (S) & ⊂ \\ ⊂ & Lat (S) & ⊂ \end{matrix} Lin.Hull (S).

Throughout this paper S 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 (S) if and only if there is a list of subsets in S such that each e ∈ E belongs to precisely p(e) members of the the list. Such a list is often called a cover of the weighted set (E, p). If p is the constant unit vector 1, then a cover of (E, p) is a decomposition of E into subsets from S. A cover of (E, 2) is often called a double cover of E.

When S = C, we are in the area of circuit covers and circuit decompositions, where numerous papers [1, 2, 4, 5, 10, 11, 12, 14, 17, 19, 21, 24, 27, 28, 29, 41, 49, 50, 53, 55] 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 S = M, we are studying perfect matching covers of graphs. The case p = 1 is concerned with 1-factorizations of graphs, where we have the classical Four-color Theorem and the stronger 4-flow conjecture of Tutte [51]. For p = 2 we have perfect matching double covers with unsolved conjectures of Fulkerson [15] and Seymour [45].

Although combinatorially less interesting, the cone and the lattice of S 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 [8, 32], whereas it is NP-hard to determine whether 1 belongs to the integer cone of perfect matchings of a cubic graph [20]. The study of the cone and the lattice is further motivated by the formula

Int.Cone (S) ⊆ Cone (S) ∩ Lat (S)  (1)

which provides necessary conditions for a vector p to belong to the integer cone of S.

Understandably, it is of special interest to know when equality holds in (1).

Definition 1.1 A set of vectors S for which equality holds in (1) is called a Hilbert basis.

This concept is closely related to total dual integrality, and has been studied by various authors [16, 6, 35, 36]. In our setting, the 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 3 and 6, respectively.

It must be emphasised that the cone and the lattice of S are worthy of independent study. For example, the characterizations of both the cone [8] and the lattice [32] of perfect matchings are landmarks in graph theory. Both the cone and the lattice of circuits in a graph have simpler descriptions [41] 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 [30].

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 [9] 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 7, we describe another connection between circuits and perfect matchings, which is expressed via certain 1-element extensions of graphic matroids called 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.

We shall assume basic familiarity with graphs and matroids as in [3] and [52]. Thus a bridge or coloop of a matroid M = (E, C) is any element contained in no circuit. Two non-bridge elements are in series or coparallel if no circuit contains exactly one of them. Recall that “coparallel” is an equivalence relation on E. A bond or cocircuit is a minimal subset of E intersecting all bases of M. The 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 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 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 uniform matroid of rank 2 on 4 elements). The cycles of a binary matroid under the symmetric difference operator Δ form a vector space of dimension |E|−rank(M) in GF(2)^{E} called the cycle space of M. Dually, parallel elements, loops and cocycles in M are are defined to be coparallel elements, coloops and cycles in M^{∗}, respectably. A cocycle is sometimes called a 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.

2 The Cone and Lattice of Circuits

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.

Proposition 2.1 For any matroid M = (E, C), Lin.Hull (C) = {p ∈ ^{E} : p(e) = 0 for any bridge e, and p(f) = p(g) for f, g coparallel }.

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, χ^{[e]} ∈ Lin.Hull (C). We use the following observation of Seymour, [42, (3.2)].

Observation 2.2 If M is bridgeless then 1 ∈ Cone (C).

(Here 1 = χ^{E} is the vector of ones.) As M is bridgeless, so is M\[e], hence χ^{E}, χ^{E\[e]} ∈ Cone (C). Subtracting, we have χ^{[e]} ∈ Lin.Hull (C). □

We now examine the cone of circuits. Since no circuit in a matroid meets a bond in exactly one element, any weight vector p ∈ Cone (C) must be balanced. That is, no element in M has more than half the total weight of any bond containing it. Seymour [42] has characterized those matroids for which the cone of circuits is precisely the set of non-negative balanced vectors.

Theorem 2.3 For any matroid M = (E, C), Cone (C) ⊆ {p ∈ _{≥0}^{E} : p(e) ≤ p(B\e) for all e ∈ B, for all bonds B}, with equality if and only if M has no minor isomorphic to any of U_{4}^{2}, M^{∗}(K_{5}), F_{7}^{∗}, or R_{10}. □

(As usual, p(S) denotes ∑_{e∈S} p(e) for any S ⊆ E.) A matroid for which equality holds in Theorem 2.3 is said to have the Sums of Circuits Property. In particular, all graphs have the Sums of Circuits Property [41]. It follows from Theorem 2.3 (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 [42] or [46] for their definitions) do not have this property consider the following four weight vectors p ∈ _{≥0}^{E}.

U_{4}^{2}: p(e_{0}) = 2 for some fixed e_{0} ∈ E and p(e) = 1 for the remaining 3 elements.

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.

F_{7}^{∗}: p(e) = 1 for all elements e in some fixed 4-circuit and p(e) = 2 for the remaining 3 elements.

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.

One easily checks that each of these vectors is balanced. To show that they are not in Cone (C) we use Farkas’ Lemma. That is, we describe a weight vector s ∈ ^{E} which has positive inner product with p, but for which each circuit in the matroid has non-positive weight. For U_{4}^{2} 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 [30] that the membership problem for the cone of bonds in K_{n} is NP-hard. Some work [7] has been done toward finding facets of this cone.

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 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.

Proposition 2.4 For any binary matroid M = (E, C), Lat(C) ⊆ Lin.Hull(C) ∩{p ∈ ^{E} : p(B) is even for all bonds B}, with equality if M has no F_{7}^{∗}-minor.

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χ^{{e}} ∈ Lat (C) for any e ∈ E, since this would imply that the even-valued vector p + χ^{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} ∩ C_{2} = {e}, whereby 2χ^{{e}} = χ^{C_{1}} + χ^{C_{2}} − χ^{C_{1}ΔC_{2}}. The existence of C_{1}, C_{2} follows, for graphs, from Menger’s theorem and, in general, from a theorem of Seymour [43] which states that all binary matroids with no F_{7}^{∗}-minor have the Integer Max-Flow Min-Cut Property. □

A matroid for which equality holds in Proposition 2.4 is said to have the 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ász, Sebő and Seress [33] 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 [42] Seymour defines, for k = 1, 2, 3, the k-sum of two binary matroids M_{1}, M_{2} to be the matroid on E(M_{1})ΔE(M_{2}) whose circuits are all subsets of the form C_{1}ΔC_{2} where C_{i} ∈ C(M_{i}), i = 1, 2. In particular, k = 1 if E(M_{1}) ∩ E(M_{2}) = ∅; k = 2 if E(M_{1}) ∩ E(M_{2}) consists of a single element which is not a loop in each M_{i}; and k = 3 if E(M_{1}) ∩ E(M_{2}) is a circuit of cardinality 3 in each M_{i}.

Definition 2.5 Any matroid which can be obtained from copies of the Fano plane F_{7} via 1-, 2- and 3-sums shall be called a Fano-cycle.

Theorem 2.6 [33] 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. □

Example 2.7 The 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 2.6 asserts that AG(2, 3)^{∗} ≅ 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.

In general, the lattice of circuits in a binary matroid can be arbitrarily “sparse”.

Example 2.8 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) ≅ F_{7}^{∗}. For 0 ≤ k ≤ m, a 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 ∈ 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 ≤ k ≤ m [33].

3 Hilbert Bases of Circuits

The 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 1.1). That is, we would like to determine those matroids M for which (M, p) has a circuit cover for all p ∈ Cone (C) ∩ Lat (C).

The circuits of a matroid do not always form a Hilbert basis.

Example 3.1 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) ∩ Lat (C), by Theorems 2.3 and 2.4. However, p_{10} ∉ Int.Cone (C) since p_{10} − χ^{C} ∉ Cone (C), for all C ∈ C.

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.

Conjecture 3.2 If a matroid contains no P_{10}-minor then C forms a Hilbert basis.

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 6.6 regarding perfect matchings in graphs.

A basic problem with dealing with Conjecture 3.2 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 2.3 and 2.4 that, for such matroids, the cone (lattice) of circuits is precisely the set of balanced (eulerian) weight vectors. In 1979, Seymour verified Conjecture 3.2 for planar graphs by showing that every balanced, eulerian edge-weighted planar graph has a circuit cover. In 1981, Seymour [42] characterized the matroids with the Sums of Circuits Property and, in the same paper, proposed that Conjecture 3.2 holds for such matroids. Recently, Alspach, Goddyn and Zhang [1], shed Seymour’s planarity restriction, and verified Conjecture 3.2 for the class of graphic matroids. Using this result, and Seymour’s matroid decomposition theorems, Fu and Goddyn [14] 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 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.

Theorem 3.3 A matroid has the Circuit Cover Property if and only if it has no minor isomorphic to any of U_{4}^{2}, M^{∗}(K_{5}), F_{7}^{∗}, R_{10}, M(P_{10}). □

Perhaps the most relevant aspect of Theorem 3.3 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 circuit double cover conjecture and Tutte’s 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 3.3 has already been used to extend results involving Even Circuit Decompositions [55] and Compatible Circuit Decompositions of Eulerian graphs [54] from the class of planar graphs to the class of graphs with no K_{5}-minor. We refer the interested reader to [1] for more applications Theorem 3.3.

Little is known about the integer cone of circuits in non-binary matroids. As observed by Sebő [36], 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 < n), and from the following consequence of Edmonds’ matroid intersection theorem.

Theorem 3.4 The bases of any matroid form a Hilbert basis. □

4 Range-Restricted Circuit Covers

Perhaps we are asking too much of matroids when we require their circuits to form Hilbert bases. One way to weaken the Hilbert-basis property is to ask whether some restricted subset of Cone (C) ∩ Lat (C) is contained within Int.Cone (C). Our intention is to determine the point at which non-Hilbert matroids such a M(P_{10}) cease to behave anomalously. In this way we obtain a more sensitive test of “how bad” such anomalous matroids really are.

A notorious problem of this type is the circuit double cover conjecture.

Conjecture 4.1 [48, 41] For any bridgeless graph, 2 ∈ Int.Cone (C).

Of course, the “bridgeless” condition is only there to assure the membership of 2 in the cone of circuits. We refer the interested reader to [24, 17, 18, 50, 29, 4, 5]. The circuit double cover conjecture is perhaps the most interesting of the uniform circuit cover problems, where the weight vector p is required to be constant on E. For integers greater than 2, the uniform circuit cover problem is has been completely solved for a large class of binary matroids, which includes all graphs.

Proposition 4.2 For any binary matroid with no F_{7}^{∗}-minor and for any integer r ≠ 2, r ∈ Int.Cone (C) if and only if r ∈ Cone (C) ∩ Lat (C).

Proof. The “only if” direction is trivial.

Conversely, suppose that r is odd. For r to be in the lattice of circuits of M, it is necessary that all cocircuits in M have even cardinality. That is, M is eulerian, and thus E(M) is the disjoint union of circuits. That is, 1 ∈ Int.Cone (C) and so r ∈ Int.Cone (C). Note that, for odd r, the statement of the theorem holds for all binary matroids.

For even r, we note that r ∈ Cone (C) if and only if the matroid M is bridgeless. Using matroid decompositions, Jamshy and Tarsi [27] showed that r ∈ Int.Cone (C) for any bridgeless binary matroid with no F_{7}^{∗}-minor if and only if the same holds for any bridgeless graph. It suffices to prove that 4, 6 ∈ Int.Cone (C) for any bridgeless graph, since every larger even integer is in the integer cone generated by {4, 6}. Indeed, Jaeger [23] proved the case r = 4 and Fan [11] proved the case r = 6. Both of these results are consequences of Seymour’s 6-flow theorem for bridgeless graphs [44]. □

Incidently, Jamshy and Tarsi [27] also show that if the circuit double cover conjecture is true, then 2 ∈ Int.Cone (C) for any bridgeless binary matroid with no F_{7}^{∗}-minor.

Little is known about uniform circuit covers of general matroids. The obvious necessary conditions are that the matroid be bridgeless and that the vector in question belong to the lattice of circuits. Indeed one might boldly propose the following on the basis of not knowing of a counterexample.

Conjecture 4.3 For any bridgeless matroid and any r ≥ 0, r ∈ Int.Cone (C) if and only if r ∈ Lat (C).

We generalize to non-uniform circuit covers by allowing the range of the weight vector to take two or more fixed values. Our general aim is to classify those ranges (subsets of positive integers) for which we have a nice characterization such as in Proposition 4.2. For sake of brevity, we shall confine most of our discussion to graphic matroids.

Definition 4.4 Let R be a set of positive integers. We say that R is a good range (for the class of graphs) if for any graph G = (V, E) and any weight vector p ∈ R^{E}, p ∈ Int.Cone (C) if and only if p ∈ Cone (C) ∩ Lat (C). A range that is not good is said to be bad.

In view of Theorems 2.3 and 2.4, a range R is good for the class of graphs if every balanced, eulerian weighted graph (G, p) with p ∈ R^{E} has a circuit cover. If R is good then so is any subset of R. Example 3.1 shows that {1, 2} is a bad range for graphs. More bad ranges can be obtained by modifying this example.

Proposition 4.5 If {1, k} ⊆ R, for some k ≥ 2, then R is bad for the class of graphs.

Proof. I thank P. Seymour for the following construction. Let F denote a fixed 1-factor in Petersen’s graph P_{10}. For any k ≥ 2, let P_{10}^{(k)} denote the graph obtained from P_{10} by replacing each edge in F with k − 1 parallel edges. We consider the weight vector p_{10}^{(k)} ∈ {1, k}^{E} which takes the value k on exactly one of the k − 1 edges in each of the five parallel classes defined above, and which takes the value 1 elsewhere. One easily checks that p_{10}^{(k)} is balanced. As any circuit cover of (P_{10}^{(k)}, p_{10}^{(k)}) would have to use k − 2 digons from each parallel class, it follows from Example 3.1 (which is the case k = 2) that p_{10}^{(k)} ∉ Int.Cone (C(P_{10}^{(k)})). □

If some range containing 2 is good, then in particular, the circuit double cover conjecture is true. This gives us a way of strengthening the circuit double cover conjecture. For example, Seymour [42, (16.6)] proposed the following.

Conjecture 4.6 The set of positive even integers is good for the class of graphs.

On the other hand, extending a range does not always affect it goodness.

Proposition 4.7 Let R be a range of even integers and let r ∈ R be such that r ≥ max R/2. Then for any odd integer k > r, R ∪ {k} is good (for the class of graphs) if and only if R is good.

Proof. The “only if” part is trivial. Conversely, suppose that R is good and let p′ ∈ R^{′E} ∩ Cone (C) ∩ Lat (C), where R′ := R ∪ {k}. As p′ is eulerian, the set F of elements having weight k form a cycle. Clearly, p := p′ − (k − r)χ^{F} belongs to R^{E} and is eulerian. We claim that p is balanced. Suppose not. Then for some cocircuit B and some e ∈ B we have p(e) > p(B\{e}) whereas p′(e) ≤ p′(B\{e}). As |F ∩ B| is even, this implies |F ∩ B\{e}| ≥ 2 and e ∉ F. From this we have max R ≥ p(e) > p(B\{e}) ≥ 2r, contradicting the hypothesis and proving the claim. Thus, p ∈ Int.Cone (C). Since χ^{F} ∈ Int.Cone (C), we have p′ ∈ Int.Cone (C). □

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.

Proposition 4.8 For the class of graphs, the range {k, k + 1} is good for all k ≥ 3.

Proof. When k is even, this follows from Propositions 4.2 and 4.7. It suffices to prove the cases k = 3 and k = 5, since 4 ∈ 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 4.2. Jaeger [23] actually proved that any bridgeless graph contains 7 cycles C_{1}, …, C_{7} such that every edge is contained in exactly 4 of them. If p ∈ {3, 4}^{E} ∩ Cone (C(G)) ∩ 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 Δ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\F is contained in exactly 4 of them. As each cycle decomposes into circuits, we have p ∈ Int.Cone (C).

The proof for k = 5 is exactly analogous, using the fact 11 = 5 + 6 and Fan’s observation [11] 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). □

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.

Conjecture 4.9 For some k ≥ 2, the range {k, k + 2} is good for the class of graphs.

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 4.5.

Conjecture 4.10 A range R is good (for the class of graphs) if and only if {1, k} ⊈ R, for all k ≥ 2.

The following table summarizes results regarding good and bad ranges for the class of graphic matroids.

Range  Status  Comments
{2}  Good? Conjecture 4.1
{k}, k ≠ 2  Good  Proposition 4.2
{1, k}, k ≥ 2  Bad  Proposition 4.5
{2, 3}  Good? Equivalent to Conjecture 4.1
{k, k + 1}, k ≥ 3 Good Proposition 4.8
{k, k + 2}, k ≥ 2 Good? Conjecture 4.9
{2k: k ∈ _{≥0}}  Good?? Conjecture 4.6
≥0\{1}  Good???? Conjecture 4.10

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.

Conjecture 4.11 The bonds of any graph form a Hilbert basis.

As M(P_{10}) is not cographic, this conjecture would follow immediately from Conjecture 3.2. However, this has only yet been verified for the class of cographic matroids with no M^{∗}(K_{5})-minor [14]. Again, the major problem is our lack of knowledge about the cone of cuts in graphs [7]. 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 [27]). On the other hand, one cannot use flow theory to prove statements such as Proposition 4.8 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 4.10 cannot be extended to the class of all matroids. Further, it is possible to formulate a common generalization to the bold Conjectures 3.2 and 4.10, 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) ∩ Lat (C)\Int.Cone (C) which is not based on Petersen’s graph (as in Proposition 4.5).

5 Cone and Lattice of Perfect Matchings

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 [8, 32] 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 brick decomposition on the resulting graph as follows. A tight cut is a edge cut which intersects each perfect matching in exactly one edge. For example, any trivial edge cut (that is, an edge cut in which one of its two 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 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ász [32] points out that a list of bricks for G can be obtained in polynomial time.

Theorem 5.1 For any graph G containing an even number of vertices, Lin.Hull (M) = {p ∈ ^{E} : ∃r ∈ , p(B) = r, for all trivial cuts and tight cuts B encountered during a brick decomposition of G}. □

The cone of perfect matchings follows from Edmonds’ well known characterization [8] of the convex hull. An odd cut is an edge cut such that both of its shores contain an odd number of vertices.

Theorem 5.2 For any graph G containing an even number of vertices, Cone (M) = {p ∈ _{≥0}^{E} : ∃r ∈ , p(B) = r, for all trivial cuts B, and p(B′) ≥ r for all odd cuts B′}. □

The lattice of perfect matchings was characterized by Lovász [32]. 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.

Theorem 5.3 For any graph G containing an even number of vertices, Lat (M) = Lin.Hull (M) ∩ {p ∈ ^{E} : p(C_{5}) is even, for every circuit C_{5} of length five contained in any brick of G isomorphic to P_{10}}. □

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 [45]. The necessity of the condition on p(C_{5}) in Theorem 5.3 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.

6 Perfect Matching Covers

Some well-known results and conjectures address the 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) ∩ Lat (M), and that M(G) is said to form a Hilbert basis if this condition is also sufficient.

For uniform vectors k with k > 0, k ∈ Cone (M) if and only if, for some r ≥ 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 [45], we call such graphs 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, 2 ∈ Lat (M). Furthermore, if an r-graph has no P_{10}-brick then 1 ∈ Lat (M). We also note that 1 ∈ 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.

Observation 6.1 Let 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 ∈ G if and only if 1 ∈ Int.Cone (M(H)) for every r-graph H ∈ G.

Proof. The “only if” direction follows immediately from the fact that 1 ∈ Cone (M(H)) ∩ Lat (M(H)) for any r-graph H ∈ G. For the converse, let p ∈ Cone (M(G)) ∩ Lat (M(G)) where G ∈ G. In (G, p), every trivial bond has weight r for some r ∈ _{≥0}. Let H be the r-regular graph obtained from G by replacing each edge e by p(e) parallel edges. As G ∈ G, so is H. Since p ∈ Cone (M(G)), 1 ∈ Cone (M(H)) so H is an r-graph. By hypothesis, 1 ∈ Int.Cone (M(H)). As any perfect matching in H corresponds to one in G, we have p ∈ Int.Cone(M(G)). □

Much of the work that has been done regarding perfect matching covers of r-graphs deals with the case r = 3. Indeed, Seymour [45, (3.5)] has proposed that this is really the only interesting case.

Conjecture 6.2 If r ≥ 4 then any r-graph has a perfect matching whose deletion yields an (r − 1)-graph.

This conjecture is not yet known to be true for any r ≥ 4.

Using the above terminology, we list some known results and conjectures regarding perfect matchings

Theorem 6.3 (Four-color theorem) For any planar 3-graph, 1∈Int.Cone (M). □

I do not know the origin of the following natural generalization, though it is implied by Conjecture (7.3) in [47].

Conjecture 6.4 For any planar r-graph with r ≥ 0, 1 ∈ Int.Cone (M).

The case r = 4 of this conjecture has been has been investigated by Jaeger and others (see [25, 26]), and is known to imply the Four-color Theorem. By Observation 6.1, Conjecture 6.4 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 [51].

Conjecture 6.5 (Tutte’s 4-flow conjecture for cubic graphs) For any 3-graph which has no P_{10}-minor, 1 ∈ Int.Cone (M).

By replacing “3-graph” by “r-graph” in Tutte’s conjecture, Lovász [33] proposed a very strong conjecture which would imply Conjectures 6.4 and 6.5 and the Four-color Theorem.

Conjecture 6.6 If a graph contains no P_{10}-minor then its perfect matchings form a Hilbert basis.

We note that this conjecture would hold true provided both Conjecture 6.5 and Conjecture 6.2 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 ^{E}. However, M is not always a Hilbert basis.

Example 6.7 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 ∈ Cone (M) ∩ Lat (M). However, p ∉ Int.Cone (M), since this would imply that P_{10} has a 1-factorization. Thus M(P_{10} + e) is not a Hilbert basis.

Clearly, M is not a Hilbert basis for any graph containing P_{10} +e as a subgraph.

Seymour [45] proposed the following analog of the Circuit Double Cover Conjecture.

Conjecture 6.8 (Perfect Matching Double Cover Conjecture) For any rgraph, 2 ∈ Int.Cone (M).

The special case r = 3 of Conjecture 6.8 was first proposed by Fulkerson [15] 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 4.8.

Conjecture 6.9 Any bridgeless graph contains exactly 6 cycles such that any edge is contained in 4 of them.

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 6.9 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 k, k > 2. By the fact 1 ∈ Cone (M) for any r-graph we have that, for any r-graph G, there exists k ≥ 1 such that k ∈ Int.Cone (M). However, it is not known whether k can be picked independently of G. This gives the following weak Fulkerson-type conjecture.

Conjecture 6.10 There exists k ≥ 2 such that, for any r-graph G, k ∈ Int.Cone (M(G)).

An even weaker conjecture was proposed by B. Jackson [22].

Conjecture 6.11 There exists k ≥ 2 such that any r-graph contains k + 1 perfect matchings with empty intersection.

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 6.11 will have been proven for r = 3 and k = 2. Jackson [22] 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.

7 Circuits, Perfect Matchings and Grafts

The vague similarities between circuits and perfect matchings might be explained by considering certain 1-element extensions of graphic matroids.

Definition 7.1 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 GF(2). Let T ⊆ V and let τ denote the {0, 1}-valued column vector which is the characteristic vector of T. Then [A τ] represents a binary matroid of rank |V (G)| − 1 on the ground set E ∪ {τ}, which we denote by G_{T}. Following Seymour [46], we call the matroid G_{T} a graft.

Grafts are precisely the binary 1-element extensions of graphic matroids. A graft G_{T} is interesting only when |T | is even, since τ is otherwise a coloop in G_{T}. If |T | = 0 then τ is a loop in G_{T}. If |T | = 2 then G_{T} ≅ 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 [46, p. 339] 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 ⊆ V, a T -join is any subset S ⊆ E(G) such that T = {v ∈ V: 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 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 [31, 13, 34, 35, 37, 38, 39, 40, 45, 9]. 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 {τ} ∪ 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 {τ}∪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 τ and which have minimum cardinality are precisely the subsets of the form {τ} ∪ F where F ∈ 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.

Example 7.2 Let k ≥ 1 and r ≥ 3. Let G be any r-regular graph, and set T = V. Consider the weight function p on the graft G_{T} where p(τ) = rk, and p(e) = k for all e ∈ 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 τ ∪F, F ∈ M(G). This gives us the following facts.

1. p ∈ Int.Cone (C(G_{T})) if and only if k ∈ Int.Cone (M(G)).

2. p ∈ Cone (C(G_{T})) if and only if k ∈ Cone (M(G)).

3. p ∈ Lat (C(G_{T})) if k ∈ Lat (M(G)).

In particular, p ∈ Cone (C(G_{T})) if and only if G is an r-graph, and p ∈ Lat (C(G_{T})) if either k is even or G has no P_{10}-brick.

As it is NP-hard to decide whether 1 ∈ Int.Cone (M) for 3-graphs [20], Example 7.2 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 7.2 also serves to connect two of the main conjectures presented earlier in this paper. We have seen that Conjecture 3.2 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 6. 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\e) as a minor, for some e ∈ 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} /τ ≅ H where H is the graph consisting of two digons joined at a vertex. However, one easily sees that H\e is not a minor of G for any e ∈ V (H).

If H is Petersen’s graph, however we have a different story. Note that P_{10}\e is independent of e up to isomorphism.

Lemma 7.3 If a graft G_{T} contains M(P_{10}) as a minor, then G contains P_{10}\e as a minor.

Proof. Suppose that G_{T} /S\R ≅ P_{10} where S, R are disjoint subsets of E(G)∪ {τ}. If τ ∉ S ∪ R then, as in [44, (10.2)], G_{T} \R/S ≅ (G\R/S)_{T′} for some T′ ⊆ V (G\R/S). Deleting any element from (G\R/S)_{T′} = P_{10} yields P_{10}\e so, in particular, P_{10}\e ≅ (G\R/S)_{T′}\τ = G\R/S and we are done. If τ ∈ R then P_{10} ≅ G_{T} \R/S = G\(R − {τ})/S is a minor of G, and again we are done. Thus we assume that τ ∈ S. Here we have G_{T} \R/(S − {τ}) ≅ G′_{T′} where G′ = G\R/(S − {τ}) and T′ is some subset of V (G′).

It remains to show that G′ contains P_{10}\e as a minor given that G′_{T′}/τ ≅ P_{10}. Suppose that G′ contains a bridge f ∈ E(G). Then, in G′_{T′}, either f is a bridge or f is coparallel with τ. In the first case, f is also a bridge of G′_{T′}/τ ≅ P_{10}, a contradiction. In the second case we have P_{10} ≅ G′_{T′}/τ ≅ G′_{T′}/f ≅ (G′/f)_{T′′} for some T′′ ⊆ V (G′/f). Deleting any element from (G′/f)_{T′′} yields P_{10}\e so, in particular, P_{10}\e ≅ (G′/f)_{T′′}\τ = G′/f. Thus P_{10}\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-nowhere-zero flow). Suppose that G′ ≅ P̸_{10}. Then G′ is the the union of two of its cycles, say E(G′) = C_{1} ∪ 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′}/τ, and their union is all of G′_{T′}/τ ≅ P_{10}. This contradiction establishes our claim and completes the proof. □

Theorem 7.4 If Conjecture 3.2 holds for grafts then Conjecture 6.6 holds for graphs which have no minor isomorphic to P_{10}\e.

Proof. Suppose that C(G_{T}) forms a Hilbert basis for any graft G_{T} having no P_{10}-minor. By Observation 6.1, it suffices to show that 1 ∈ Int.Cone (M(G)) for any r-graph G which has no minor isomorphic to P_{10}\e. Let (G_{T} , p) be the weighted graft obtained from G as in Example 7.2 with k = 1. By 1. of the example, we need to show that p ∈ Int.Cone (C(G_{T})). By 2. and 3., p ∈ Cone (C(G_{T})) ∩ 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 7.3, G_{T} does not contain a P_{10}-minor. □

Theorem 7.4 demonstrates both the relevance and the ominous difficulty of Conjecture 3.2. Were it to hold for grafts, the Four-color Theorem and the stronger Conjecture 6.4 would be immediate corollaries. It would be nice if the forbidden-minor restriction in the conclusion of Theorem 7.4 could be be dropped. This would make Tutte’s 4-flow Conjecture (6.5) a consequence of Conjecture 3.2. To drop this restriction only requires an argument for those graphs G which have a P_{10}\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 2.3, 2.4). Indeed, F_{7}^{∗} ≅ 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 [32, (3.2), (3.3)]). 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 5.2 and 5.3).

On the other hand this success in matching theory, and our increasing understanding of T -joins [37, 38] 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 2.8). 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.

Acknowledgement

I wish to thank Bill Jackson, András Sebő, and Paul Seymour for their valuable suggestions and stimulating discussions.

References

[1] B. R. Alspach, L. A. Goddyn and C-Q Zhang, Graphs with the circuit cover property, Trans. Amer. Math. Soc., submitted.

[2] J. C. Bermond, B. Jackson and F. Jaeger, Shortest coverings of graphs with cycles, J. Combin. Theory Ser. B 35 (1983), 297-308.

[3] J. A. Bondy and U. S. R. Murty, “Graph Theory with Applications” North Holland, New York, 1980.

[4] J. A. Bondy, Small cycle double covers of graphs, in “Cycles and Rays”, G. Hahn, G. Sabidussi and R. Woodrow, eds., Nato ASI Series C, vol. 301, Klummer Academic Publishers, Dordrecht/Boston/London, 1990, pp. 21-40.

[5] P. Catlin, Double cycle covers and the Petersen graph, J. Graph Theory 13 (1989), 465-483.

[6] W. Cook, J. Fonloupt and A. Schrijver, An integer analogue of Carathéodory’s Theorem, J. Combin. Theory Ser. B 40 (1986), 63-70.

[7] 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.

[8] J. Edmonds, Maximum matching and a polyhedron with (0,1) vertices, J. Res. Nat. Bur. Standards B 69 (1965), 125-130.

[9] J. Edmonds and E. L. Johnson, Matching, Euler-Tours, and the Chinese Postman, Math. Programming 5 (1973), 88-124.

[10] G. Fan, Covering weighed graphs by even subgraphs, J. Combin. Theory Ser. B 49 (1990), 137-141.

[11] G. Fan, Integer flows and cycle covers, J. Combin. Theory Ser. B, to appear.

[12] H. Fleischner and A. Frank, On circuit decompositions of planar Eulerian graphs, J. Combin. Theory Ser. B 50 (1990), 245-253.

[13] A. Frank, Conservative weightings and ear-decompositions of graphs. in “Integer Programming and Combinatorial Optimization (IPCO) Proceedings”, R. Kannan, W. R. Pulleyblank, Eds., University of Waterloo Press, Waterloo, 1990, pp.217-230.

[14] X. Fu and L. A. Goddyn, Matroids with the circuit cover property, in preparation.

[15] D. R. Fulkerson, Blocking and antiblocking pairs of polyhedra, Math. Programming 1 (1971), 168-194.

[16] F. R. Giles and W. R. Pulleyblank, Total dual integrality and integer polyhedra, Linear Algebra and Its Applications 25 (1979), 191-196.

[17] L. A. Goddyn, Cycle double covers of graphs with Hamilton paths, J. Combin. Theory Ser. B 46 (1989), 253-254.

[18] L. A. Goddyn, “Cycle Covers of Graphs”, Ph. D. Thesis, Dept. of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada, 1988.

[19] G. Haggard, Loops in duals, Amer. Math. Monthly 87 (1980), 654-656.

[20] I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10 (1981), 718-720.

[21] B. Jackson, Shortest circuit covers and postman tours in graphs with a nowhere zero 4-flow, SIAM J. Discrete Math., submitted.

[22] B. Jackson, personal communication.

[23] F. Jaeger, Flows and generalized coloring theorems in graphs, J. Combin. Theory Ser. B 26 (1979), 205-216.

[24] F. Jaeger, A survey of the cycle double cover conjecture, 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.

[25] F. Jaeger and H. Shank, On the edge-coloring problem for a class of 4-regular maps. J. Graph Theory, 5 (1981), 269-275.

[26] F. Jaeger and G. Koester, Vertex signatures and edge-4-colorings of 4-regular plane graphs. J. Graph Theory, 14 (1990), 399-403.

[27] U. Jamshy and M. Tarsi, Cycle covering of binary matroids, J. Combin. Theory Ser. B 46 (1989), 154-161.

[28] U. Jamshy, A. Raspaud and M. Tarsi, Short circuit covers for regular matroids with a nowhere zero 5-flow, J. Combin. Theory Ser. B 42 (1987), 354-357.

[29] U. Jamshy and M. Tarsi, Short cycle covers and the cycle double cover conjecture, J. Combin. Theory Ser. B, submitted.

[30] R. Karzanov, Metrics and undirected cuts, Math. Programming 32 (1985), 183-198.

[31] 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.

[32] L. Lovász, Matching structure and the matching lattice, J. Combin. Theory Ser. B 43 (1987), 187-222.

[33] L. Lovász, A. Sebő, Á. Seress, Personal communication,

[34] L. Lovász, 2-matchings and 2-covers of hypergraphs, Acta Math. Acad. Sci. Hung. 26 (1975), 433-444.

[35] A. Schrijver, On total dual integrality, Linear Algabra and Its Applications 38 (1981), 27-32.

[36] A. Sebő, Hilbert bases, Carathéodory’s theorem and combinatorial optimization, in “Integer Programming and Combinatorial Optimization (IPCO) Proceedings”, R. Kannan, W. R. Pulleyblank, Eds., University of Waterloo Press, Waterloo, 1990, pp.431-456.

[37] A. Sebő, Undirected distances and the postman-structure of graphs. J. Combin. Theory Ser. B 49 (1990), 10-39.

[38] A. Sebő, Finding the t-join structure of graphs. Math. Programming 36 (1986), 123-134.

[39] A. Sebő, The Schrijver system of odd join polyhedra, Combinatorica 8 (1986), 103-116.

[40] A. Sebő, A quick proof of Seymour’s theorem on t-joins, Discrete Mathematics 64 (1987), 101-103.

[41] P. D. Seymour, Sums of circuits, in “Graph Theory and Related Topics”, J. A. Bondy and U. S. R. Murty, Eds., pp. 341-355, Academic Press, New York/Berlin, 1979.

[42] P. D. Seymour, Matroids and multicommodity flows, Europ. J. Combinatorics 2 (1981), 257-290.

[43] P. D. Seymour, Matroids with the max-flow min-cut property. J. Combin. Theory Ser. B 23 (1977), 189-222.

[44] P. D. Seymour, Nowhere-zero 6-flows, J. Combin. Theory Ser. B 30 (1981), 130-135.

[45] P. D. Seymour, On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte. Proc. London Math. Soc. (3) 38 (1979), 423-460.

[46] P. D. Seymour, Decomposition of regular matroids. J. Combin. Theory Ser. B 28 (1980), 305-359.

[47] P. D. Seymour, On Tutte’s extension of the Four-Colour Problem J. Combin. Theory Ser. B 31 (1981), 82-94.

[48] G. Szekeres, Polyhedral decompositions of cubic graphs, J. Austral. Math. Soc. 8 (1973), 367-387.

[49] M. Tarsi, Nowhere zero flows and circuit covering in regular matroids, J. Combin. Theory Ser. B 39 (1985), 346-352.

[50] M. Tarsi, Semi-duality and the cycle double cover conjecture, J. Combin. Theory Ser. B 41 (1986), 332-340.

[51] W. T. Tutte, On the algebraic theory of graph colorings, J. Combin. Theory 1 (1966), 15-50.

[52] D. Welsh, “Matroid Theory”, Academic Press, San Francisco, 1976.

[53] C-Q Zhang, Minimum coverings and integer flows, J. Graph Theory, to appear.

[54] C-Q Zhang, On compatible cycle decompositions of eulerian graphs, preprint.

[55] C-Q Zhang, On even cycle decompositions of eulerian graphs, preprint.