Removable Circuits in Multigraphs

Luis A. Goddyn ^{1} ^{∗} Jan van den Heuvel ^{1}^{†}^{‡} Sean McGuinness ^{2}

1 Department of Mathematics and Statistics, Simon Fraser University Burnaby, B.C., Canada V5A 1S6 2 Department of Mathematics, University of Umeå Umeå, Sweden

∗ Supported by the Natural Sciences and Engineering Research Council of Canada † Supported by a grant from the Natural Sciences and Engineering Research Council of Canada ‡ Current address : Centre for Discrete and Applicable Mathematics, Department of Mathematics, London

School of Economics, Houghton Street, London WC2A 2AE, United Kingdom

Proposed Running Head: Removable Circuits in Multigraphs

Please send proofs to:

Luis Goddyn Department of Mathematics and Statistics Simon Fraser University Burnaby, BC V5A 1S6 CANADA

email: goddyn@sfu.ca tel: (604) 291-4699

Abstract

We prove the following conjecture of Bill Jackson ( J. London Math. Soc. (2) 21 (1980) p. 391 ).

If G is a 2-connected multigraph with minimum degree at least 4 and containing no Petersen minor, then G contains a circuit C such that G − E(C) is 2-connected.

In fact, G has at least two edge-disjoint circuits which can serve as C. Until now, the conjecture had been verified only for planar graphs and for simple graphs.

Keywords : ( removable ) circuit, multigraph, Petersen graph

AMS Subject Classifications (1991) : 05C38, 05C40, 05C70

1 Introduction

In this paper a graph may have multiple edges, but no loops. A graph is simple if it has no multiple edges. A circuit in a graph G is a connected 2-regular subgraph of G. A circuit C in G is removable if G − E(C) is 2-connected. A Petersen minor of a graph G is a minor of G which is isomorphic with Petersen’s graph. A graph is called eulerian if all its vertices have even degree.

The study of removable circuits in a graph seems to have been initiated by A. Hobbs [6], who asked whether every 2-connected eulerian graph with minimum degree at least 4 contains a removable circuit. The answer to this question is no, as was first realized by N. Robertson [11], and later, independently, by B. Jackson [7]. Their counterexample is depicted in Figure 1.

[figure]

Figure 1 A 2-connected 4-regular eulerian graph without removable circuit.

The fact that the counterexample in Figure 1 contains multiple edges, was shown to be unavoidable by the following result.

1.1 Theorem ( Jackson [7] ) Let G be a 2-connected simple graph with minimum degree k ≥ 4 and let e ∈ E(G). Then there exists a removable circuit C in G of length at least k − 1 and such that e ∉ E(C).

In fact, a similar result for arbitrary connectivity can be derived from an older result of W. Mader [8, Satz 1]. We state only the corollary here.

1.2 Theorem ( Mader [8] ) Let G be a k-connected simple graph with minimum degree at least k + 2. Then G contains a circuit C such that G − E(C) is k-connected.

A result with a somewhat different flavor was obtained by C. Thomassen and B. Toft.

1.3 Theorem ( Thomassen & Toft [13] ) Let G be a 2-connected simple graph with minimum degree at least 4. Then G contains an induced circuit C such that G − V (C) is connected and G − E(C) is 2-connected.

Theorems 1.1–1.3 all show that a 2-connected simple graph with minimum degree at least 4 contains a removable circuit. But the problem remains to find sufficient conditions such that this conclusion holds for nonsimple graphs. Since all known examples of 2-connected graphs with minimum degree at least 4 and containing no removable circuit contain the Petersen graph as a minor, the following conjecture was made in [7].

1.4 Conjecture ( Jackson [7] ) Let G be a 2-connected graph with minimum degree at least 4 and containing no Petersen minor. Then G contains a removable circuit.

The special case of Conjecture 1.4 for planar graphs was proved in [3].

1.5 Theorem ( Fleischner & Jackson [3] ) Let G be a planar 2-connected graph with minimum degree at least 4. Then G contains a removable circuit.

In this paper we will present a proof of Conjecture 1.4. In fact, we will prove the following stronger result.

