Graphic Matroid

graph-theory discrete-mathematics combinatorics

Definition

Graphic Matroid

A graphic matroid (also called a cycle matroid) is a matroid $M=(E,\mathcal{I})$ whose ground set $E$ is the edge set of an undirected graph $G=(V,E)$, and whose independent sets are the acyclic edge sets, that is, the forests:

$$\mathcal{I}=\{X\subseteq E\mid (V,X)\text{ is acyclic}\}.$$

Why the axioms hold

• Non-emptiness: the empty edge set is acyclic.
• Heredity: a subgraph of a forest is a forest.
• Exchangeability: if $|X|<|Y|$ with both forests, then $Y$ has fewer connected components than $X$; some edge of $Y$ joins two components of $X$ without creating a cycle, so $X\cup \{e\}$ is acyclic.