On the interplay between graphs and matroids

Summary

Abstract

“If a theorem about graphs can be expressed in terms of edges and circuits only it probably exemplifies a more general theorem about matroids.” This assertion, made by Tutte more than twenty years ago, will be the theme of this paper. In particular, a number of examples will be given of the two-way interaction between graph theory and matroid theory that enriches both subjects.

Introduction

This paper aims to be accessible to those with no previous experience of matroids; only some basic familiarity with graph theory and linear algebra will be assumed. In particular, the next section introduces matroids by showing how such objects arise from graphs. It then presents a minimal amount of theory to make the rest of the paper comprehensible. Throughout, the emphasis is on the links between graphs and matroids.

Section 3 begins by showing how 2-connectedness for graphs extends naturally to matroids. It then indicates how the number of edges in a 2-connected loopless graph can be bounded in terms of the circumference and the size of a largest bond. The main result of the section extends this graph result to matroids. The results in this section provide an excellent example of the two-way interaction between graph theory and matroid theory.

In order to increase the accessibility of this paper, the matroid technicalities have been kept to a minimum. Most of those that do arise have been separated from the rest of the paper and appear in two separate sections, 4 and 10, which deal primarily with proofs. The first of these sections outlines the proofs of the main results from Section 3.