1.6 Theorem Let G be a 2-connected graph with minimum degree at least 4 and containing no Petersen minor. Then G contains 2 edge-disjoint removable circuits.

Theorem 1.6 follows from an even slightly stronger result, the exact statement of which can be found in Section 3.

The remainder of this paper is organized as follows. In the next section, we prove a a special case of our main result regarding eulerian graphs containing no Petersen minor. The general case is proved in Section 3. Section 4 contains some general remarks, possible extensions and related open problems.

2 The eulerian case

The goal of this section is to prove the following result, which is an important step toward the proof of the general theorem.

2.1 Theorem Let G be a 3-connected eulerian graph having no Petersen minor. Then there exist two edgedisjoint removable circuits in G, each having length at least 3.

A circuit decomposition of G is a set of circuits in G whose edge sets partition E(G). A hypergraph H is a set of vertices V (H) together with a multiset E(H) of hyperedges. Each hyperedge is a nonempty subset of V (H). For A, B ⊆ V (H) we denote by [A, B]_{H} the set of hyperedges in H with at least one vertex in each of A and B. A hypergraph H = (V, E) is k-edge connected if for every partition (A, B) of V into two nonempty parts |[A, B]_{H}| ≥ k. If v ∈ V, then H − v denotes the hypergraph with vertex set V \ {v} and hyperedge set { e \ {v} | e ∈ E(H) and |e \ {v}| ≥ 1 }.

2.2 Lemma Let H be a hypergraph of order at least 2. Let k ≥ 1. If H is k-edge connected, then there exist two vertices v_{1}, v_{2} in H such that both H − v_{1} and H − v_{2} are ⌈\frac{1}{2} k⌉-edge connected.

Proof For |V (H)| = 2, the result follows immediately from the definition of edge-connectivity. Suppose |V (H)| ≥ 3 and that there exists v ∈ V (H) such that H − v is not ⌈\frac{1}{2} k⌉-edge connected. Then there is a partition (A, B) of V (H) \ {v} into nonempty parts such that |[A, B]_{H}| ≤ ⌈\frac{1}{2} k⌉ − 1. Let H_{A} denote the hypergraph obtained from H by identifying all vertices in B ∪ {v} with a new vertex b. More precisely, V (H_{A}) = A ∪ {b} and E(H_{A}) = { e ∈ E(H) | e ⊆ A } ∪ { (e′ ∩ A) ∪ {b} | e′ ∈ [A, B ∪ {v}]_{H} }. It is straightforward to check that H_{A} is a k-edge connected hypergraph. Since |V (H_{A})| < |V (H)|, we can inductively find two vertices x, y in V (H_{A}) such that both H_{A} − x and H_{A} − y are ⌈\frac{1}{2} k⌉-edge connected. We may assume x ≠ b, hence x ∈ A. We claim that H − x is ⌈\frac{1}{2} k⌉-edge connected. Suppose this is not true. Then there is a partition (A′, B′) of V (H) \ {x} into nonempty parts such that |[A′, B′]_{H}| ≤ ⌈\frac{1}{2} k⌉ − 1. We may assume v ∈ A′. Set B^{∗} = B ∩ B′ and suppose B^{∗} ≠ Ø. By the choice of A, B, A′, B′ we have |[A, B^{∗}]_{H}| ≤ ⌈\frac{1}{2} k⌉ − 1 and |[A′, B^{∗}]_{H}| ≤ ⌈\frac{1}{2} k⌉ − 1. Since A ∪ A′ = V (H) \ B^{∗}, this implies |[B^{∗}, V (H) \ B^{∗}]_{H}| ≤ 2 (⌈\frac{1}{2} k⌉ − 1) ≤ k − 1, contradicting the fact that H is k-edge connected. Thus we have B^{∗} = Ø, hence B′ ⊆ A. But then |[B′, V (H_{A} − x) \ B′]_{H_{A}}| = |[B′, A′]_{H}| ≤ ⌈\frac{1}{2} k⌉ − 1, contradicting that H_{A} − x is ⌈\frac{1}{2} k⌉-edge connected. This shows that H − x is ⌈\frac{1}{2} k⌉-edge connected. Similarly, there is a vertex x′ ∈ B such that H − x′ is ⌈\frac{1}{2} k⌉-edge connected, which proves the lemma.

