Removable Circuits in Binary Matroids

Luis A Goddyn Department of Mathematics and Statistics

Simon Fraser University, Burnaby, B.C., Canada V5A 1S6

and Bill Jackson Department of Mathematical and Computing Sciences Goldsmiths’ College, London SE14 6NW, England

June 30, 1997

Abstract We show that if M is a connected binary matroid of cogirth at least five which does not have both an F_{7}-minor and an F_{7}^{∗}-minor, then M has a circuit C such that M − C is connected and r(M − C) = r(M).

1 Introduction

We shall consider the problem of finding sufficient conditions for the existence of a circuit in a given matroid M whose deletion leaves the rank or connectivity of M unchanged. The existence of such a circuit in graphs has been considered by various authors. The most general result for simple graphs can be deduced from a theorem of W. Mader [5, Satz 1].

Theorem 1 Let k be a positive integer and G be a simple k-connected graph of minimum degree at least k+2. Then G has a circuit C such that G−E(C) is k-connected.

Stronger results for the special case when G is simple and k = 2 can be found in Jackson [4] and Thommassen and Toft [10].

It seems natural to ask if Theorem 1 can be extended to a graph G, which may contain multiple edges. We can obtain a partial result by applying Theorem 1 to the underlying simple graph of G, if G has no edges of multiplicity greater than two, and otherwise choosing C to be a 2-circuit of G belonging to an edge of multiplicity at least three, to deduce

Corollary 2 Let k be a positive integer and G be a k-connected graph of minimum degree at least k + 3. Then G has a circuit C such that G − E(C) is k-connected.

It follows from a result of Sinclair [9] that the bound k + 3 in Corollary 2 can be reduced to k + 2 for the special case when k = 1. This is not true when k = 2, however, as can be seen from an example constructed by N. Robertson and later B. Jackson (see [4]). However, replacing k + 3 by k + 2 when k = 2 in Corollary 2 is valid for graphs which do not contain a vertex of degree four incident with two edge-disjoint 2-circuits by [9], for planar graphs by [1], and, more generally, graphs with no Petersen minor, by [2].

Oxley asked in [7, Problem 14.4.8] if the following partial extension of Theorem 1 when k = 2 is valid for binary matroids: does every connected binary matroid of girth at least three and cogirth at least four have a circuit C such that M −C is connected? L Lemos (see [2]) has constructed a cographic matroid of cogirth four which shows that the answer to Oxley’s question is no. It remains an open problem, however, to decide if there exists an integer t ≥ 5 such that all connected binary matroids M of cogirth at least t have a circuit C such that M −C is connected. We shall show in Theorem 7 that this assertion is true with t = 5 for binary matroids M which do not have both an F_{7}- and an F_{7}^{∗}-minor. This gives a partial generalisation of Corollary 2 when k = 2. Our proof uses the decomposition theory of Seymour in [8] which implies that a 3-connected, vertically 4-connected binary matroid which does not have both an F_{7}-minor and an F_{7}^{∗}-minor is either graphic or cographic, or is isomorphic to R_{10}, F_{7} or F_{7}^{∗}. We shall first show that our result holds for graphic and cographic matroids. We then proceed by contradiction and show that a smallest counterexample to the result would be vertically 4-connected. It then only remains to check that the result holds for matroids obtained from R_{10}, F_{7} or F_{7}^{∗} by parallel extensions.

2 Graphs

We shall consider finite graphs which may contain multiple edges, but no loops. We consider a graph G to be 2-connected if G − v is connected for all v ∈ V (G). We shall use E_{G}(v) to denote the set of edges of G incident with a vertex v and put d_{G}(v) = |E_{G}(v)|. We will suppress the subscript G when it is clear to which graph we are referring. Given a circuit C of G, put |C| = |E(C)|.

We first obtain, in Lemma 4 below, a slight extension of the case k = 2 of Corollary 2. We need this extension for our inductive proof on matroids. Lemma 4 itself follows from a result of Sinclair [9]. We include a proof in this paper for the sake of completeness. We shall use the following elementary result.

Lemma 3 Let G be a graph on n vertices and C_{0} be a circuit of G such that |C_{0}| ≤ 3 and n > |C_{0}|. Suppose that for all v ∈ V (G) − V (C_{0}) we have d_{G}(v) ≥ 4. Then G has a circuit C such that E(C_{0}) ∩ E(C) = ∅.

Proof. If G is not 2-connected then choosing C to be any circuit in an endblock of G which does not contain C_{0} we have E(C_{0}) ∩ E(C) = ∅. Hence we may suppose that G is 2-connected.

