Matroids with the Circuit Cover Property

Xudong Fu

Department of Computer Science University of Toronto Toronto, ON

        fu@theory.utoronto.ca

Luis A. Goddyn^{∗}

Department of Mathematics and Statistics Simon Fraser University Burnaby, BC

                                               goddyn@math.sfu.ca

March 23, 1995

Abstract

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

Keywords: matroids, circuit covers, cycle covers, Hilbert base, sums of circuits, bond covers, cut covers

AMS Classifications: 05B35, ( 05C38, 05C70, 90C10 )

∗Support from the National Sciences and Engineering Research Council is gratefully acknowledged.

1 Introduction

In this paper, we verify a conjecture of P. Seymour [13, (16.5)] which regards covering the elements of a binary matroid with circuits. We give a forbidden-minor characterization of those matroids which have a certain “Circuit Cover Property”. The special case regarding graphic matroids, solved in [1], has had a number of implications for problems such as the Cycle Double Cover Conjecture, the Chinese Postman Problem, and Eulerian Decompositions [3, 6, 8, 17, 18, 19, 20]. We extend this result to the class of binary matroids by applying some fairly standard matroid decomposition techniques. This strategy involves verifying the conjecture for certain small matroids, and demonstrating that the relevant properties are preserved under matroid sums. The most involved single step (Lemma 5.4) requires checking that the bonds of a particular graph of order eight satisfy the conjecture. We assume familiarity with basic matroid theory such as in [15].

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

1.1 p(e) ∈ _{+} 1.2 p(B) ≡ 0 (mod 2) 1.3 If e ∈ B, then p(e) ≤ p(B − e).

(Here, _{+} denotes the non-negative integers. For S⊆E we write p(S) for ∑_{e∈S} p(e), and S −e for S −{e}.) The necessity of these conditions follows from the fact that, in a binary matroid, any circuit meets each cocircuit in an even number of elements. We say that (M, p) is eulerian if it satisfies 1.2 for all cocircuits B, (M, p) is balanced if it satisfies 1.3 for all pairs (B, e), and (M, p) is admissible if it satisfies 1.1, 1.2 and 1.3 for all pairs (B, e). A binary matroid M has the circuit cover property if (M, p) has a circuit cover for every admissible weight function p.

1.4 Theorem (Main Theorem) Let M be a binary matroid. Then M has the circuit cover property if and only if M has no minor isomorphic to any of F_{7}^{∗}, R_{10}, M^{∗}(K_{5}) or M(P_{10}).

We describe here these matroids and some terminology. If M is a matroid then M^{∗} denotes its dual. For any graph G = (V, E), M(G) denotes the matroid on E(G) whose circuits are the edge sets of polygons (simple closed walks) in G. The dual matroid M^{∗}(G) has as circuits the edge sets of bonds (minimal edge cuts) in G. Matroids of the form M(G) (M^{∗}(G)) for some graph G are said to be graphic (cographic). The complete graph on n vertices is denoted K_{n}, complete bipartite graphs are denoted with K_{s,t}, and Petersen’s graph is denoted P_{10}. The Wagner graph V_{8} (sometimes called the Möebius ladder of order eight) is obtained from the polygon v_{0}v_{1} … v_{7}v_{0} by adding four new edges of the form v_{i}v_{i+4}. The Fano matroid F_{7} is the binary matroid represented over GF(2) by the seven non-zero binary 3-tuples. Thus the circuits of F_{7}^{∗} are precisely the 4-arcs of the projective plane PG(2,2). We denote by R_{10} the unique 10-element regular matroid which is neither graphic nor cographic (see [13]). This matroid is conveniently represented by the edges of K_{5}, where S⊆E(K_{5}) is a circuit of R_{10} if and only if S induces in K_{5} either a polygon of length four or the complement of a polygon of length four.

As graphic matroids have no minors isomorphic to F_{7}^{∗}, R_{10} or M^{∗}(K_{5}), the main theorem extends (and relies on) the following result which was proved in [1].

1.5 Corollary A graphic matroid M(G) has the circuit cover property if and only if G has no subgraph contractible to P_{10}.

□

A circuit cover of a weighted cographic matroid (M^{∗}(G), p) corresponds to a covering of E(G) with bonds. Thus a graph G has the bond cover property if (G, p) has a bond cover for every p : E(G) → _{+} such that (the edge set of) every polygon has even total weight and no edge has more than half the total weight of any polygon containing it. As none of F_{7}^{∗}, R_{10} and M(P_{10}) is cographic, Theorem 1.4 implies the following.

1.6 Corollary A graph has the bond cover property if and only if it has no subgraph contractible to K_{5}.

□

2 Bad Minors

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

2.1 Lemma None of F_{7}^{∗}, R_{10}, M^{∗}(K_{5}) and M(P_{10}) has the circuit cover property.

Proof. For each of these matroids we describe a circuit-minimal weighting p.

F_{7}^{∗}: Let C be a fixed 4-circuit of F_{7}^{∗}. Put p(e) = 1 for all e ∈ C, and p(e) = 2 for the remaining 3 elements in F_{7}^{∗}.

R_{10}: Let S be any 3-subset of elements not contained in any 4-circuit of R_{10}. Put p(e) = 3 for all e ∈ S, and p(e) = 1 for the remaining 7 elements in R_{10}.

M^{∗}(K_{5}): Let T be six edges in K_{5} which induce a subgraph isomorphic with K_{2,3}. Put p(e) = 1 for all e ∈ T, and p(e) = 2 for the remaining four edges in K_{5}.