2.3 Lemma Let G be a 3-connected graph containing a circuit decomposition L in which every circuit has length at least 3. Then there exist two circuits in L that are removable in G.

Proof We define the hypergraph H_{L} as follows. Set V (H_{L}) = L and E(H_{L}) = { e_{v} | v ∈ V (G) }, where e_{v} = { C ∈ L | v ∈ V (C) }. Since G is 3-connected and L contains no circuits of length 2, H_{L} is 3-edge connected. Since G is 3-connected, L contains at least 2 circuits, hence H_{L} contains at least 2 vertices. So by Lemma 2.2, there exist two circuits C_{1}, C_{2} in L such that H_{L} − C_{1} and H_{L} − C_{2} are 2-edge connected. We will show that this implies that G − E(C_{1}) and G − E(C_{2}) are 2-connected. Suppose that G − E(C_{1}) is not 2-connected. Then we can partition the edges of G−E(C_{1}) into two parts A, B such that |V (G[A])∩V (G[B])| ≤ 1. Thus for any circuit C in L \ {C_{1}} we have E(C) ⊆ A or E(C) ⊆ B. This induces a partition of V (H_{L} − C_{1}) into two parts such that at most one hyperedge of H_{L} − C_{1} intersects both parts, contradicting that H_{L} − C_{1} is 2-edge connected. Similarly, G − E(C_{2}) is 2-connected. Thus C_{1}, C_{2} ∈ L are both removable in G.

The following result is a special case of the main result in [1].

2.4 Theorem ( Alspach, Goddyn & Zhang [1] ) Let G be a 2-connected eulerian graph containing no Petersen minor. Assume further that every edge in G has multiplicity at most 2. Then there exists a circuit decomposition L of G such that every circuit in L has length at least 3.

We now can give the proof of Theorem 2.1.

Proof of Theorem 2.1 Let G be a 3-connected eulerian graph having no Petersen minor. First suppose G contains edges of multiplicity at least 3. Since G is 3-connected and eulerian, the end vertices of these edges have degree at least 6. So if we remove two edges from an edge of multiplicity at least 3, the remaining graph is still 3-connected and eulerian. Moreover, a removable circuit in the smaller graph is certainly removable in the original graph. So we can assume that G has only edges of multiplicity 1 or 2. By Theorem 2.4, there exists a circuit decomposition L of G such that every circuit in L has length at least 3. By Lemma 2.3, there are two circuits in L that are removable in G, proving the theorem.

2.5 Remark By applying and extending the ideas used in the proofs of the Claims 1, 2, and 3 in the proof of Theorem 3.1 below, we may replace in Theorem 2.1 the hypothesis that G is 3-connected with the weaker hypothesis that G is 2-connected with minimum degree at least 4.

3 The general case

In order to eliminate the minimum degree condition in Theorem 1.6, we extend slightly the definition of a removable circuit; a circuit C in G is removable if G − E(C) is the union of a 2-connected graph with a ( possibly empty ) set of isolated vertices. A digon is a circuit of length two. A digon C in G is lonely if exactly two edges in G join the two vertices of C. A circuit is good in G if it is removable in G and not a lonely digon.

The following result immediately implies Theorem 1.6.

3.1 Theorem Let G be a 2-connected graph different from a circuit and having no Petersen minor. Suppose G has exactly k ∈ {0, 1} vertices of degree 3. Then there exist 2 − k edge-disjoint good circuits in G.

We denote by d_{G}(v) the degree of a vertex v in graph G, and denote by v_{i}(G) the number of vertices in G having degree i. An edge cut is the set of edges δ(X) having exactly one end vertex in X, for some X ⊆ V (G) with Ø ≠ X ≠ V (G); a k-edge cut is an edge cut having cardinality k. Where convenient, we sometimes identify a circuit by its edge set.

Proof of Theorem 3.1 Suppose the theorem is false, and let H be a counterexample for which |E(H)| is minimum.

Claim 1 H has no 2-edge cut.

