In 1937, Wagner proved that a graph is planar if and only if it has neither K5 nor K3,3 as a minor, where one obtains a minor of a graph by a sequence of deletions or contractions of edges or deletion of vertices. Thus, Wagner proved that {K5,K3,3} is the set of excluded minors for the class of planar graphs. A celebrated result of Robertson and Seymour proves the far-reaching extension of Wagner’s Theorem that, for every class of graphs that is closed under taking minors, the set of excluded minors is finite.
Whitney introduced matroids to abstractly capture the notion of linear dependence. For example, from every matrix, one obtains a matroid whose elements are the matrix’s column labels and whose independent sets are the linearly independent sets of columns. In particular, the vertex-edge incidence matrix of a graph, interpreted over the 2-element field, gives rise to a graphic matroid. Like graphs, matroids have substructures called minors; these are obtained by a sequence of deletions and contractions of elements. Unlike graphs, matroids have numerous minor-closed subclasses that cannot be characterized by a finite set of excluded minors. Indeed, precisely which natural classes of matroids have such a characterization is unknown. It has been announced that, for a fixed field, the set of matroids that arise from matrices over that field has a finite set of excluded minors exactly when the field is finite, although the proof of this result has yet to appear. In 1959, Tutte proved that the class of graphic matroids has five excluded minors. The class of bicircular matroids is another well-studied and natural class of matroids arising from graphs. Specifically, the bicircular matroid of a graph is the matroid on the edge set of the graph where a set I of edges is independent exactly when there is a corresponding set of |I| distinct vertices such that each edge meets its corresponding vertex. This paper proves that the class of bicircular matroids can be characterized by a finite set of excluded minors.