Graphic Matroid

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}\}.$$

Proof

Forests satisfy the matroid axioms

Let $G=(V,E)$ be a finite undirected graph and let $\mathcal{I}$ be its family of acyclic edge sets. We verify the three matroid axioms. Every subgraph below retains all vertices of $V$, including isolated vertices.

Non-emptiness: select no edges

The graph $(V,\varnothing )$ has no edges, hence no cycle. Thus $\varnothing \in \mathcal{I}$, proving non-emptiness.

Heredity: removing edges cannot create a cycle

Let $Y\in \mathcal{I}$ and $X\subseteq Y$. Any cycle in $(V,X)$ would use only edges of $X$, hence only edges of $Y$. This would contradict $Y\in \mathcal{I}$. Therefore $X\in \mathcal{I}$, proving heredity.

Exchangeability: find an edge joining different components

Fix any $X,Y\in \mathcal{I}$ with $|X|<|Y|$. These are two separate forests on the same vertices: $Y$ has more edges, but need not contain $X$. We need just one edge $e\in Y\setminus X$ that can be added to $X$ without creating a cycle; we are not adding all of $Y$ to $X$.

Such an edge must join two different connected components of $(V,X)$. Within one component, its endpoints are already joined by a path of $X$-edges, so adding the edge would close a cycle. The task is therefore to show that not all edges of $Y$ can stay inside the components of $X$.

Both rows start with the same forest $X$. The dashed boundaries show its components before the orange edge is added. In the top row, $a$ can already reach $c$ through $b$. In the bottom row, there is no path from $c$ to $d$ until the new edge is added.

Count the edges already inside each component

Let $V_1,\dots ,V_t$ be the vertex sets of the components of $(V,X)$. These sets partition $V$. Each component is a tree, so on $|V_i|$ vertices it has exactly $|V_i|-1$ edges. Consequently,

$$|X|=\sum _{i=1}^t\underset{\text{edges of }X\text{ in }{V}_i}{\underbrace{(|V_i|-1)}}.$$

An isolated vertex is a component too: it contributes $1-1=0$ edges.

In the diagrams, $ab$ abbreviates the undirected edge $\{a,b\}$. The dashed boundaries will remain fixed: they describe the components of $X$, not those of $Y$.

Assume that no edge of $Y$ crosses between components of $X$

Given: $X,Y$ are forests on the same vertices, with $|Y|>|X|$. The sets $V_1,\dots ,V_t$ remain the vertex groups determined by $X$.

Assume for contradiction: no $Y$-edge crosses between these groups:

$$\forall \{u,v\}\in Y\exists i\in \{1,\dots ,t\}:u,v\in V_i.$$

Different edges may lie in different groups. We will compare their counts inside each group, then add them.

This picture illustrates only the no-crossing assumption, not $|Y|>|X|$. The proof will show that both requirements cannot hold together.

Compare the two edge counts inside one fixed group

Fix any $i\in \{1,\dots ,t\}$. Write

$$\begin{array}{rl}{X}_i& =\{\{u,v\}\in X:u,v\in V_i\},\\ Y_i& =\{\{u,v\}\in Y:u,v\in V_i\}.\end{array}$$

Both use the same $V_i$, the vertices of the $i$-th component of $(V,X)$; $Y_i$ need not be a subset of $X_i$.

• $(V_i,X_i)$ is a tree: connected by the choice of $V_i$, acyclic because $X$ is a forest. Hence $|X_i|=|V_i|-1$.
• The graph $(V_i,Y_i)$ is a forest: any cycle in it would already lie in $Y$.

Restrict $(V,Y)$, not $G$: keep the vertices of the $X$-component $V_i$ and only the $Y$-edges between them. Here $X$ uses $ab,bc$, while $Y$ uses $ac$. We compare them separately; adding $ac$ to $X$ would create a cycle.

To count $Y_i$, start with $|V_i|$ isolated vertices and insert its edges. Each edge merges two components: joining already connected vertices would create a cycle. Thus each insertion reduces the component count by one.

These dashed outlines show the changing components while inserting $Y_i$, not the fixed components of $X$.

Let $k_i$ count the final components, including isolated vertices. Since $V_i\ne \varnothing$, $k_i\ge 1$. The forest edge count gives:

$$\begin{array}{rlrl}{k}_i& =\underset{\text{initial components}}{\underbrace{|V_i|}}-\underset{\text{merges}}{\underbrace{|Y_i|}},& & \\ |Y_i|& =|V_i|-k_i,& & \\ & \le |V_i|-1& & \text{because }{k}_i\ge 1,\\ & =|X_i|& & \text{because }(V_i,X_i)\text{ is a tree}.\end{array}$$

Local consequence: $|Y_i|\le |X_i|$ for every $i$. Being less connected only reduces the edge count. This bound uses acyclicity, not the no-crossing assumption.

Add the internal counts: there is no room for more edges than $X$

Use the contradiction assumption here:

• No crossing edges $\Rightarrow$ every $Y$-edge belongs to some $Y_i$.
• Disjoint vertex groups $\Rightarrow$ no edge belongs to two different $Y_i$.

Therefore $Y_1,\dots ,Y_t$ partition $Y$, so $|Y|={\sum }_i|Y_i|$. Without the first premise, crossing edges would be missing from the sum.

Add the local inequalities, then identify the totals. Every $X$-edge is internal by definition:

$$\begin{array}{rl}|Y_1|& \le |X_1|,\\ & ⋮\\ |Y_t|& \le |X_t|,\\ \underset{|Y|\text{ by no crossing}}{\underbrace{\sum _{i=1}^t|Y_i|}}& \le \underset{|X|\text{ by definition}}{\underbrace{\sum _{i=1}^t|X_i|}}.\end{array}$$

Counting edges in the pictured groups

Fixed vertex group	Edges of $X$ inside it	Maximum edges of a forest inside it
$V_1=\{a,b,c\}$	$2$	$2$
$V_2=\{d,e\}$	$1$	$1$
$V_3=\{f\}$	$0$	$0$
Total	$3$	$3$

A forest with more than three edges cannot put all its edges inside these groups. Changing which internal edges it uses cannot increase any of the bounds in the last column.

Contradiction: $|Y|\le |X|$, but the premise is $|Y|>|X|$.

Consequence: some $Y$-edge crosses between components of $X$. The next picture illustrates this conclusion with four edges, rather than the earlier two-edge illustration of the restriction.

Here $Y$ is the path $a-c-d-e-f$ together with the isolated vertex $b$. The internal edges need not agree with $X$: $ac$ replaces $ab,bc$ inside $V_1$. What matters is the bound on their number, not which edges are shared.

Add a crossing edge without closing a cycle

Choose such an edge $e=\{u,v\}\in Y$. Since $u$ and $v$ lie in different components of $(V,X)$, $e\notin X$. Thus $e\in Y\setminus X$.

If adding $e$ created a cycle, that cycle would have to use $e$, because $X$ is acyclic. Removing $e$ from the cycle would leave a path from $u$ to $v$ using only edges of $X$. But then $u$ and $v$ would already lie in the same component of $(V,X)$, a contradiction. Hence

$$X\cup \{e\}\in \mathcal{I}.$$

This proves exchangeability. Despite its name, this axiom only adds an edge to $X$; it does not require removing one.

All three axioms hold, so $(E,\mathcal{I})$ is a matroid.