Proof Suppose that δ(X_{1}) = {e, f} is a 2-edge cut in H. Since H is 2-connected and not a circuit, e and f are not parallel. Thus the graph H′ obtained from H by contracting e is loopless and satisfies the hypothesis of the theorem with v_{3}(H′) ≤ v_{3}(H). By the minimality of H, H′ has 2 − v_{3}(H′) edge-disjoint good circuits. Expansion of e transforms these circuits into at least 2 − v_{3}(H) edge-disjoint circuits which are each removable in H. Since H is a counterexample, one of these circuits, say C_{1}, is a lonely digon in H. This can happen only if each of the two edges g, h of C_{1} induce a triangle with {e, f} and e ∩ f is a vertex of degree 2 in H. Thus D_{1} = {e, f, g} is a circuit which is good in H. As H is a counterexample, we have v_{3}(H) = 0 and thus H′ has a second removable circuit which corresponds to a removable circuit C_{2} in H. The circuit C_{2} is edge-disjoint from C_{1} and cannot be a lonely digon. If C_{2} is edge-disjoint from D_{1}, then we are done. So we may assume that C_{2} contains e and f. But now C_{2} − {e, f} + g is a good circuit in H edge-disjoint from D_{1}, a contradiction. □

Note that in particular Claim 1 implies that H has no vertex of degree 2.

Claim 2 H has no pair y ∈ V (H), e ∈ E(H) such that H − y − e is disconnected.

Proof Suppose that y, e is such a pair. Let X_{1}, X_{2} ⊆ V (H) be such that |X_{1}|, |X_{2}| ≥ 2, X_{1} ∪ X_{2} = V (H), X_{1} ∩ X_{2} = {y}, and e is the unique edge in H with an end vertex in X_{1} \ {y} and an end vertex in X_{2} \ {y}. By Claim 1, H[X_{1}] and H[X_{2}] contain at least 2 edges. For i = 1, 2, let x_{i} denote the end vertex of e in X_{i}, and define H_{i} to be the graph obtained from H[X_{i}] by adding a new vertex u_{i} and two new edges u_{i}y and u_{i}x_{i}. By Claim 1, at least two edges join y to other vertices in X_{i}, so d_{H}(y) ≥ 4 and d_{H_{i}}(y) ≥ 3, i = 1, 2. To obtain a contradiction, it suffices to show for i = 1, 2 that if no vertex in V (H_{i}) \ {y} has degree 3 in H_{i}, then H[X_{i}] contains a circuit which is good in H. Suppose v_{3}(H_{i}) = 0. Since H is 2-connected, H_{i} is 2-connected and satisfies the hypothesis of the theorem. By the minimality of H, H_{i} has 2 edge-disjoint good circuits. One of these two circuits does not contain u_{i}, and is therefore removable in H. By construction of H_{i}, this circuit is not a lonely digon and is thus good in H, a contradiction. Thus we may assume v_{3}(H_{i}) = 1 and d_{H_{i}}(y) = 3. By the minimality of H, H_{i} has a good circuit. Since this circuit does not contain y, it is removable in H. Again, by construction of H_{i}, this circuit is a good circuit in H, a contradiction. □

Claim 3 H is 3-connected.

Proof Suppose {x, y} is a vertex cut in H. Let X_{1}, X_{2} ⊆ V (H) be such that |X_{1}|, |X_{2}| ≥ 3, X_{1} ∪ X_{2} = V (H), X_{1} ∩ X_{2} = {x, y}, and no edge of H has an end vertex in X_{1} \ {x, y} and an end vertex in X_{2} \{x, y}. Applying Claim 2, at least two edges join x to a vertex in X_{i} \{x, y}, i = 1, 2. A similar statement holds for y. Let H′ be the graph obtained from H by deleting all edges joining x to y. Then d_{H′}(x), d_{H′}(y) ≥ 4 and so v_{3}(H′) = v_{3}(H). The hypothesis of the theorem is satisfied by H′. If H′ ≠ H, then by minimality, there are 2 − v_{3}(H) edge-disjoint good circuits in H′. These circuits are also good in H, a contradiction. Thus we have shown that

(1) H has no edge joining x to y.

