Graphic matroid

In matroid theory, a discipline within mathematics, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the forests in a given undirected graph. The dual matroids of graphic matroids are called co-graphic matroids or bond matroids. A matroid that is both graphic and co-graphic is called a planar matroid; these are exactly the graphic matroids formed from planar graphs.

A matroid may be defined as a family of finite sets (called the "independent sets" of the matroid) that is closed under subsets and that satisfies the "exchange property": if sets ${\displaystyle A}$ and ${\displaystyle B}$ are both independent, and ${\displaystyle A}$ is larger than ${\displaystyle B}$, then there is an element ${\displaystyle x\in A\setminus B}$ such that ${\displaystyle B\cup \{x\}}$ remains independent. If ${\displaystyle G}$ is an undirected graph, and ${\displaystyle F}$ is the family of sets of edges that form forests in ${\displaystyle G}$, then ${\displaystyle F}$ is clearly closed under subsets (removing edges from a forest leaves another forest). It also satisfies the exchange property: if ${\displaystyle A}$ and ${\displaystyle B}$ are both forests, and ${\displaystyle A}$ has more edges than ${\displaystyle B}$, then it has fewer connected components, so by the pigeonhole principle there is a component ${\displaystyle C}$ of ${\displaystyle A}$ that contains vertices from two or more components of ${\displaystyle B}$. Along any path in ${\displaystyle C}$ from a vertex in one component of ${\displaystyle B}$ to a vertex of another component, there must be an edge with endpoints in two components, and this edge may be added to ${\displaystyle B}$ to produce a forest with more edges. Thus, ${\displaystyle F}$ forms the independent sets of a matroid, called the graphic matroid of ${\displaystyle G}$ or ${\displaystyle M(G)}$. More generally, a matroid is called graphic whenever it is isomorphic to the graphic matroid of a graph, regardless of whether its elements are themselves edges in a graph.

...
Wikipedia