Let H = G − E(C_{0}). Suppose H is a forest. Then |E(H)| ≤ n − 1. Let t be the number of edges between V (C_{0}) and V (G) − V (C_{0}). Then |E(H)| = \frac{1}{2}(t + ∑_{v∈V (G)−V (C_{0})} d_{G}(v)). Since G is 2-connected, t ≥ 2, and since d(v) ≥ 4 for all v ∈ V (G) − V (C_{0}), we have |E(H)| ≥ 2n − 2|C_{0}| + 1. Thus n ≤ 2|C_{0}| − 2. Since n ≥ |C_{0}|, we have |C_{0}| = 3, and n = 4. Let V (G) − V (C_{0}) = {v}. Using the assumption that H is a forest, we have d_{G}(v) ≤ 3. This contradicts an hypothesis on G and so the assumption that H is a forest must be false.

Lemma 4 Let G be a 2-connected graph on n vertices and C_{0} be a circuit of G such that |C_{0}| ≤ 3 and n > |C_{0}|. Suppose that for all v ∈ V (G) − V (C_{0}) we have d_{G}(v) ≥ 5. Then G − E(C_{0}) has a circuit C such that G − E(C) is 2-connected.

Proof. Suppose the theorem is false and let G be a counterexample. By Lemma 3, we can choose a circuit C in G − E(C_{0}). Let H = G − E(C), let B_{0} be the block of H which contains C_{0} and B be an end-block of H distinct from B_{0}. We may suppose that C has been chosen such that |E(B)| is minimal. Let e be an edge of B chosen such that, if B contains a cut-vertex x of H, then e is incident with x. Since d_{G}(v) ≥ 5 for all v ∈ V (G) − V (C_{0}), at most one vertex of B − e has degree less than two. Thus we may choose a circuit C′ contained in B − e. Using the minimality of |E(B)| and the fact that G is 2-connected we see that each end-block of H−E(C′) is incident with C and each component of H − E(C′) is incident with at least two vertices of C. Thus G − E(C′) = (H − E(C′)) ∪ E(C) is 2-connected. This contradicts the choice of G as a counterexample to the theorem.

Given a graph G and U ⊆ V (G), we use N_{G}(U) to denote the set of vertices of V (G) − U adjacent to a vertex of U and G[U] to denote the subgraph of G induced by U. For S ⊆ E(G), let G/S be the graph obtained from G by contracting the edges in S, and V (S) the set of vertices of G incident with S.

We next show, in Lemma 6 below, that the case k = 2 of Corollary 2 can be extended to cographic matroids. We shall use the following elementary result.

Lemma 5 Let G be a connected graph on n vertices and X_{0} be a cocircuit of G such that |X_{0}| ≤ 3 and |E(G)| ≥ n + |X_{0}| − 1. Suppose that G − X_{0} has girth at least four. Then V (G) ≠ V (X_{0}).

Proof. Let H_{1} and H_{2} be the two components of G − X_{0}. Suppose V (G) = V (X_{0}). Then |V (H_{i})| ≤ 3 and since G − X_{0} has girth at least four, H_{i} is a tree for 1 ≤ i ≤ 2. Thus

|E(G)| = |V (H_{1})| − 1 + |V (H_{2})| − 1 + |X_{0}| = n + |X_{0}| − 2.

This contradicts the hypothesis on |E(G)|.

Lemma 6 Let G be a 2-connected graph on n vertices and X_{0} be a cocircuit of G such that |X_{0}| ≤ 3 and |E(G)| ≥ n + |X_{0}| − 1. Suppose that G − X_{0} has girth at least five. Then there exists v ∈ V (G) − V (X_{0}) such that G/E(v) is 2-connected.

Proof. Suppose the theorem is false and let G be a counterexample. By Lemma 5, we can choose a vertex v in V (G) − V (X_{0}). Let H = G/E(v) and x be the vertex of H corresponding to N_{G}(v) ∪ {v}. Then x is the unique cut vertex of H. Since X_{0} ∩ E(v) = ∅, X_{0} is a cocircuit of H and hence is contained in a block B of H. Let U = V (B) − x. We may suppose that v has been chosen such that |U| is maximal. Note that N_{G}(U) ⊆ {v} ∪ N_{G}(v). Furthermore, since G is 2-connected, |N_{G}(U)| ≥ 2 and G[U ∪ N_{G}(U) ∪ {v}] is 2-connected. Choose v′ ∈ V (H) − V (B). Then v′ ∈ V (G) − V (X_{0}). Let H′ = G/E(v′_{)} and x′ be the vertex of H corresponding to N_{G}(v′) ∪ {v′}. Let B′ be the block of H′ containing X_{0} and U′ = V (B′) − x′. Then U ∪ (N_{G}(U) − N_{G}(v′)) is properly contained in V (B′). By the maximality of |U| we must have N_{G}(U) ⊆ N_{G}(v′). Now the facts that N_{G}(U) ⊆ {v} ∪ N_{G}(v) and |N_{G}(U)| ≥ 2 imply that E(v) ∪ E(v′) contains a circuit of G of length at most four. This contradicts the fact that G − X_{0} has girth at least five.

