Bicircular Matroid

In the mathematical subject of matroid theory, the bicircular matroid of a graph G is the matroid B(G) whose points are the edges of G and whose independent sets are the edge sets of pseudoforests of G, that is, the edge sets in which each connected component contains at most one cycle. The circuits, or minimal dependent sets, of this matroid are the bicircular graphs (or bicycles, but that term has other meanings in graph theory); these are the theta graph, consisting of three paths joining the same two vertices but not intersecting each other, the figure eight graph (or tight handcuff), which consists of two cycles having just one common vertex, and the loose handcuff (or barbell), which consists of two disjoint cycles and a minimal connecting path. All these definitions apply to multigraphs, i.e., they permit multiple edges (edges sharing the same endpoints) and loops (edges whose two endpoints are the same vertex).

The bicircular matroid was introduced by Simões-Pereira and explored further by Matthews and others. It is a special case of the frame matroid of a biased graph.

Bicircular matroids can be characterized as the transversal matroids that arise when no point belongs to more than two sets. A transversal presentation in terms of a point set and a class of subsets comes directly from the graph. The points of the presentation are the edges. There is one set for each vertex, and it consists of the edges which have that vertex as an endpoint.

The closed sets (flats) of the bicircular matroid of a graph G can be described as the forests F of G such that in the induced subgraph in V(G) − V(F), every connected component has a cycle. Since the flats of a matroid form a geometric lattice when partially ordered by set inclusion, these forests of G also form a geometric lattice. Their partial ordering is that F₁ ≤ F₂ if

• each component tree of F₁ is either contained in or vertex-disjoint from every tree of F₂ and
• each vertex of F₂ is a vertex of F₁.

For the most interesting example, let G o be G with a loop added to every vertex. Then the flats of B(G o) are all forests of G, spanning or nonspanning; thus, all forests of a graph G form a geometric lattice, the forest lattice of G (Zaslavsky 1982).