The University of Montana
Mathematical Sciences Colloquium

* Big Sky Conference on Discrete Mathematics

Around 1975, A.M. Hobbs asked whether every 2-connected multigraph G with minimum degree at least four contains a circuit C such that G-E(C) is still 2-connected. A positive answer to this question would imply the Cycle Double Cover Conjecture. The answer is "no" in general due to an example involving Petersen's graph and multiple edges. The answer is "yes" for simple graphs (Mader, Jackson) and planar multigraphs (Fleischner, Jackson). In joint work with Jan van den Heuvel and Sean McGuinness, we show:

A 2-connected multigraph G with minimum degree at least four and containing no Petersen graph as a minor, contains two edge-disjoint circuits C such that G-E(C) is 2-connected.

An obvious question is "How far can the above result be generalised to matroids?" In particular:

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

For cographic matroids, the question above is equivalent to:

Which 2-connected graphs with girth at least four have a bond (a minimal edge-cut) B such that the graph resulting from contracting all edges in B is still 2-connected?

With Jan van den Heuvel, we show that all graphs which are not contractible to K₅ have this property. There are interesting issues regarding the complexity of finding such a removable circuit.

Colloquium home | Mathematical Sciences home | The University of Montana home