Matroids and the Greedy Algorithm

The axioms of a matroid, the graphic matroid, the optimality theorem for the greedy algorithm, a reinterpretation of MST algorithms, and matroid intersection.

Folio Official

March 1, 2026

1 Definition of a Matroid

Definition 1 (Matroid).

A matroid is a pair

M = (E, I)

consisting of a finite set

E

and a collection

I \subseteq 2^{E}

of subsets satisfying three axioms:

(I1) Nonemptiness: $\emptyset \in I$ .
(I2) Hereditary property: If $I \in I$ and $J \subseteq I$ , then $J \in I$ .
(I3) Augmentation property: If $I, J \in I$ and $∣ I ∣ < ∣ J ∣$ , then there exists $e \in J ∖ I$ such that $I \cup {e} \in I$ .

The elements of

I

are called independent sets.

Remark 2.

The augmentation property (I3) abstracts the following fact from linear algebra: if

dim (span (I)) < dim (span (J))

, then

J

contains a vector that can be added to

I

while preserving linear independence.

2 The Graphic Matroid

Definition 3 (Graphic matroid).

For a graph

G = (V, E)

, the graphic matroid (or cycle matroid) is

M (G) = (E, I)

, where

I = {F \subseteq E ∣ (V, F) is acyclic}

Theorem 4.

M (G)

is a matroid.

Proof.

(I1): The empty edge set

(V, \emptyset)

has no cycles, so

\emptyset \in I

(I2): If

F

is acyclic and