For i = 1, 2, we define H_{i} to be the graph obtained from H[X_{i}] by adding two new edges e_{i}, f_{i}, each joining x to y. For i = 1, 2 we have d_{H_{i}}(x), d_{H_{i}}(y) ≥ 4, so H_{i} satisfies the hypothesis of the theorem, and has strictly fewer edges than H has. Furthermore, v_{3}(H_{1})+v_{3}(H_{2}) = v_{3}(H) ≤ 1, so we may assume v_{3}(H_{1}) = 0 and v_{3}(H_{2}) = v_{3}(H). Thus H_{i} has 2 − v_{3}(H_{i}) good circuits, i = 1, 2. We have three observations regarding these 4 − v_{3}(H) circuits in H_{1} ∪ H_{2}. First, by (1), none of these circuits contains more than one edge from {e_{1}, f_{1}, e_{2}, f_{2}}. Secondly, if any one of these circuits does not contain any of e_{1}, f_{1}, e_{2}, f_{2}, then that circuit is also good in H. Thirdly, if one of these circuits, say D_{1}, contains exactly one of e_{1}, f_{1} and another of these circuits, say D_{2}, contains exactly one of e_{2}, f_{2}, then D_{1} ∪ D_{2} − {e_{1}, f_{1}, e_{2}, f_{2}} is good in H. Applying these three observations to the 4 − v_{3}(H) circuits obtained above, one can construct in all cases 2 − v_{3}(H) edge-disjoint good circuits in H, achieving the desired contradiction.

□

In what follows, an edge e = uv of H is called an (a, b)-edge if d_{H}(u) = a and d_{H}(v) = b.

Claim 4 H has no (a, b)-edge with a, b ≥ 5.

Proof If e is such an edge, then, since H is 3-connected, H − e satisfies the hypothesis with v_{3}(H − e) = v_{3}(H). By the minimality of H, H − e has 2 − v_{3}(H − e) edge-disjoint good circuits. Each of these circuits is also good in H, a contradiction. □

Claim 5 H has no edge of multiplicity greater than 2.

Proof Suppose that u, v ∈ V (H) are joined by at least three edges. By Claim 3, u and v each have at least two neighbors in V (H) \ {u, v}, so d_{H}(u), d_{H}(v) ≥ 5, contradicting Claim 4.

□

Claim 6 H has no (3, b)-edge with b ≥ 5.

Proof If e = uv is such an edge and d_{H}(u) = 3, then H − e satisfies the hypothesis with v_{3}(H − e) = v_{3}(H) − 1 = 0. By minimality, H − e has two good circuits. At least one of these circuits does not contain u; this circuit is good in H, a contradiction. □

Claim 7 H has no (3, 4)-edge.

Proof Suppose e = uv is such an edge where d_{H}(u) = 3. Then H − e satisfies the hypothesis with v_{3}(H − e) = v_{3}(H) = 1. By minimality, H − e has a good circuit C. If C does not contain u, then C is good in H, a contradiction. Thus we assume u ∈ V (C). We distinguish two cases.

Case 1 : C contains a vertex w with d_{H}(w) ≥ 5. Let P be a u, w-path in C and assume that w has been chosen such that every vertex in V (P) \ {u, w} has degree 4 in H. Since C is removable in H − e, and therefore removable in H, the graph H′ = H − E(P) is 2-connected and satisfies the hypothesis of the theorem with v_{3}(H′) = v_{3}(H) − 1 = 0. By the minimality of H, H′ contains two edge-disjoint good circuits. Since d_{H′}(u) = 2, one of these two circuits, say C_{1}, does not contain u. One easily checks that C_{1} is a good circuit in H.

Case 2 : Every vertex in V (C) \ {u} has degree 4 in H. Let f = ux be an edge of C incident with u and let P be the path C − f. Again the graph H′ = H − E(P) satisfies the hypothesis of the theorem, but now v_{3}(H′) = v_{3}(H) = 1. By the minimality of H, H′ has a good circuit C_{1}. Since d_{H′}(x) = 3 and d_{H′}(u) = 2, C_{1} does not contain x and therefore C_{1} does not contain u. This implies that C_{1} is a good circuit in H.

In either case we contradict H being a counterexample, proving Claim 7. □

Claim 8 H is 4-regular.

