chapter  6.6
27 Pages

Matroidal Methods in Graph Theory

WithJames Oxley

Every graph gives rise to a matroid so every theorem for matroids has an immediate consequence for graphs, although many of these are easy to derive directly. On the other hand, numerous results for graphs have analogs or generalizations to matroids. This link between graph theory and matroid theory is so close that the famous graph theorist W. T. Tutte (1917–2002) wrote [Tu79]: “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 section provides an overview of the rich interaction between graph theory and matroid theory.