3 Binary Matroids

We shall use the following operation on binary matroids from Seymour [8]. Given binary matroids M_{1} and M_{2} let M_{1}△M_{2} be the binary matroid with E(M) = E(M_{1})△E(M_{2}) and circuits all minimal non-empty subsets of E(M) of the form C_{1}△C_{2}, where C_{i} is a circuit of M_{i}. We refer the reader to [7] for other definitions on matroids. Our main result is

Theorem 7 Let M be a connected binary matroid which does not have both an F_{7}-minor and an F_{7}^{∗}-minor. Let C_{0} be a circuit of M such that |C_{0}| ≤ 3 and r(M) > r(C_{0}). Suppose |X| ≥ 5 for all cocircuits X of M such that X ∩ C_{0} = ∅. Then M − C_{0} has a circuit C such that M − C is connected and r(M − C) = r(M).

Proof. We proceed by contradiction. Suppose the theorem is false and let M be a counterexample chosen such that r(M) is as small as possible.

Claim 1 M is vertically 3-connected.

Proof. Suppose that M has a vertical 2-separation (S_{1}, S_{2}). Choose (S_{1}, S_{2}) such that |S_{1} ∩ C_{0}| is minimal. Since r(S_{i}) ≥ 2 we have |S_{i}| ≥ 2. By [8, 2.6], M = M_{1}△M_{2} for minors M_{1} and M_{2} of M such that 2 ≤ r(M_{i}) < r(M), E(M_{1})∩E(M_{2}) = C′_{0} for some 2-circuit C′_{0} = {f, g} of M_{i}, and E(M_{i})−C′_{0} = S_{i} for 1 ≤ i ≤ 2. Since M is connected each M_{i} is connected. Since M_{i} is a minor of M, M_{i} is binary and does not have both an F_{7}-minor and an F_{7}^{∗}-minor. Since C′_{0} ∩ E(M) = ∅ we have C′_{0} ∩ C_{0} = ∅. Since |C_{0}| ≤ 3, |C_{0} ∩ E(M_{1})| ≤ 1.

Suppose C_{0}∩E(M_{1}) = {e}. Then C_{0} = C_{1}△C_{2} for some circuits C_{i} of M_{i}, 1 ≤ i ≤ 2. Thus |C_{1}| = 2 and e is parallel to f and g in M_{1}. Let h ∈ S_{1} − e and Y be a circuit of M which meets both S_{1} and S_{2}. Then Y = Y_{1}△Y_{2}△ for some circuits Y_{i} of M_{i} such that |Y_{i} ∩C′_{0}| = 1, 1 ≤ i ≤ 2. Thus Y_{1} −C′_{0} +e is a circuit of both M_{1} and M, and r(S_{1} − e) = r(S_{1}) ≥ 2. Similarly since e ∈ C_{0} ⊆ S_{2} + e we have r(S_{2} + e) = r(S_{2}) ≥ 2. Thus (S_{1} − e, S_{2} + e) is a vertical 2-separation of M. This contradicts the minimality of |S_{1} ∩ C_{0}|. Hence we must have C_{0} ∩ E(M_{1}) = ∅.

Let X_{1} be a cocircuit of M_{1} such that X_{1} ∩C′_{0} = ∅. Then X_{1} is a cocircuit of M such that X_{1} ∩ C_{0} = ∅ so by an hypothesis of the theorem we have |X_{1}| ≥ 5. Using the minimality of r(M) we deduce that M_{1} − C′_{0} has a circuit C such that M_{1} − C is connected and r(M_{1} − C) = r(M_{1}). Since M − C = (M_{1} − C)△M_{2} we have C is a circuit of M − C_{0} such that M − C is connected and r(M − C) = r(M). This contradicts the choice of M. Thus M has no vertical 2-separation and hence M is vertically 3-connected.

Claim 2 M is vertically 4-connected.