Proof By Claims 1, 6 and 7, H has minimum degree 4 and thus v_{3}(H) = 0. Suppose e is a (4, b)-edge with b ≥ 5. Then H − e satisfies the induction hypothesis with v_{3}(H − e) = 1, so H − e contains a good circuit C. One easily checks that C is good in H. We aim to find two edge-disjoint good circuits in H. It is possible that neither of them will equal C. We consider three cases.

Case 1 : C contains two distinct vertices v, w with d_{H}(v), d_{H}(w) ≥ 5. Let P be a v, w-path in C and assume that all vertices in V (P) \ {v, w} have degree 4 in H. Since C is removable in H, the graph H′ = H − E(P) satisfies the hypothesis of the theorem with v_{3}(H′) = v_{3}(H) = 0. By the minimality of H, H′ has two edge-disjoint good circuits, and these two circuits are also edge-disjoint and good in H.

Case 2 : C contains exactly one vertex w with d_{H}(w) ≥ 5. Let e = wv be an edge of C incident with w and let P = C − e. Then H − E(P) satisfies the hypothesis of the theorem with v_{3}(H′) = v_{3}(H) + 1 = 1. Thus H′ contains a good circuit C′, and this circuit is also good in H. Since d_{H′}(v) = 3, C′ does not contain e, and so C′ is edge disjoint from C. Hence C and C′ are edge-disjoint good circuits in H.

Case 3 : All vertices in C have degree 4 in H. Let H′ = H − E(C). Since C is removable in H, H′ is 2-connected and satisfies the hypothesis with v_{3}(H′) = v_{3}(H) = 0. Thus H′ has two edge-disjoint good circuits C_{1}, C_{2}. We claim that one of these is removable, and hence good in H. As C_{1}, C_{2} and C are edge-disjoint in H, and d_{H}(v) = 4 for each v ∈ V (H), each vertex in C is belongs to at most one of C_{1}, C_{2}. Since C is not a lonely digon, Claim 5 implies that C has length at least 3. Therefore either C_{1} or C_{2}, say C_{1}, satisfies |V (C) \ V (C_{1})| ≥ ⌈\frac{1}{2} |V (C)|⌉ ≥ 2. Thus there are at least two distinct vertices in C which belong to the non-trivial 2-connected component of H′ − E(C_{1}). It follows that H − E(C_{1}) has exactly one non-trivial component, and this component is 2-connected. Thus C_{1} is removable in H as claimed, and C, C_{1} are edge-disjoint good circuits in H.

In each case we have contradicted H being a counterexample, and Claim 8 is proved. □

The theorem now follows immediately from Claims 3 and 8 and Theorem 2.1.

4 Remarks

This section contains some relevant examples, conjectures and extensions.

4.1 Some examples

The connectivity requirement in Lemma 2.3 is necessary. For example, the graph of Figure 2 has four distinct circuit decompositions into circuits of length at least three. In each of these

[figure]

Figure 2 A 2-connected graph containing circuit decompositions in which every circuit has length at least 3, but containing no removable circuit of length at least 3.

decompositions L, the hypergraph H_{L} is a circuit with multiple edges so no circuit in L is removable. In fact, the graph has no removable circuits at all except for lonely digons.

Conversely, Figure 3 depicts an eulerian graph which has a removable circuit of length at least three, even though every circuit decomposition must use a lonely digon.

If G is a graph having no good circuit ( in the sense of Theorem 3.1 ), then we may obtain a graph having no removable circuit at all by replacing all lonely digons with two lonely digons which are “in series”, in the manner of the graph of Figure 1. An alternative view is to replace each lonely digon in G with an edge of weight 2. This raises a more general problem.

4.1 Problem Which 2-connected edge-weighted graphs (G, p), p : E → {1, 2, …}, have a circuit C such that G − (E(C) ∩ p^{−1}(1)) is 2-connected ?

[figure]

Figure 3 A 2-connected graph containing no circuit decomposition in which all circuits have length at least 3, but containing a removable circuit ( shown in bold ) of length at least 3.

A faithful circuit cover of an edge-weighted graph (G, p) is a list of circuits such that each e ∈ E(G) is in exactly p(e) of the circuits in the list. A strengthened form of Lemma 2.3 holds here. We omit the proof as it is similar to that of Lemma 2.3, with regard to Remark 2.5, and using the more general statement of Theorem 2.4 found in [1].