M(P_{10}): Let F be the edges in a fixed 1-factor of P_{10}. Put p(e) = 2 for all e ∈ F, and p(e) = 1 for the remaining 10 edges in P_{10}.

It is routine to verify that all four weighted matroids are circuit minimal. □

2.2 Remark There is an easy way to check that the first three of the above four weighted matroids (M, p) have no circuit cover. In each case, we define a function s on E(M) via

s(e) = \{ \begin{matrix}1 & if p(e) = 1, \\ −1 & otherwise. \end{matrix}

One easily checks that s has negative inner product with p whereas s(C) is non-negative for each circuit C of M. By Farkas’ lemma p cannot be expressed as a linear combination of the vectors {χ^{C} : C is a circuit in M} with nonnegative coefficients, whereas a circuit cover corresponds to such a linear combination with nonnegative integer coefficients. This argument fails for M(P_{10}) since the weighting described above is a nonnegative half-integral combination of circuits.

A cycle in a binary matroid M is any disjoint union of circuits in M. The cycles of M form a subspace of GF(2)^{E(M)}, called the cycle space, under the symmetric difference operator “△”. Clearly (M, p) has a cycle cover if and only if it has a circuit cover. The terms cocycle and cocycle space are defined analogously. If (M, p) is a weighted matroid, then any minor M′ of M, induces a weighted minor (M′, p _{E(M′)}), which we often denote by (M′, p) where no confusion results. As a further abuse, we may write e ∈ M and p : M → instead of e ∈ E(M) and p : E(M) → . We say that a cocycle D is balanced in (M, p) if p(e) ≤ p(D − e) for all e ∈ D.

2.3 Lemma If a binary matroid M has the circuit cover property then any minor of M also has the circuit cover property.

Proof. Assume M has the circuit cover property and let f ∈ M. We show that both M\f and M/f have the circuit cover property. First, suppose that (M\f, p) is admissible. We extend the definition of p to M by setting p(f) := 0. Then (M, p) is clearly admissible and thus has a circuit cover (C_{i}). Since p(f) = 0, (C_{i}) is also a circuit cover of (M\f), so M\f has the circuit cover property.

Now suppose that (M/f, p) is admissible. We may assume that f is contained in some cocircuit of M, since otherwise f is a loop and M/f = M\f. We extend p to E(M) by setting

p(f) := min{p(B − f) : B is a cocircuit in M containing f}.

Let B_{0} be a cocircuit in M achieving this minimum. We claim that (M, p) is admissible.

Let B be any cocircuit in M. We may assume f ∈ B, for otherwise B is a cocircuit in M/f, whence 1.2 and 1.3 hold for B. Since B△B_{0} is a cocycle in M not containing f, B△B_{0} is a cocycle in M/f, so its total weight is even. We have, modulo 2, that p(B△B_{0}) ≡ p(B) + p(B_{0}), so p(B) ≡ p(B_{0}) = 2p(f) ≡ 0. Thus (M, p) is eulerian. Let e ∈ B. If e ∈ B ∩ B_{0}, then we have p(e) ≤ p(B_{0} − e) ≤ p(B − e), by the choice of B_{0}. If e ∈ B − B_{0}, then B△B_{0} is a cocycle of M/f containing e, and thus p(e) ≤ p(B△B_{0} − e) ≤ p(B − f) + p(B_{0} − f) − p(e) = p(B − f) + p(f) − p(e) = p(B − e). Hence (M, p) is balanced, and thus admissible. Let (C_{i}) be a circuit cover of (M, p). Each C_{i} − {f} is a cycle in M/f. Thus (C_{i} − {f}) is a cycle cover of (M/f, p), and M/f has the circuit cover property.

□

3 Decomposition Theorems

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

Let M_{1}, M_{2} be binary matroids whose ground sets E_{1}, E_{2} may intersect. We denote by M_{1}△M_{2} the matroid on E_{1}△E_{2} whose cycles are all subsets of E_{1}△E_{2} of the form C_{1}△C_{2}, where C_{i} is a cycle in M_{i}, i = 1, 2. In particular, we define the following three matroid sums.

1. M_{1}△M_{2} is a 1-sum of M_{1} and M_{2} if E_{1} ∩ E_{2} = ∅.

2. M_{1}△M_{2} is a 2-sum of M_{1} and M_{2} if E_{1} ∩ E_{2} = {f}, where f is neither a loop nor a coloop of M_{1} or M_{2}.

3. M_{1}△M_{2} is a Y-sum of M_{1} and M_{2} if |E_{1} ∩ E_{2}| = 3, where Z := E_{1} ∩ E_{2} is a cocircuit of size 3 in both M_{1} and M_{2}, and Z contains no circuit of either M_{1} or M_{2}.

A matroid sum of M_{1} and M_{2} is said to be proper if it contains proper minors isomorphic with M_{1} and M_{2}. If M and M′ are matroids, then an M′ minor of M is a minor of M isomorphic with M′. We state two classical decomposition results. The first is due to Seymour (see [12, (11.3.16) and (11.3.19)]).

3.1 Lemma Every binary matroid with no F_{7}^{∗} minor may be constructed recursively by means of proper 1-sums, 2-sums and Y-sums, starting from copies of F_{7}, R_{10}, graphic, and cographic matroids. □

We note that a Y-sum can not involve a copy of either R_{10} or F_{7} since neither matroid has a cocircuit of cardinality three. The second decomposition result is essentially due to Wagner [16]. It is stated in dual form in [14, (10.5.15)]. A matroid is planar if it is both graphic and cographic.

3.2 Lemma Every cographic matroid with no M^{∗}(K_{5}) minor may be constructed recursively by means of proper 1-sums, 2-sums and Y-sums starting from copies of M^{∗}(K_{3,3}), M^{∗}(V_{8}), and planar matroids. □

Seymour [12, (6.10)] observes that M^{∗}(K_{3,3}), which is a minor of M^{∗}(V_{8}), may be dropped from the list of starting minors provided we do not require the sums to be proper. Indeed the following is easy to check.

3.3 Proposition Every proper minor of M^{∗}(V_{8}) is either planar or is a Y-sum of two planar matroids. □

3.4 Lemma Every binary matroid with no F_{7}^{∗}, R_{10}, M^{∗}(K_{5}) or M(P_{10}) minor may be constructed recursively by means of 1-sums, 2-sums and Y-sums starting from copies of F_{7}, M^{∗}(V_{8}), and graphic matroids containing no M(P_{10}) minor.

Proof. Let M be a binary matroid with no minor isomorphic to F_{7}^{∗}, R_{10}, M^{∗}(K_{5}) or M(P_{10}). We decompose M via Lemma 3.1, obtaining a list L of matroids. Since the sums in Lemma 3.1 are proper, each matroid in L is one of following.

• F_{7}

• cographic, with no M^{∗}(K_{5})-minor

• graphic, with no M(P_{10})-minor.

We have used here that M(P_{10}) is not cographic and M^{∗}(K_{5}) is not graphic. We further decompose each cographic matroid in L by applying Lemma 3.2. Finally we apply Proposition 3.3 to eliminate copies of M^{∗}(K_{3,3}) and obtain our final decomposition. As planar matroids are graphic and have no M(P_{10})-minor, each matroid in the final decomposition is of the required type. □

4 Preservation under sums

We show here that the circuit cover property is preserved by 1-sums, 2-sums and Y-sums. We note that the operation that is dual to the Y-sum, called △-sum by Truemper [14] and used by Seymour [12, 13], does not preserve the circuit cover property. For example, F_{7} has the circuit cover property (Lemma 5.3), whereas any △-sum of two copies of F_{7} has an F_{7}^{∗} minor. However, the proof of Lemma 4.2 below has a similar flavour to (7.2) and (7.3) of [13]. We first state an observation of Seymour [12, p. 319].

4.1 Lemma Let M be a 1-sum, 2-sum or Y-sum of binary matroids M_{1} and M_{2}. Then the cocycles of M are precisely the subsets of E_{1}△E_{2} of the form B_{1}△B_{2}, where B_{i} is a cocycle of M_{i}, i = 1, 2.

□

4.2 Lemma Suppose M is a 1-sum, 2-sum or Y-sum of binary matroids M_{1} and M_{2}, where both M_{1} and M_{2} have the circuit cover property. Then M has the circuit cover property.

Proof. We omit the 1-sum case as its proof is almost trivial. Let M be a 2-sum of M_{1} and M_{2} where M_{1}∩M_{2} = {f} and where each M_{i} has the circuit cover property. We proceed by constructing an admissible weighting p_{i} of M_{i}, i = 1, 2. Let i ∈ {1, 2}. Since f is not a loop in M_{i}, some cocircuit in M_{i} contains f. We choose such a cocircuit D_{i} which minimizes p(D_{i} − {f}), and let n_{i} denote this minimum. We assume without loss of generality that n_{1} ≤ n_{2}. For i = 1, 2 we define p_{i} : M_{i} → by

p_{i}(e) = \{ \begin{matrix}n_{1} & if e = f \\ p(e) & otherwise. \end{matrix}

From this definition we immediately have

p_{1}(e) ≤ p_{1}(D_{1} − {e}), for all e ∈ D_{1}.  (1)

We now show that each (M_{i}, p_{i}) is admissible. Let i ∈ {1, 2}. By Lemma 4.1 each cocircuit D in M_{i} not containing f is a cocycle in M. Since (M, p) is admissible and since p and p_{i} coincide on D, D is balanced and eulerian in (M_{i}, p_{i}). We assume now that D is a cocircuit in M_{i} containing f. By Lemma 4.1, D△D_{1} is a cocycle of M, so D△D_{1} is balanced and has even total weight in (M, p). Since p_{1}(D_{1}) is even and p(D△D_{1}) ≡ p_{i}(D) + p_{1}(D_{1}) (mod 2), it follows that p_{i}(D) is even. Let e ∈ D. If e ∈ D ∩ D_{1}, then by (1) and the choice of D_{1}

p_{i}(e) = p_{1}(e) ≤ p_{1}(D_{1} − {e}) ≤ p_{i}(D − {e}).

If e ∈ D − D_{1}, then e ∈ D_{1}△D and

p_{i}(e) = p(e) ≤ p(D△D_{1}−{e}) ≤ p(D−{f})+p(D_{1}−{f})−p(e) = p_{i}(D−{f})+p_{i}(f)−p_{i}(e) = p_{i}(D−{e}).

Thus (M_{i}, p_{i}) is admissible and, by hypothesis, has a circuit cover L_{i}, i = 1, 2. We form a cycle cover of (M, p) by “pairing off” the circuits in L_{1} which contain f with those in L_{2} which contain f. More precisely, we let L′_{i} be the sublist of L_{i} consisting of the n_{1} circuits which contain f, i = 1, 2, and let g : L′_{1} → L′_{2} be any bijection. The list (L_{1} − L′_{1}) ∪ (L_{2} − L′_{2}) ∪ (C△g(C) : C ∈ L′_{1}) is a cycle cover of (M, p). Thus M has the circuit cover property.

We assume now that M is a Y-sum of M_{1} and M_{2} where each M_{i} has the circuit cover property. Let M_{1} ∩ M_{2} = Z = {e_{1}, e_{2}, e_{3}} where Z is a cocircuit in both M_{1} and M_{2}. Let p be an admissible weighting of M. Let i ∈ {1, 2} and j ∈ {1, 2, 3}. Since Z contains no circuit of M_{i}, e_{j} is not a loop in M_{i}/(Z − {e_{j}}) and thus there is a cocircuit D in M_{i} such that D ∩ Z = {e_{j}}. Let d_{ij} be the minimum of p(D − e_{j}) over all such cocircuits D, and let D_{ij} be a cocircuit attaining this minimum. For j = 1, 2, 3, we define n_{j} := min{d_{1j}, d_{2j}}, and let D_{j} be a cocircuit in {D_{1j}, D_{2j}} with p(D_{j} − p) = n_{j}. Let n := n_{1} + n_{2} + n_{3}. For i = 1, 2 we define the weighting p_{i} : M_{i} → by

p_{i}(e) = \{ \begin{matrix}min\{n_{j}, n − n_{j}\} & if e = e_{j}, for some j ∈ \{1, 2, 3\} \\ p(e) & otherwise. \end{matrix}

We now show each (M_{i}, p_{i}) is admissible. Let i ∈ {1, 2}. Let D be any cocircuit of M_{i}. We have four cases depending on |Z ∩ D|.

Case |Z ∩ D| = 3: Here D = Z. By construction of p_{i}, Z is balanced in (M_{i}, p_{i}). Its weight, p_{i}(Z), equals either n or 2n − 2n_{j} for some j ∈ {1, 2, 3}, and thus Z is eulerian provided that n is even. By Lemma 4.1, D_{1}△D_{2}△D_{3}△Z is a cocycle of M, and so n = n_{1} + n_{2} + n_{3} = p(D_{1}) + p(D_{2}) + p(D_{3}) − p(Z) ≡ p(D_{1}△D_{2}△D_{3}△Z) ≡ 0 (mod 2), as required.

Case |Z ∩ D| = 0: Here Z is a cocycle of M, and is thus balanced and eulerian in (M_{i}, p_{i}).

Case |Z∩D| = 1: By symmetry we may assume Z∩D = {e_{1}}. If p_{i}(e_{1}) = n_{1}, then by the same argument as in the 2-sum case, D is eulerian and balanced in (M_{i}, p_{i}). We assume that p_{i}(e_{1}) = n_{2} + n_{3} < n_{1}, p_{i}(e_{2}) = n_{2}, and p_{i}(e_{3}) = n_{3}. We claim that neither M_{1} nor M_{2} contains both D_{2} and D_{3}. Otherwise, D_{2}△D_{3}△D would be a cocycle in M_{1} or M_{2} such that (D_{2}△D_{3}△D) ∩ Z = {e_{1}}. This cocycle contains a cocircuit D′_{1} with D′_{1} ∩ Z = {e_{1}}. For k = 1, 2 we have

p_{k}(D′_{1} − {e_{1}}) ≤ p_{k}(D_{2} − {e_{2}}) + p_{k}(D_{3} − {e_{3}}) = n_{2} + n_{3} < n_{1}

contradicting the minimality of n_{1} and proving our claim. Hence exactly one of D_{2}, D_{3}, say D_{2}, belongs to M_{i}. Now D′_{3} := D_{2}△D△Z is a cocycle of M_{i} with D′_{3} ∩ Z = {e_{3}}. Since p_{i}(D′_{3}), p_{i}(D_{2}) and p_{i}(Z) are even, and p_{i}(D′_{3}) ≡ p_{i}(D_{2}) + p_{i}(D) + p_{i}(Z) (mod 2), p_{i}(D) is even. We now show D is balanced in (M_{i}, p_{i}). Let e ∈ D. If e ∈ D ∩ D_{2}, then

p_{i}(e) ≤ p_{i}(D_{2} − {e}) = p_{i}(D_{2} − {e_{2}}) + p(e_{2}) − p_{i}(e)
= n_{2} + n_{2} − p_{i}(e) ≤ 2(n_{2} + n_{3}) − p_{i}(e) = 2p_{i}(e_{1}) − p_{i}(e)
≤ p_{i}(D − {e_{1}}) + p_{i}(e_{1}) − p_{i}(e) = p_{i}(D − {e}).

If e ∈ D −D_{2}, then e ∈ D′_{3} = D_{2}△D△Z. Since D′_{3} ∩Z = {e_{3}} and p(e_{3}) = n_{3}, D′_{3} is balanced and eulerian in (M_{i}, p_{i}) as in the second sentence of this case. Therefore

p_{i}(e) ≤ p_{i}(D_{2}△D△Z − {e}) ≤ p_{i}(D − {e_{1}}) + p(D_{2} − {e_{2}}) + p_{i}(e_{3}) − p_{i}(e)
= p_{i}(D − {e_{1}}) + p_{i}(e_{1}) − p_{i}(e) = p_{i}(D − {e}).

Case |Z ∩ D| = 2: We may assume that D ∩ Z = {e_{1}, e_{2}} so that D△Z is a cocycle of M_{i} satisfying (D△Z) ∩ Z = {e_{3}}. As in the previous case, p_{i}(D△Z) is even. Since p_{i}(Z) is even, p_{i}(D) is even. We now show that D is balanced in (M_{i}, p_{i}) Let e ∈ D. If e ∈ D − {e_{1}, e_{2}}, then e ∈ D△Z. By the previous case D△Z is balanced in (M_{i}, p_{i}) so

p_{i}(e) ≤ p_{i}(D△Z − {e}) = p_{i}(D) − p_{i}(e_{1}) − p_{i}(e_{2}) + p_{i}(e_{3}) − p_{i}(e) ≤ p_{i}(D − {e}).

Lastly, we have

p_{i}(e_{1}) ≤ p_{i}(e_{2}) + p_{i}(e_{3}) ≤ p_{i}(e_{2}) − p_{i}(D − {e_{1}, e_{2}}) = p_{i}(D − {e_{1}})

and similarly p_{i}(e_{2}) ≤ p_{i}(D − {e_{2}}).

We have shown (M_{i}, p_{i}) is admissible, i = 1, 2. By hypothesis (M_{i}, p_{i}) has a circuit cover L_{i}, i = 1, 2. Each circuit in L_{i} which intersects Z in 0 or 2 elements. For j = 1, 2, 3 we denote by L_{i}^{j} those circuits in L_{i} containing Z − {e_{j}}. For any partition {j} ∪ {k, ℓ} of {1, 2, 3} we have |L_{1}^{k}| + |L_{1}^{ℓ}| = p_{1}(e_{j}) = p_{2}(e_{j}) = |L_{2}^{k}| + |L_{2}^{ℓ}|, and thus |L_{1}^{j}| = |L_{2}^{j}| = (p_{1}(e_{k}) + p_{1}(e_{ℓ}) − p_{1}(e_{j}))/2. Similarly to the 2-sum case, the circuits in in L_{1}^{j} may be “paired off” with those in L_{2}^{j}, j = 1, 2, 3 in an obvious way to yield a circuit cover of (M, p). Thus (M, p) has the circuit cover property. □

5 Good Matroids

It remains to show that each of the building blocks of the decomposition of Lemma 3.4 has the circuit cover property. The first is due to Alspach, Goddyn and Zhang [1].

5.1 Lemma Graphic matroids containing no M(P_{10}) minor have the circuit cover property.

We define a partial order on the set of weightings of a matroid M. For p, q : M → we write p ⪯ q if p(e) ≤ q(e) for each e ∈ M. A weighting (M, p) is positive if p(e) ≥ 1 for all e ∈ M. Let B be a cocircuit in M and let e ∈ B. We define the slack of (B, e) in (M, p) by

sl(B, e) = sl_{p}(B, e) := p(B − e) − p(e).

Thus if (M, p) is admissible, then sl(B, e) is a nonnegative even integer. The following is convenient for showing that a matroid has the circuit cover property.

5.2 Lemma Let M be a matroid such that M\e has the circuit cover property for all e ∈ M. Suppose further that, for any admissible positive weighting (M, p), there exists a circuit C such that for any cocircuit B and e ∈ B,

sl(B, e) ≥ \{ \begin{matrix}|C ∩ B| & if e ∉ C \\ |C ∩ B| − 2 & if e ∈ C. \end{matrix}  (2)

Then M has the circuit cover property.

Proof. Suppose M satisfies the hypothesis, but does not have the circuit cover property. Let (M, p) be a ⪯-minimal admissible weighting which has no circuit cover. If p(e) = 0 for some e ∈ M, then the restriction (M\e, p) is admissible. By hypothesis (M\e, p) has a circuit cover. This circuit cover is also a circuit cover of (M, p), a contradiction. Thus p is positive, whence there exists a circuit C satisfying (2) for every cocircuit B and e ∈ B. Let p′ := p − χ^{C}. Since (M, p) is eulerian and positive, (M, p′) is eulerian and nonnegative valued. For any S⊆E(M) we have p′(S) = p(S) − |C ∩ S|, so (2) is equivalent to the statement p′(e) ≤ p′(B − e). Thus (M, p′) is admissible and, by minimality of p, (M, p′) has a circuit cover. Adjoining C to this circuit cover yields a circuit cover of (M, p), a contradiction. Thus M has the circuit cover property. □

5.3 Lemma The matroid F_{7} has the circuit cover property.

Proof. We check that F_{7} satisfies the hypothesis of Lemma 5.2. For any e ∈ F_{7}, F_{7}\e ≅ M(K_{4}) which has the circuit cover property by Lemma 5.1. Let (F_{7}, p) be admissible and positive. Let a, b ∈ F_{7} be such that p(e) ≤ p(b) ≤ p(a) for all e ∈ E − {a, b}, and let C be the unique circuit of cardinality 3 containing a and b. Let B be any cocircuit of F_{7} and let e ∈ B. As |C ∩ B| is even and |C| = 3, C ∩ B contains either 0 or 2 elements. Since sl(B, e) ≥ 0, (2) holds unless e ∉ C and |C ∩ (B − e)| = 2. In this case e is different from a and b. Every cocircuit of F_{7} has cardinality 4 so B − e contains 3 elements of positive weight. Since |C−B| = 1, one of these 3 elements is either a or b. We have sl(B, e) = p(B−e)−p(e) ≥ (p(b)+2)−p(e) ≥ 2 and (2) holds. Thus F_{7} has the circuit cover property. □

The following lemma completes the proof of the main theorem. It is the most involved single step in its proof. The details are supplied in the next section.

5.4 Lemma The matroid M^{∗}(V_{8}) has the circuit cover property.

6 Bond covers of V_{8}

To minimize confusion we use a separate terminology for graphs. A cycle in a graph G is the edge set of a simple closed walk in G. An edge cut is the set δ(X) of edges with exactly one endpoint in X for some X⊆V (G). A bond is an minimal nonempty edge cut. We say that G has the bond cover property if M^{∗}(G) has the circuit cover property. The graph V_{8} is obtained from the polygon v_{0}e_{0}v_{1}e_{1} ⋯ e_{6}v_{7}e_{7} by adding the edges e_{04}, e_{15}, e_{26}, e_{37}, where each e_{ij} has endpoints v_{i} and v_{j}. Each e_{i} is called a rim edge whereas each e_{ij} is called a spoke. The automorphism group of V_{8} is the dihedral group of order 16. Our aim is to show that V_{8} has the bond cover property.

If G is a plane graph then G has the bond cover property if and only if the polygon matroid of its plane dual G^{∗} has the the circuit cover property. As planar graphs do not have P_{10} as a minor, Lemma 2.3 implies the following.

6.1 Lemma Every planar graph has the bond cover property.

□

Applying Lemmas 3.3 and 4.2, we have the following.

6.2 Lemma All proper minors of V_{8} have the bond cover property.

□

As in Section 5, we define

sl(C, e) := p(C − e) − p(e)

for any cycle C and e ∈ C. We say that an edge weighted graph (G, p) is bond admissible if (M^{∗}(G), p) is admissible. Thus p : E(G) → _{+} is bond admissible if for each cycle C and e ∈ C, sl(C, e) is a non-negative even integer. A cycle C in (G, p) is balanced if sl(C, e) ≥ 0 for all e ∈ C, and is tight if sl(C, e) = 0 for some e ∈ C. If sl(C, e) = 0, then e is called a leader of C. If G is simple and p is positive and bond admissible, then each tight cycle in (G, p) has a unique leader. A chord of a cycle C is an edge in E(G) − C such that both its endpoints are incident with an edge in C. We recall that the symmetric difference of two cycles in G is an edge-disjoint union of cycles in G.

6.3 Lemma Let p be a positive weighting of a graph G. Let C, C′ be cycles and e, f be edges in G such that e ∈ C −C′ and f ∈ C ∩C′. Let D be a cycle in C△C′ containing e. Then sl(D, e) ≤ sl(C, e)+sl(C′, f) with equality if and only if D = C△C′ and f is a chord of D.

Proof. Let a = sl(C, e) and b = sl(C′, f). We have p(C△C′ −e) = p(C −e−f)+p(C′ −f)−2p(C ∩C′ −f) and so

p(e) = p(C − e) − a = p(C − e − f) − a + p(f)
= p(C − e − f) − a + p(C′ − f) − b
= p(C△C′ − e) + 2p(C ∩ C′ − f) − a − b
≥ p(D − e) − a − b.

Since p is positive, equality holds if and only if D = C△C′, and C ∩ C′ = {f}. □

6.4 Corollary Let C be a cycle in G, e ∈ C and let f be a chord of C. Let C_{e} be the cycle in C ∪ {f} containing both e and f, and let C_{f} be the cycle in C ∪ {f} − {e}. Then for any edge-weighting p we have

sl(C, e) = sl(C_{e}, e) + sl(C_{f}, f). □

For any edge weighting (V_{8}, p) we define the set of leaders

L = L(p) := {e ∈ E(V_{8}) : e is the leader of some tight cycle in (V_{8}, p)}.

6.5 Lemma Let (V_{8}, p) be positive and bond admissible. If |C ∩ L| ≥ 2 for some tight cycle C, then (V_{8}, p) has a bond cover.

Proof. Let e, f ∈ C ∩ L and assume that e is the (unique) leader of C. Then f is the leader of some tight cycle C′ different from C. Since p(f) < p(e), we have e ∉ C′. Let D be the cycle in C△C′ containing e. As D is a balanced in (V_{8}, p), Lemma 6.3 gives 0 ≤ sl(D, e) ≤ sl(C, e) + sl(C′, f) = 0 so D = C△C′ is a tight cycle and f is a chord of D.

Let x, y be the endpoints of f. Since every cycle in V_{8}\f is a cycle in V_{8}, (V_{8}\f, p) is bond admissible. By Lemma 6.2, (V_{8}\f, p) has a bond cover L′. Let L′′ be the sublist consisting of those bonds δ(X) in L′ for which |X ∩ {x, y}| = 1. Let L be the list of bonds in V_{8} obtained from L′ by adding the edge f = xy to those bonds in L′′. Since D is tight, each bond in L′ which contains e contains exactly one other edge in D, so the number of bonds in L′′ is exactly p(C′ − f) = p(f). Thus L is a bond cover of (V_{8}, p). □

We say that a bond B in (V_{8}, p) is removable if (V_{8}, p − χ^{B}) is bond admissible. In particular, any bond in a bond cover of (V_{8}, p) is removable. As in Lemma 5.2, if p is positive, then a bond B is removable if and only if for any cycle C and e ∈ C,

sl(C, e) ≥ \{ \begin{matrix}|B ∩ C| & if e ∉ B \\ |B ∩ C| − 2 & if e ∈ B. \end{matrix}

We derive a sufficient condition, depending only on the leaders L(p), for a bond to be removable in (V_{8}, p). A k-cycle is a cycle of cardinality k.

6.6 Lemma Let (V_{8}, p) be positive and bond admissible. Then a bond B is removable provided all of the following hold.

1. L ⊆ B

2. For every 4-cycle C contained in B, we have |C ∩ L| ≥ 2.

3. For every 5-cycle C such that |C ∩ B| = 4, we have |C ∩ L| ≥ 2 and there exists f ∈ C ∩ L such that every chordless cycle C′ containing f satisfies |C′ ∩ (C ∪ L)| ≥ 2.

Proof. Suppose that B is not removable, but that 1., 2., and 3. hold. Let p′ = p − χ^{B}. Then some cycle is unbalanced in (V_{8}, p′). Applying Corollary 6.4, there exists an unbalanced cycle C in (V_{8}, p′) which is chordless. Since every cycle in V_{8} having cardinality greater than five has a chord, we have 4 ≤ |C| ≤ 5. Since C is balanced in (V_{8}, p) but not in (V_{8}, p′), |B ∩ C| equals either 2 or 4. If |B ∩ C| = 2, then C is tight in (V_{8}, p) and B does not contain the leader of C, contradicting 1. Thus we have 4 = |C ∩ B| ≤ |C| ≤ 5. By 2. and 3., |C ∩ L| ≥ 2. If C were tight in (V_{8}, p), then (V_{8}, p) would have a removable bond by Lemma 6.5. Thus C is not tight in (V_{8}, p) whereas C is unbalanced in (V_{8}, p′). Since |C| ≤ 5 this can happen only if |C| = 5 and, for some e ∈ C, C − B = {e} and sl_{p}(C, e) = 2. Let f ∈ C ∩ L be the edge specified in condition 3. Applying Corollary 6.4, f is a leader of some chordless tight cycle C′. Since f ∈ C′ ∩ C ∩ L, condition 3. implies that either |C′ ∩ C| ≥ 2 or |C′ ∩ L| ≥ 2. Applying Lemma 6.5 to C′, we may assume |C′ ∩ L| = 1 and thus |C′ ∩ C| ≥ 2. If e ∈ C′, then p(f) = p(C′ − f) ≥ p(e) = p(C − e) − 2 ≥ p(f) − 2 which is absurd. Therefore e ∈ C − C′ and f ∈ C ∩ C′. Let D be the cycle in C△C′ which contains e. Applying Lemma 6.3 to (V_{8}, p), we have sl(D, e) ≤ sl(C, e) + sl(C′, f) = 2 + 0. Since |C′ ∩ C| ≥ 2, we do not have equality here, whence sl(D, e) = 0. Thus e ∈ L − B, contradicting 1. □

A matching is a set of edges such that no two are adjacent.

6.7 Lemma Let (V_{8}, p) be positive and bond admissible. If L is not a matching of cardinality at least two, then V_{8} has a removable bond.

Proof. Let v ∈ V (V_{8}). Every cycle intersects the star-bond δ(v) in at most two edges. Therefore if δ(v) is not removable, then there exists a tight cycle C in (V_{8}, p) which intersects δ(v) but whose leader is not contained in δ(v). Since v is arbitrary, we have |L| ≥ 2. Furthermore, if v is incident with at least two edges in L, then one of these two edges is in C, since v has degree three. Thus |C ∩ L| ≥ 2 and by Lemma 6.5, (V_{8}, p) has a bond cover. □

We now complete the proof of Theorem 5.4. By Lemmas 5.2 and 6.2 it suffices to show the existence of a removable bond in any positive, bond admissible weighting (V_{8}, p). By Lemma 6.7 we may assume that L(p) is a matching of cardinality at least two. For S⊆E(V_{8}) we denote by [S] the orbit of S under the group of automorphisms of V_{8}. Referring to Figure 1, we claim that for any matching L in V_{8} with |L| ≥ 2, there is a bond B in either [B_{1}], [B_{2}], [B_{3}] or [B_{4}] satisfying conditions 1., 2., and 3. of Lemma 6.6. We note that condition 2. is vacuously true for B_{1}, B_{3} and B_{4}, and that condition 3. is vacuously true for B_{1}, B_{2} and B_{3}.

If L contains no rim edges and |L| ≤ 3, then some bond in [B_{1}] contains L, and thus satisfies 1., 2., and 3. If L consists of all four spokes in V_{8}, then B_{2} satisfies the three conditions. If L contains exactly one rim edge then, since L is a matching, some bond in [B_{1}] contains L and is therefore removable. If L contains exactly two rim edges and these two edges are at distance 3 (4) along the rim of V_{8}, then some bond in [B_{1}] ([B_{2}]) again satisfies the three conditions, and hence is removable. If L contains exactly two edges at distance 2 along the rim of V_{8} then, since L is a matching, |L| = 2 and a bond in [B_{3}] contains L and thus satisfies the three conditions. If L contains 3 or 4 rim edges, then L contains no spokes since L is a matching. If L⊆B_{3}, then B_{3} is removable so we may assume that L = {e_{0}, e_{2}, e_{5}}. We claim that B_{4} is removable in this case. In this case condition 3. must be checked with C = {e_{2}, e_{3}, e_{4}, e_{5}, e_{26}}; here e_{5} serves as the required edge f. In all cases, there is a removable bond in V_{8}, and thus V_{8} has the bond cover property.

Figure 1: Four bonds in V_{8}

7 Remarks

Remark 2.2 provides a good reason that none of F_{7}^{∗}, R_{10}, M^{∗}(K_{5}) has the circuit cover property; each of these matroids has an admissible weighting which does not even have a “fractional” circuit cover. This suggests that the admissibility conditions, 1.1, 1.2, 1.3, should be replaced with stronger ones. Let C = C(M) denote the set of circuits in matroid M. Let _{+} denote the non-negative rational numbers. For any matroid M we define the lattice, the cone and the integer cone of circuits in M by

(C) := {∑_{C∈C} α_{C}χ^{C} : α_{C} ∈ for all C ∈ C}
+(C) := {∑_{C∈C} α_{C}χ^{C} : α_{C} ∈ _{+} for all C ∈ C}
+(C) := {∑_{C∈C} α_{C}χ^{C} : α_{C} ∈ _{+} for all C ∈ C}

Thus (M, p) has a circuit cover if and only if p ∈ _{+}(C). For any matroid,

+(C)⊆ _{+}(C) ∩ (C).

If equality holds here, then we say that C forms a Hilbert base. Let H denote the class of matroids whose circuits form a Hilbert base. The following problem is raised in [5].

7.1 Problem Characterize the matroids in H.

It is known (see [5, 10]) that for any binary matroid M with no F_{7}^{∗} minor, a weighting p : M → belongs to (M) if and only if 1.2 holds for all cocircuits B and 1.3 holds for all cocircuits B with |B| ≤ 2. Seymour [13] showed that, for all binary matroids with no F_{7}^{∗}, R_{10} or M^{∗}(K_{5}) minor, a weighting p : M → _{+} belongs to _{+}(M) if and only if 1.3 holds for all cocircuits B. Thus our main theorem partially answers the above problem.

7.2 Corollary Let M be a binary matroid with no F_{7}^{∗}, R_{10} or M^{∗}(K_{5}) minor. Then M ∈ H if and only if M has no M(P_{10}) minor.

□

If M contains a F_{7}^{∗}, R_{10} or M^{∗}(K_{5}) minor, then our main theorem is no longer relevant since the cone of circuits of M is strictly contained in cone of non-negative weights p satisfying 1.3. Indeed, it is N Phard to determine whether p ∈ _{+}(M), even if M is cographic [7]. Some further progress has been made on Problem 7.1. For example, the dual of any projective geometry PG(n, q) (including F_{7}^{∗} = PG^{∗}(2, 2)) belongs to H since its circuits are linearly independent in ^{E}. It follows from matroid partition theory (see [2]) that the bases of a matroid form a Hilbert base, and hence all uniform matroids belong to H. M. Laurent [9] has shown that H contains every proper minor of M^{∗}(K_{6}) whereas no cographic matroid containing an M^{∗}(K_{6}) minor is in H. As far we know, the following problem is open.

7.3 Problem Is the class of cographic matroids in H closed under taking minors?

Acknowledgement

An early version of this paper appears in the first author’s Masters thesis [4]. We would like to thank B. R. Alspach for helpful comments on the thesis.

References

[1] B. Alspach, L. Goddyn and C-Q Zhang, Graphs with the circuit cover property, Trans. Amer. Math. Soc. 344 (1994), 131–154.

[2] W. Cook, J. Fonlupt, A. Schrijver An integer analogue of Carathéodory’s Theorem, J. Comb. Theory Ser. B 40 (1986), 63–70.

[3] G. Fan and C-Q Zhang, Circuit Decompositions of Eulerian Graphs, J. Comb. Theory Ser. B, submitted.

[4] X-D Fu, Matroids with the circuit cover property, Masters thesis, Department of Mathematics and Statistics, Simon Fraser University, September, 1991.

[5] L. Goddyn, Cones, lattices and Hilbert bases of circuits and perfect matchings. in “Graph Structure Theory”, N. Robertson, P. Seymour, Eds., Contemporary Mathematics 147, pp. 419–440. American Mathematical Society, 1993.

[6] L. Goddyn, J. van den Heuvel, S. McGuinness, Removable circuits in multigraphs, in preparation.

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

[8] B. Jackson, On circuit covers, circuit decompositions and Euler tours of graphs, in “Surveys in Combinatorics,” (Keele Ed.), London Math. Soc. Lecture Note Ser. 187, pp. 191–210 Cambridge Univ. Press, Cambridge, 1993.

[9] M. Laurent, Hilbert bases of cuts, Research report LIENS – 93 – 9 , Laboratoire d’Informatique, URA 1327 du CNRS, Département de Mathématiques et d’Informatique, Ecole Normale Supérieure, April 1993.

[10] L. Lovász, Á. Seress, The cocycle lattice of binary matroids. Europ. J. Combinatorics 14 (1993), 241–250.

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

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

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

[14] K. Truemper, Matroid Decomposition, Academic Press, Boston (1992).

[15] J. G. Oxley, Matroid Theory, Oxford University Press, New York (1992).

[16] K. Wagner, Uber eine Eigenschaft der evenen Komplexe, Math. Ann. 114 (1937), 570–590.

[17] C-Q Zhang, Cycle cover theorems and their applications, in “Graph Structure Theory,” (N. Robertson and P. Seymour, Eds.), Contemporary Mathematics 147 (1993), 405–418.

[18] C-Q Zhang, Cycle covers and cycle decompositions of graphs, Annals Discrete Math. 55 (1993), 183–190.

[19] C-Q Zhang, On even circuit decompositions of eulerian graphs, J. Graph Theory 18 (1994), 51–57.

[20] C-Q Zhang, Hamiltonian weights and unique 3-edge-colorings of cubic graphs, Journal of Graph Theory, (to appear).