Proof. Suppose that M has a vertical 3-separation (S_{1}, S_{2}). Choose (S_{1}, S_{2}) such that |S_{1} ∩ C_{0}| is minimal. Since |C_{0}| ≤ 3, |C_{0} ∩ E(M_{1})| ≤ 1. We first show that |S_{i}| ≥ 4 for 1 ≤ i ≤ 2.

Suppose |S_{i}| = 3 for some i ∈ {1, 2}. Since r(S_{i}) ≥ 3 we must have r(S_{i}) = 3. Since r(S_{1}) + r(S_{2}) − r(M) = 2 we have r(S_{j}) = r(M) − 1, for j = 3−i. Thus the closure of S_{j} is a hyperplane of M. The complement of this hyperplane will be a cocircuit X_{0} of M contained in S_{i}. Since |X_{0}| ≤ |S_{i}| = 3, it follows from an hypothesis of the theorem that X_{0} ∩ C_{0} ≠ ∅. Since M is binary we must have |X_{0} ∩ C_{0}| = 2. Since S_{i} is independent we must have |C_{0}| = 3 and |S_{j} ∩ C_{0}| = 1. By the minimality of |S_{1} ∩ C_{0}|, we must have i = 2. Choosing e_{0} ∈ S_{1} ∩ C_{0} we have r(S_{1} − e) ≤ r(S_{1}) and, since e_{0} ∈ C_{0} ⊆ S_{2} + e_{0}, r(S_{2} + e_{0}) = r(S_{2}) = 3. Thus (S_{1} − e_{0}, S_{2} + e_{0}) is either a vertical 2-separation of M, contradicting Claim 1, or it is a vertical 3-separation of M, contradicting the minimality of |S_{1} ∩ C_{0}|. Thus |S_{i}| ≥ 4 for i ∈ {1, 2}.

By [8, 2.9], M = M_{1}△M_{2} for minors M_{1} and M_{2} of M such that 3 ≤ r(M_{i}) < r(M), E(M_{1}) ∩ E(M_{2}) = C′_{0} for some 3-circuit C′_{0} = {f, g, h} of M_{i}, and E(M_{i}) − C′_{0} = S_{i} for 1 ≤ i ≤ 2. Since M is connected, each M_{i} is connected. Since M_{i} is a minor of M, M_{i} is binary and does not have both an F_{7}- and an F_{7}^{∗}-minor. Since C′_{0} ∩ E(M) = ∅ we have C′_{0} ∩ C_{0} = ∅.

Suppose e ∈ C_{0} ∩ E(M_{1}). Then C_{0} = C_{1}△C_{2} for some circuit C_{i} of M_{i}, 1 ≤ i ≤ 2. Thus C_{1} − C′_{0} = {e} and 1 ≤ |C_{1} ∩ C′_{0}| ≤ 2. If |C_{1} ∩ C′_{0}| = 2 then replacing C_{1} by C′_{1} = C_{1}△C′_{0} we have |C′_{1} ∩ C′_{0}| = 1. Thus we may assume without loss of generality that e is parallel to f in M_{1}. Let M′_{1} be the simple matroid obtained by replacing all parallel classes of M_{1} by single elements and let f, g and h represent their own parallel classes in M′_{1}. Using Claim 1 it follows that M′_{1} is 3-connected. If f is a coloop M′_{1} − {g, h} then C′_{0} would contain a cocircuit of M′_{1}. Since M′_{1} is binary this cocircuit would have size two and hence would contradict the fact that M′_{1} is 3-connected. Thus f is contained in some circuit of M′_{1} − {g, h}. Since e is parallel to f we deduce that M has a circuit which contains e and is contained in S_{1}. Hence r(S_{1} − e) = r(S_{1}) ≥ 2. Similarly since e ∈ C_{0} ⊆ S_{2} + e we have r(S_{2} + e) = r(S_{2}) ≥ 2. Thus (S_{1} − e, S_{2} + e) is a vertical 3-separation of M which contradicts the minimality of |S_{1} ∩ C_{0}|. Hence we must have C_{0} ∩ E(M_{1}) = ∅.

Let X_{1} be a cocircuit of M_{1} such that X_{1} ∩C′_{0} = ∅. Then X_{1} is a cocircuit of M such that X_{1} ∩ C_{0} = ∅ so by an hypothesis of the theorem we have |X_{1}| ≥ 5. Using the minimality of r(M) we deduce that M_{1} − C′_{0} has a circuit C such that M_{1} − C is connected and r(M_{1} − C) = r(M_{1}). Since M − C = (M_{1} − C)△M_{2} it follows that C is a circuit of M such that M − C is connected and r(M − C) = r(M). This contradicts the choice of M. Thus M has no vertical 3-separation and hence M is vertically 4-connected.