4.2 Lemma Suppose (G, p) has a faithful circuit cover, where G is 2-connected and has no Petersen minor. Then (G, p) has a faithful circuit cover (C_{1}, C_{2}, …, C_{k}) such that, for each i = 1, 2, …, k, C_{1} ∪ C_{2} ∪ ⋯ ∪ C_{i} is a 2-connected subgraph of G.

This result cannot be extended to graphs which have Petersen minors, as demonstrated by the graph of Figure 4. However, it could be the case that the conclusion holds true for all 3-connected weighted graphs (G, p) which have a faithful circuit cover.

4.2 Petersen Conjectures

We denote by P the 4-regular multigraph obtained from Petersen’s graph by duplicating each of the five edges in one of its 1-factors. It is clear that P plays a central role in the examples in the previous subsection. This observation and a lack of counterexamples tempt us to venture the following.

Figure 4 A 2-connected edge-weighted graph ( thin edges have weight 1, bold edges have weight 2 ) having a faithful circuit cover, but no faithful circuit cover that satisfies the properties in Lemma 4.2.

4.3 Conjecture If G is a 3-connected graph with minimum degree at least 4 and G has no removable circuit different from a lonely digon, then G is isomorphic to P or may be obtained from copies of P via repeated applications of the graph composition operation depicted in Figure 5.

[figure: G_{1}; G_{2}; G]

Figure 5 If neither G_{1} nor G_{2} has a removable circuit different from a lonely digon, then neither has G.

An apparently weaker conjecture seems to contain much of the difficulty of Conjecture 4.3. This unpublished conjecture was posed by Goddyn [5], and is weaker than a conjecture of Fleischner and Jackson ( see Conjecture 12 in [2] ).

Let σ be a permutation of {1, …, n}. A σ-prism is the graph obtained from two disjoint circuits (v_{1}v_{2} ⋯ v_{n}v_{1}), (u_{1}u_{2} ⋯ u_{n}u_{1}) by adding a digon between vertices v_{i} and u_{σ(i)}, for i = 1, …, n.

4.4 Conjecture Let H be a σ-prism with n ≥ 2 having no removable circuit different from a digon. Then H ≅ P.

Conjecture 4.4, which we call the “Prism Conjecture”, is known to hold true whenever the underlying simple graph of H is 3-edge colorable or has no Petersen minor [1]. Little else appears to be known regarding Conjecture 4.4.

4.3 Complexity

Determining whether a graph contains a Petersen minor can be done in polynomial time [12], so there exists a polynomial time algorithm to decide whether a given graph satisfies the hypothesis of Theorem 3.1. By our results we know that such a graph contains a removable circuit. On the other hand, the complexity of the following problem is unknown.

(P1) Given a 2-connected graph G with minimum degree at least 4 and containing no Petersen minor, find a circuit C such that G − E(C) is 2-connected.

This is in contrast to the published proofs of Theorems 1.1, 1.3 and 1.5, all of which translate to polynomial time algorithms for finding removable circuits.

It is the application of Theorem 2.4 which hinders a conversion of the proof of Theorem 3.1 into a polynomial algorithm for (P1). More precisely, the proof of Theorem 3.1 entails a polynomial reduction of (P1) to the following construction problem for Theorem 2.4.

(P2) Given a 3-connected 4-regular graph G containing no Petersen minor, find a decomposition of G into circuits of length at least 3.

However, (P2) is of unknown complexity [1]. Circumventing this problem appears to require a completely different proof of Theorem 2.1.

4.4 Extension to matroids

J. Oxley proposed the following problem in [10] ( see this book for definitions and notation ). The cogirth of a matroid M is the minimum cardinality of a cocircuit in M.

4.5 Problem ( Oxley [10, (14.4.8)] ) Let M be a simple connected binary matroid having cogirth at least 4. Does M have a circuit C such that M \ C is connected ?

For graphic matroids, Problem 4.5 is answered in the affirmative by any of the Theorems 1.1 to 1.3. In fact, the condition “having cogirth at least 4” translates to the condition “is 4-edge connected” for graphs, which means that the conditions in Problem 4.5 for graphs are more restrictive than those in Theorem 1.1.

