Graphic matroid

In the mathematical theory of matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the forests in a given finite 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 sometimes called a planar matroid (but this should not be confused with matroids of rank 3, which generalize planar point configurations); these are exactly the graphic matroids formed from planar graphs.

Definition 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 A {\displaystyle A} and B {\displaystyle B} are both independent, and A {\displaystyle A} is larger than B {\displaystyle B} , then there is an element x ∈ A ∖ B {\displaystyle x\in A\setminus B} such that B ∪ { x } {\displaystyle B\cup \{x\}} remains independent. If G {\displaystyle G} is an undirected graph, and F {\displaystyle F} is the family of sets of edges that form forests in G {\displaystyle G} , then F {\displaystyle F} is clearly closed under subsets (removing edges from a forest leaves another forest). It also satisfies the exchange property: if A {\displaystyle A} and B {\displaystyle B} are both forests, and A {\displaystyle A} has more edges than B {\displaystyle B} , then it has fewer connected components, so by the pigeonhole principle there is a component C {\displaystyle C} of A {\displaystyle A} that contains vertices from two or more components of B {\displaystyle B} . Along any path in C {\displaystyle C} from a vertex in one component of B {\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 B {\displaystyle B} to produce a forest with more edges. Thus, F {\displaystyle F} forms the independent sets of a matroid, called the graphic matroid of G {\displaystyle G} or M ( G ) {\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. The bases of a graphic matroid M ( G ) {\displaystyle M(G)} are the full spanning forests of G {\displaystyle G} , and the circuits of M ( G ) {\displaystyle M(G)} are the simple cycles of G {\displaystyle G} . The rank in M ( G ) {\displaystyle M(G)} of a set X {\displaystyle X} of edges of a graph G {\displaystyle G} is r ( X ) = n − c {\displaystyle r(X)=n-c} where n {\displaystyle n} is the number of vertices in the subgraph formed by the edges in X {\displaystyle X} and c {\displaystyle c} is the number of connected components of the same subgraph. The corank of the graphic matroid is known as the circuit rank or cyclomatic number.

… excerpt ends here. Continue reading the full article.