We are now ready to complete the proof of the theorem. Let M′ be the simple matroid obtained by replacing all parallel classes of M by single elements. By Claims 1 and 2, M′ is a 3-connected vertically 4-connected binary matroid. By [8, 7.6 and 14.3], M′ is either graphic or cographic, or is isomorphic to R_{10}, F_{7} or F_{7}^{∗}. Thus M is either graphic or cographic, or can be obtained from R_{10}, F_{7} or F_{7}^{∗} by a sequence of parallel extensions. If the latter alternative holds then since R_{10}, F_{7} and F_{7}^{∗} have many cocircuits of size four, M − C_{0} must contain a circuit C of size two. The 3-connectivity of M′ now implies that M − C is connected and r(M − C) = r(M). Hence M is graphic or cographic. Lemmas 4 and 6 now give a contradiction to the choice of M as a counterexample to the theorem.

4 Closing Remarks

Remark 1 It follows from Corollary 2 that every connected graph G of minimum degree at least three has a circuit C such that G − E(C) is connected. Thus every graphic matroid M of cogirth at least three has a circuit C such that r(M) = r(M − C). The same result holds for a cographic matroid M of cogirth at least three. (This can be seen by considering the graph G for which M is the cographic matroid. Then G has girth at least three and the set of edges incident with any non-cutvertex of G will give the required circuit C of M.) The result does not extend to regular matroids of cogirth at least three since it does not hold for R_{10} (which has cogirth four). However, if M is a binary matroid which does not have both an F_{7}- and an F_{7}^{∗}-minor, and has cogirth at least five, then we may apply Theorem 7 to a component of M to deduce that M has a circuit C such that r(M) = r(M − C).

One may hope that all binary matroids M of sufficiently high girth have a circuit C such that r(M) = r(M − C). This is not the case. To see this note that r(M) = r(M −C) if and only if C does not contain any cocircuit of M. Thus, if M is identically self-dual (and in particular if M = R_{10}) then no such circuit can exist. The assertion now follows since there exist identically self-dual binary matroids of arbitrarily high cogirth. The column matroid of the parity check matrix of the binary Reed-Muller code R(s, 2s + 1), for example, is identically self dual and has cogirth 2^{s+1}. Remark 2 It is not true that every connected matroid of sufficiently high girth has a circuit C such that M − C is connected. This can be seen by considering the uniform matroid U_{m,2m}. It is still conceivable, however, that this may hold for binary matroids.

Problem 1 Does there exist an integer t such that every connected binary matroid M of cogirth at least t has a circuit C such that M −C is connected?

Remark 3 We could also ask for sufficient conditions for the existence of a cocircuit in a matroid M the deletion of which preserves the connectivity of M. The following reult of P.D. Seymour (see [6, Lemma 6]) is in the spirit of this paper. It is a matroid analogue of an earlier graph theoretic result of Kaugars (see [3, p. 31]).

Lemma 8 Let M be a connected binary matroid of girth and cogirth at least three. Then M has a cocircuit X such that M − X is connected.

References

[1] H. Fleischner and B. Jackson, Removable cycles in planar graphs, J. London Math. Soc. 31 (1985) 8-48.

[2] L.A. Goddyn, J. van den Heuvel and S. McGuinness, Removable circuits in multigraphs, submitted.

[3] F. Harary, ”Graph Theory” Addison-Wesley Reading, Mass.; Menlo Park, Calif.; London (1969). minimum degree at least four, J. London Math. Soc. 21 (1980) 385-392.

[4] B. Jackson, Removable circuits in 2-connected graphs of minimum degree at least four, J. London Math. Soc. 21 (1980) 385-392.

[5] W. Mader, Kreuzungsfreie a, b-Wege in endlichen Graphen, Abh. Sem. Univ. Hamburg 42 (1974) 187-204.

[6] J.G. Oxley, Circuit coverings and packings for binary matroids, Math. Proc. Cambridge Phil. Soc. 83 (1978) 347-351.

[7] J.G. Oxley, ”Matroid Theory”,Oxford Univ. Press Oxford (1992).

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

[9] P.A. Sinclair, Strong snarks and the removal of edges from circuits in graphs, PhD thesis, University of London, 1997.

[10] C. Thomassen and B. Toft, Non-separating induced cycles in graphs, J. Combinatorial Theory (B) 31 (1981) 199-224.