For cographic matroids, Problem 4.5 translates as follows. A circuit T in M^{∗}(G) corresponds to a bond ( a minimal edge cut ) in G. The matroid M^{∗}(G) \ T is connected if and only if either |E(G / T)| = 1 or G / T is loopless and 2-connected. Here G / T denotes the graph obtained from G by contracting all edges in T, but not deleting any resulting multiple edges and loops.

4.6 Problem Let G be a 2-connected, 3-edge connected graph with girth at least 4. Does G contain a bond B such that G / B is 2-connected ?

The answer to Problem 4.6 ( and Problem 4.5 ) is “no” in general. The following counterexample, due to M. Lemos, was communicated to us by J. Oxley in December, 1995. Let H be the complete bipartite graph with vertex partition (X_{1}, X_{2}) where |X_{1}| = |X_{2}| = 5. For i = 1, 2 and for each 3-subset S ⊆ X_{i}, we add to H two new vertices x_{S}, y_{S}, and add a new edge joining each of the six pairs in {x_{S}, y_{S}} × S. Contracting any bond in the resulting graph results in a graph which is not 2-connected.

Extending the main result of this paper to matroids entails removing the word “simple” from Problem 4.5, and removing the requirement “3-edge connected” from Problem 4.6. Here, there is a much smaller cographic counterexample which seems to play a role analogous to that played by the graph P in the graphic case.

Let B be a bond of cardinality six in K_{5}, and let G be the graph obtained from K_{5} by duplicating each edge in E(K_{5}) − B and then subdividing both edges of each resulting digon exactly once. Then G is 2-connected with girth at least 4, but contracting any bond of G leaves a graph which is not 2-connected.

This example inspires the following.

4.7 Conjecture Let G be a 2-connected graph with girth at least 4 and having no minor isomorphic with K_{5}. Then G contains a bond B such that G / B is 2-connected.

More generally, we ask the following.

4.8 Question What is the largest minor-closed class of matroids such that every connected matroid M in this class having cogirth at least 4 has a circuit C such that M \ C is connected ?

There is a construction similar to the one preceding Conjecture 4.7 which involves the dual Fano F_{7}^{∗} ( this time B is a cocircuit of size 4 and we perform a series and parallel extension on the elements of F_{7}^{∗}−B). Also, the uniform matroid U_{2,5} has no removable circuit. This suggests that M^{∗}(K_{5}), F_{7}^{∗}, U_{2,5} and Petersen’s graph should be excluded minors for Question 4.8. This list appears to be related to the list of excluded minors for binary matroids having the “circuit cover property” as given in [4].

The “dual” problems, obtained by replacing “circuit” with “cocircuit” in Problems 4.5 and 4.8, appear to have a completely different quality. For example, P. Seymour ( see [9, Lemma 6] ) has shown that a connected binary matroid M of girth and cogirth at least 3 has a cocircuit B such that M \ B is connected.

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] H. Fleischner, Some blood, sweat, but no tears in Eulerian graph theory, Congressus Numerantium 63 (1988) 8–48.

[3] H. Fleischner and B. Jackson, Removable cycles in planar graphs, J. London Math. Soc. (2) 31 (1985) 193–199.

[4] X. Fu and L. A. Goddyn, Matroids with the circuit cover property, Submitted to European J. Combin.

[5] L. A. Goddyn, Cycle double covers–current status and new approaches, Contributed lecture, Cycle Double Cover Conjecture Workshop, IINFORM, Vienna, January 1991.

[6] A.M. Hobbs, Personal communication (1995).

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

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

[9] J.G. Oxley, Cocircuit coverings and packings for binary matroids, Math. Proc. Camb. Phil. Soc. 83 (1978) 347–351.

[10] J.G. Oxley, “Matroid theory”, Oxford University Press, Oxford (1992).

[11] N. Robertson, Letter to A.M. Hobbs. Dated August 25, 1975.

[12] P. Seymour and N. Robertson, Graph minors. XIII . The disjoint paths problem, J. Combin. Theory Ser. B 63 (1995) 65–110.

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