F^{'} \subseteq F

, then

F^{'}

is also acyclic. Heredity holds.

(I3): Let

I, J \in I

with

∣ I ∣ < ∣ J ∣

. The subgraph

(V, I)

is a forest with

∣ I ∣

edges and

∣ V ∣ - ∣ I ∣

connected components. Similarly,

(V, J)

has

∣ V ∣ - ∣ J ∣

components. Since

∣ V ∣ - ∣ J ∣ < ∣ V ∣ - ∣ I ∣

, the forest

(V, J)

has fewer components than

(V, I)

It follows by the pigeonhole principle that some edge

e \in J ∖ I

connects two vertices that lie in different components of

(V, I)

. Adding

e

I

does not create a cycle, so

I \cup {e} \in I

. □

Definition 5 (Rank function).

For a matroid

M = (E, I)

, the rank of a subset

S \subseteq E

r (S) = max {∣ I ∣ ∣ I \subseteq S, I \in I} .

The quantity

r (E)

is the rank of

M

. For the graphic matroid,

r (E) = ∣ V ∣ - c

, where

c

is the number of connected components.

3 Optimality of the Greedy Algorithm

Definition 6 (Optimization over a matroid).

Given a matroid

M = (E, I)

and a weight function

w : E \to R_{\geq 0}

, the goal is to find a basis (maximal independent set) that maximizes (or minimizes)

w (I) = \sum_{e \in I} w (e)

Theorem 7 (Optimality of the greedy algorithm (Rado, 1957; Edmonds, 1971)).

Let

M = (E, I)

be a matroid and

w : E \to R_{\geq 0}

a weight function. Sort the elements of

E

in nonincreasing order of weight:

w (e_{1}) \geq w (e_{2}) \geq \dots \geq w (e_{m})

. The greedy algorithm

I_{0} = \emptyset, I_{k} = {I_{k - 1} \cup {e_{k}} I_{k - 1} if I_{k - 1} \cup {e_{k}} \in I, otherwise,

produces an independent set

I_{m}

with

w (I_{m}) = max {w (I) ∣ I \in I}

Proof.

Let

I^{*} \in I

be a maximum-weight independent set, and suppose

I_{m}

is not optimal. Denote the elements chosen by the greedy algorithm as

a_{1}, a_{2}, \dots, a_{r}

(with

w (a_{1}) \geq \dots \geq w (a_{r})

), and list the elements of

I^{*}

in nonincreasing weight order as

b_{1}, b_{2}, \dots, b_{s}

Let

j

be the first index with

w (a_{j}) < w (b_{j})

(if no such index exists, then

w (I_{m}) \geq w (I^{*})

). Set

J = {b_{1}, \dots, b_{j}}

and

I = {a_{1}, \dots, a_{j - 1}}

. Then

∣ I ∣ < ∣ J ∣

and both

I, J \in I

. By the augmentation property (I3), there exists

b_{k} \in J ∖ I

with

I \cup {b_{k}} \in I

. Since

w (b_{k}) \geq w (b_{j}) > w (a_{j})

and

b_{k}

was not among

a_{1}, \dots, a_{j - 1}

, the greedy algorithm should have chosen

b_{k}

before or at step

j

(as

b_{k}

appears before

a_{j}

in the weight-sorted order and

I \cup {b_{k}}

is independent). This contradicts the behavior of the greedy algorithm. □

4 The Converse

Theorem 8 (Characterization of matroids by the greedy algorithm).

Let

E

be a finite set and

I

a hereditary family with

\emptyset \in I

. If the greedy algorithm produces an optimal solution for every weight function

w : E \to R_{\geq 0}

, then

(E, I)

is a matroid.

Proof.

We prove the contrapositive. Suppose

(E, I)

is not a matroid, i.e., the augmentation property (I3) fails. Then there exist

I, J \in I

with

∣ I ∣ < ∣ J ∣

such that

I \cup {e} \in / I

for every

e \in J ∖ I

Define the weight function:

w (e) = 1 + ε

for

e \in I

w (e) = 1

for

e \in J ∖ I

, and

w (e) = 0

otherwise, where

ε > 0

is sufficiently small. The greedy algorithm selects the elements of

I

first (they have the largest weights), after which no element of

J ∖ I

can be added. This gives

w (I_{m}) \leq ∣ I ∣ (1 + ε)

. On the other hand,

w (J) = ∣ I \cap J ∣ (1 + ε) + ∣ J ∖ I ∣ \geq ∣ J ∣ > ∣ I ∣ (1 + ε)

for sufficiently small

ε

. The greedy algorithm is therefore not optimal. □

5 Kruskal's Algorithm Revisited

Remark 9.

Given a connected graph

G = (V, E)

with positive edge weights

w : E \to R_{> 0}

, Kruskal's algorithm for finding a minimum spanning tree (MST) sorts the edges in nondecreasing weight order and greedily adds each edge that does not create a cycle.

This is precisely the greedy algorithm on the graphic matroid

M (G)

, optimizing the weight function

w^{'} = - w

(equivalently, sorting in nondecreasing order corresponds to maximizing the negative weight, i.e., minimizing the original weight). The optimality theorem for the greedy algorithm therefore provides a clean proof that Kruskal's algorithm correctly computes the MST.

graph TD
    A["Matroid (E, I)"] --> B["Graphic Matroid"]
    A --> C["Linear Matroid"]
    A --> D["Uniform Matroid"]
    B --> E["Kruskal = Greedy"]
    C --> F["Linear Independence"]
    E --> G["MST"]

6 Matroid Intersection

Definition 10 (Matroid intersection).

Given two matroids

M_{1} = (E, I_{1})

and

M_{2} = (E, I_{2})

on the same ground set

E

, the matroid intersection problem asks for a largest set belonging to

I_{1} \cap I_{2}

Theorem 11 (Matroid intersection theorem (Edmonds, 1970)).

max {∣ I ∣ ∣ I \in I_{1} \cap I_{2}} = S \subseteq E min (r_{1} (S) + r_{2} (E ∖ S)),

where

r_{1}

and

r_{2}

are the rank functions of

M_{1}

and

M_{2}

, respectively.

Remark 12.

Matroid intersection provides a unifying framework for many combinatorial optimization problems, including bipartite matching (which arises as the intersection of two partition matroids) and arborescences. The intersection of two matroids is solvable in polynomial time, but the intersection of three or more matroids is NP-hard in general. Matroid intersection thus marks a sharp boundary between tractability and intractability in combinatorial optimization.

Graph Theory Discrete Mathematics Textbook Matroids Greedy Algorithm Minimum Spanning Trees

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·105 articles

Matroids and the Greedy Algorithm

1 Definition of a Matroid

2 The Graphic Matroid

3 Optimality of the Greedy Algorithm

4 The Converse

5 Kruskal's Algorithm Revisited

6 Matroid Intersection

Share your expertise with the world

More from Folio Official

Monetizing Your Articles — How to Earn Revenue Safely with Stripe Connect

Mastering Theorem Environments — theorem, definition, proof, and Friends

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry