What Is a Matroid? A Visual Introduction

Linear algebra has independent vectors. Graph theory has acyclic edge sets (forests). These two ideas look unrelated, yet they obey the same abstract rules. A matroid is exactly that abstraction.

Definition

A matroid is a pair $M = (E, \mathcal{I})$ where $E$ is a finite ground set and $\mathcal{I}$ is a family of subsets of $E$ called independent sets, satisfying three axioms:

(I2) is the hereditary property: any subset of an independent set is independent. (I3) is the exchange property, and it is the heart of the structure — it forces every maximal independent set to have the same size.

The graphic matroid

The cleanest example takes $E$ to be the edges of a graph and calls a set of edges independent when it contains no cycle (i.e. it is a forest). The visualization below builds one greedily: edges that keep the set acyclic are added, edges that would close a cycle are rejected.

Bases, rank, and circuits

Three derived notions describe any matroid:

• A basis is a maximal independent set. By the exchange axiom, all bases share the same cardinality. For the graphic matroid of a connected graph, a basis is a spanning tree.
• The rank $r(M)$ is that common size. A graph on $n$ vertices has rank $n - 1$.
• A circuit is a minimal dependent set. In the graphic matroid, a circuit is exactly a cycle.

In the example above, $B = \{e_1, e_2, e_3\}$ is a basis, the rank is $3$, and both $\{e_1, e_2, e_3, e_4\}$ and $\{e_1, e_2, e_5\}$ contain a circuit.

Why matroids matter: the greedy theorem

Matroids are not just a tidy generalization — they pin down precisely when greed pays off. Assign a weight to each element of $E$ and run the greedy algorithm: sort elements, then add each one whenever it keeps the set independent.

Rado–Edmonds theorem. For a hereditary set system $(E, \mathcal{I})$, the greedy algorithm returns a maximum-weight basis for every weight function if and only if $(E, \mathcal{I})$ is a matroid.

Applied to the graphic matroid this is exactly Kruskal’s algorithm for the minimum spanning tree. The reason Kruskal works is not luck — it is that forests form a matroid. $\blacksquare$