On Connectivity in Matroids and Graphs

Abstract

In this paper we derive several results for connected matroids and use these to obtain new results for 2-connected graphs.In particular, we generalize work of Murty and Seymour on the number of two-element cocircuits in a minimally connected matroid, and work of Dirac, Plummer and Mader on the number of vertices of degree two in a minimally 2-connected graph.We also solve a problem of Murty by giving a straightforward but useful characterization of minimally connected matroids.The final part of the paper gives a matroid generalization of Dirac and Plummer's result that every minimally 2-connected graph is 3-colourable.

Locations

• Transactions of the American Mathematical Society - View - PDF