# Matroids

How to contact me.

Back to the
Graph
Theory Index

Base *B*,
Circuit *C*,
Closure *σ*,
Greedy *G*,
Independence *I*,
Rank *r*,
Rank *r'*,
Transversal Matroid.

## Matroids (Notes from a previous class)

There are several definitions of *matroids*
We shall examine some of these
with an eye to showing their equivalence.
We have in class already seen a few
applications, including that fact that matroids are effectively those
structures on which greedy algorithms work.
To keep the definitions separate,
we shall refer to the variants as *C*-matroids,
*B*-matroids,
*r*-matroids,
*s*-matroids, etc.
The theorems will
show that we are really talking about the same types of objects.

Base *B*,
Circuit *C*,
Closure *σ*,
Greedy *G*,
Independence *I*,
Rank *r*,
Rank *r'*.

**Definition**. An *I-matroid*
is a finite set *S* and a collection
*I* of subsets of *S* (called *indepedent sets*) such that
axioms (I1)-(I3) are satisfied.

(I1) *{ } ∈ I*;

(I2) if *X ∈ I* and *Y ⊆ X*, then
*Y ∈ I*; and

(I3) if *U,V ∈ I* with
*|U| = |V|+1*, then there is an
*x ∈ U \ V*
such that *V ∪ {x} ∈ I*.

In class, I gave (I1), (I2), (I3)':

(I3)' if *U,V ∈ I* with
*|U| > |V|*, then there is an
*x ∈ U \ V*
such that *V ∪ {x} ∈ I*.

It is immediately obvious that (I1), (I2), (I3)' are equivalent to
(I1), (I2), (I3).
There is a third definition
involving
independence.

Base *B*,
Circuit *C*,
Closure *σ*,
Greedy *G*,
Independence *I*,
Rank *r*,
Rank *r'*.

The other structure we studied was:

**Definition**.
A *G-matroid M=(S,F)* is a finite set
*S* and a non-empty collection *F* of subsets of *S*
satisfying the
following two conditions:

(G1) if *X ∈ F* and *Y ⊆X*,
then *Y ∈ F*; and

(G2) for any function *w* from *S* to
the set of non-negative real numbers,
the greedy algorithm
applied to *(F,w)* returns a maximum weight element of *F*.

We showed, in class, that (G1), (G2) are equivalent to (I1), (I2),
(I3). Thus we have the following theorem.

**Theorem**.
An *I*-matroid is a *G*-matroid, and conversely.

Base *B*,
Circuit *C*,
Closure *σ*,
Greedy *G*,
Independence *I*,
Rank *r*,
Rank *r'*.

We now introduce some of the other parameters.
A *base* of a matroid *M=(S,I)* is a maximal independent set.
We use
*B(M)* or *B* for the set of bases of *M*.

**Definition**.
A *B-matroid M=(S,B)* is a finite set *S*
and a non-empty collection of subsets *B* of *S* satisfying:

(B1) If *B*_{1}, B_{2} ∈ B and
*x ∈ B*_{1} \ B_{2}, then
there is some
*y ∈ B*_{2} \ B_{1} such that
*(B*_{1} \ {x}) ∪ {y} ∈ B.

**Theorem**. An *I-matroid M=(S,I)* is a *B-matroid*.

**Proof**.
For the collection *B* we use the collection of bases of *M*. (This is obviously non-empty.)

If *B*_{1},B_{2} ∈ B
and *x ∈ B*_{1} \ B_{2}, then
*B*_{1} \ {x} ∈ I and
*B*_{2} ∈ I and
*|B*_{1} \ {x}|=|B_{2}| − 1.
Hence, by axiom (I3) there is a
*y ∈ B*_{2} \ (B_{1}\{x}) = B_{2} \ B_{1}
such that
*(B*_{1}\{x}) ∪ {y} ∈ I.
But, *|(B*_{1} \ {x}) ∪ {y}|=|B_{2}|.
If *(B*_{1} \ {x}) ∪ {y} is not maximal,
then it is a subset of
some base *B*_{3} with
*|B*_{3}| > |B_{2}|
and an application of (I3) shows
that *B*_{2} can be augmented, contradicting the maximality of
*B*_{2}.
Hence, *(B*_{1} \ {x}) ∪ {y}
is maximal,
and thus *(B*_{1} \ {x}) ∪ {y} ∈ B.

**Lemma**. All bases in a *B*-matroid have the same cardinality.

**Proof.**. Let *B*_{1},B_{2} ∈ B with
*|B*_{1}| ≠ |B_{2}|, but,
subject to this, with *|B*_{1} ∩ B_{2}|
as large as possible.
Suppose that there is some
*x ∈ B*_{1} \ B_{2}.
Then by (B1) there is an element
*y ∈ B*_{2} \ B_{1} such that
*B*_{3} = (B_{1} \ {x}) ∪ {y} ∈ B.
But, *|B*_{3}| = |B_{1}| ≠ |B_{2}| and
*|B*_{3} ∩ B_{2}| > |B_{1} ∩ B_{2}|,
which is a contradiction.
Thus, *B*_{1} \ B_{2} = { }.
Similarly, *B*_{2} \ B_{1} = { } .
Therefore,
*|B*_{1}| = |B_{2}|, contradicting the assumption that
*|B*_{1}| ≠ |B_{2}|.

**Theorem**. A *B*-matroid *M=(S,I)* is an *I*-matroid.

**Proof**. We define *I* in the natural way:
*I* is the collection of all subsets of elements of *B*.
It is obvious that (I1) and (I2) are satisfied, and we need only prove (I3).
Let *U,V ∈ I* with
*|U| = |V| + 1*.
Then, *U* is a subset of some
*B*_{2} in *B* and
*V* is a subset of some *B*_{1} in *B*,
where we choose *|B*_{1} ∩ B_{2}| as large as
possible.

If *B*_{1}=B_{2},
then any *y ∈ U \ V* will satisfy
*V ∪ {y} ∈ I*.

Thus, we assume that *B*_{1} ≠ B_{2}.
Let *x ∈ B*_{1} \ V.
Suppose that *x ∉ B*_{2}.
Then, there is some
*y ∈ B*_{2} \ B_{1} such
that
*B*_{3} = (B_{1} \ {x}) ∪ {y} ∈ B.
However,
*V ⊆ B*_{3},
*U ⊆ B*_{2} and
*|B*_{3} ∩ B_{2}| > |B_{1} ∩ B_{2}|,
violating the choice of *B*_{1} and
*B*_{2}. Hence, *B*_{1} \ V is a subset of
*B*_{2}.
Since *U ⊆ B*_{2},
and *|B*_{1}| = |B_{2}| (from the Lemma),
we derive:

*|U ∩ (B*_{1} \ V)| =
|U| + |B_{1} \ V| − |U ∪ (B_{1} \ V) | ≥
|V| + 1 + |B_{1} \ V| − |B_{2}|
= |B_{1}| + 1 - |B_{2}| = 1.

Let *y ∈ U ∩ (B*_{1} \ V) ⊆ U \ V, then
*V ∪ {y} ⊆ B*_{1} ∈ I.
Therefore, (I3) is satisfied and *(S,I)* is an
*I*-matroid.

**Exercise**.
Let *M=(S,I)* be an *I*-matroid.
Define *B* as above.
In the proof of the theorem,
we constructed another set
which we might call *I(B)*. Show that
*I=I(B)*, thus the process of converting an
*I*-matroid to a *B*-matroid
and then back to an *I*-matroid
actually returns us to the original matroid.
(The reader should do a similar verification
for each of the theorems showing
equivalency.)

**Theorem**.
Suppose that *M=(S,B)* is a
*B*-matroid. Then,

(B2) If *B*_{1}, B_{2} ∈ B and
*y ∈ B*_{2} \ B_{1}, then
there is an *x ∈ B*_{1} \ B_{2}
such that
*(B*_{1} \ {x}) ∪ {y} ∈ B.

**Proof**.
Since *M* is a *B*-matroid, the collection
*I* of subsets of elements of *B* is the
collection of independent sets of an *I'*-matroid.
Therefore *{y} ⊆ B*_{2} ∈ I, *{y} ∈ I*, and
since *B*_{1} is an independent set,
repeated use of axiom
(I3)' yields an independent set *K* with *y ∈ K ⊆ B*_{1} ∪ {y},
and with *|K| = |B*_{1}|. Thus,
*K* must be a maximal independent set,
and hence, *K* is a base.
But *K = (B*_{1} \ {x}) ∪ {y}, for
some *x ∈ B*_{1}, completing the proof.

**Example**.
We list all of the non-isomorphic matroids on
at most 4 elements.
We do this by listing the possible choices for *B*.

Suppose *S* is the empty set.

Then the only possible base is:

*B*_{1}={{ }}.

Suppose *S={a}*.

The choices for *B* are

(1) *B*_{1}={{a}} and

(2) *B*_{2}={{ }}.

Suppose *S={a,b}*.

The choices for *B* are

(1) *B*_{1}={{a,b}},

(2) *B*_{2}={{a},{b}},

(3) *B*_{3}={{a}} and

(4) *B*_{4}={{ }}.

Suppose *S={a,b,c}*.

The choices for *B* are

(1) *B*_{1}={{a,b,c}},

(2) *B*_{2}={{a,b},{a,c},{b,c}},

(3) *B*_{3}={{a,b},{a,c},},

(4) *B*_{4}={{a,b}},

(5) *B*_{5}={{a},{b},{c},},

(6) *B*_{6}={{a},{b}},

(7) *B*_{7}={{a}}, and

(8) *B*_{8}={{ }}.

Suppose *S={a,b,c,d}*.

The choices for *B* are

(1) *B*_{1}={{a,b,c,d}},

(2) *B*_{2}={{a,b,c},{a,b,d},{a,c,d},{b,c,d}},

(3) *B*_{3}={{a,b,c},{a,b,d},{a,c,d}},

(4) *B*_{4}={{a,b,c},{a,b,d}},

(5) *B*_{5}={{a,b,c}},

(6) *B*_{6}={{a,b},{a,c},{a,d},{b,c},{b,d},{c,d}},

(7) *B*_{7}={{a,b},{a,c},{a,d},{b,c},{b,d}},

(8) *B*_{8}={{a,c},{a,d},{b,c},{b,d}},

(9) *B*_{9}={{a,b},{a,c},{b,c}},

(10) *B*_{10}={{a,b},{a,c},{a,d}},

(11) *B*_{11}={{a,b},{a,c}},

(12) *B*_{12}={{a,b}},

(13) *B*_{13}={{a},{b},{c},{d}},

(14) *B*_{14}={{a},{b},{c}},

(15) *B*_{15}={{a},{b}},

(16) *B*_{16}={{a}}, and

(17) *B*_{17}={{ }}.

**Exercise**.
Let *G* be a graph and recall that a forest *F* of
*G* is an acyclic subgraph of *G*.
Prove that the collection *I* of edge sets of forests of *G* is the
collection of independent sets of a matroid and that the maximal spanning
forests of *G* are bases of the matroid.

**Definition**.
A *B*-matroid
*M=(S,B)* is *graphic* if there exists a graph *G*
with edge set *S*
such that *B* is the collection of maximal
edge sets of *G* which do not support a cycle of *G*.

**Definition**.
The *dual* of a *B*-matroid
*M=(S,B)* is the structure
*M*=(S,B*)*, where
*B*={S \ X: X ∈ B}*.
By (B2),
*M** is, in fact, a matroid.
We will also show (later) that the matroid
associated with the dual of a planar graph
is the dual of the matroid of the graph,
thereby justifying the name.

**Definition**.
A *cographic matroid* is the dual of a graphic matroid.

All of the matroids for *|S| < 4* are graphic.
For *|S| = 4*, all but one are graphic.
The matroid, *U*_{4,2},
determined by the sixth basis, *B*_{6},
in the example,
is neither graphic nor cographic.
We will also see that a matroid is both graphic and
cographic if and only if it
is the matroid of a planar graph.

All of the matroids with *|S| ≤ 4* are transversal.

**Exercise**.
Let *|S|=n*. Let *B* be a non-empty
collection of subsets of *S* each of cardinality *n-1*.
Prove that
*(S,B)* is a matroid.

Base *B*,
Circuit *C*,
Closure *σ*,
Greedy *G*,
Independence *I*,
Rank *r*,
Rank *r'*.

The *rank function* of a
matroid *M=(S,I)* is a function
*r* from the set of subsets of *S* to the set of integers,
defined by

*r(A)=*max*{|X|:X* a subset of *A* and *X* in *I}*,
for every subset *A* of *S*.

The *rank of the matroid M*, denoted *r(M)*, is the rank of *S*.

**Definition**.
An *r*-matroid M=(S,r) is a finite set *S*
and a function *r* from the set of subsets of *S* to
the set of integers such that
for every subset *X* of *S*
and every *y,z* in *S*,
the following three conditions
are satisfied:

(R1) *r({ })=0*;

(R2) *r(X) <= r(X* union *{y}) <= r(X)+1*;
and

(R3) if
*r(X* union *{y})=r(X* union *{z})=r(X)*,
then
*r(X* union *{y,z})=r(X)*.

**Theorem**.
An *I*-matroid is an *r*-matroid.

**Proof**.
We take
*r(A)=*max*{|X|:X* a subset of *A* and *X* in *I}*,
for every subset *A* of *S*,
as defined previously.
Let *X* be a subset of *S*
and let *y,z* be elements of *S*.

(R1): The only independent subset of *{ }* is
*{ }*.
Therefore, *r({ })=0*.

(R2): Let *U* be a subset of *X*
such that *U* is in *I* and
*|U|=r(X)*.
Then *U* is a subset of *X* union *{y}*.
Hence, *r(X* union *{y}) >= |U|=r(X)*.
Now let *V* be a subset of *X* union *{y}*
such that *V* is in *I* and
*|V|=r(X* union *{y})*.
Then *V*_{1}=V\{y} is a
subset of *X* and *V*_{1} is in *I*.
Therefore,
*r(X)+1 >= |V*_{1}| +1 >= |V| = r(X union *{y})*.

(R3): Suppose that
*r(X* union *{y}) = r(X* union *{z}) = r(X)*
From (R2), which we have just proved, we know that
*r(X* union *{y,z}) >= r(X* union *{y}) = r(X)*.
Thus, *r(X* union *{y,z}) >= r(X)*.

Suppose that *r(X* union *{y,z}) > r(X)*.
Let *U* be a subset of *X* union *{y,z}*
such that *U* is in *I* and
*|U| = r(X* union *{y,z})* and let
*V* be a subset of *X*
such that *V* is in *I* and
*|V|=r(X)*.
Then, *|U|>|V|*.
By (I3)', there is an element *b* in
*U\V*, which is a subset of *X* union *{y,z}*, such that
*V* union *{b}* is in *I*.
However, *b* is not in *X*, since this would force
*V* union *{b}* to be a subset of *X*,
Therefore, *b=y* or *b=z*. If *b=y*, then
*V* union *{b}* is a subset of *X* union *{y}*
and
*|V| + 1 = |V* union *{b}| <= r(X* union *{y})=r(X)=|V|*.
Hence, *b* cannot be *y*. Similarly, *b* cannot be *z*.
This is a contradiction.

Base *B*,
Circuit *C*,
Closure *σ*,
Greedy *G*,
Independence *I*,
Rank *r*,
Rank *r'*.

**Lemma**.
Let *M=(S,r)* be an *r*-matroid. Let
*X* be a subset of *S*.
Then *r(X) <= |X|*.

**Proof**.
Let *k=|X|* and
let *X={x*_{1},x_{2},...,x_{k}}.
Let *X*_{0}={ } and *X*_{i}={x_{1},x_{2},...,x_{i}} for
*1 <= i <= k*.
Then *r(X*_{0})=0 and *r(X*_{i}) <= r(X_{i}\{x_{i}})+1 for
*1 <= i <= k*.
It follows, by induction, that *r(X*_{i}) <= i.
Therefore, *r(X) = r(X*_{k}) <= k = |X|.

**Lemma**.
Let *M=(S,r)* be an *r*-matroid. Let *X* be
a subset of *Y*.
Then *r(X) <= r(Y) <= r(X) + |Y\X|*.

**Proof**.
Let *k=|Y\X|* and
let *Y\X={x*_{1},x_{2},...,x_{k}}. Let
*X*_{0}=X and *X*_{i}=X union *{x*_{1},...,x_{i}} for
*a <= i <= k*.
Then *r(X*_{i-1}) <= r(X_{i}) <=
r(X_{i-1})+1 for
*a <= i <= k*.
It follows, by induction, that
*r(X) <= r(X*_{i}) <= r(X)+i.
Therefore, *r(X) <= r(Y) <= r(X)+|Y\X|*.

**Theorem**.
An *r*-matroid is an *I*-matroid.

**Proof**.
Let *I={A: A* is a subset of *S* and *|A|=r(A)}*.

(I1): Since *r({ })=0=|{ }|*,
it follows that *{ }* is in *I*.

(I2): Let *X* be in *I*. Then *r(X)=|X|*.
Suppose that *Y* is a subset of *X*
but that *Y* is not in *I* and,
subject to this, assume
that *Y* is as large as possible.
Now, *X\Y* cannot be *{ }*.
Let *x* be an element of *X\Y*.
Then *Y* union *x* is in *I*.
Hence, *r(Y)+1 < |Y|+1 = |Y* union *{x}| = r(Y* union *{x})
=r(Y)+1*.

(I3): Let *U,V* be sets in *I* with
*|U|=|V|+1*.
Suppose that *r(V* union *{y}) = r(V)*
for every element *y* of *U\V*.
Let *U\V = Y = {y*_{1},y_{2},...,y_{k}}.

I sketch the remainder of the argument.
Prove, inductively, that
*r(V* union *Y') = r(V)*, for each subset *Y'*
of *Y*.
For *|Y'|=1*, this is just *k(k-1)/2* applications of
(R3). Now let *X* be an *i-1* element extension of
*V*, the previous inductive step shows that
r(X union *{y})=r(X* union *{z})=r(X)*,
for each choice of
*y,z* in *Y/X*, since these are just
*i* element extensions.
By (R3),
*r(X* union *{y,z})=r(X)*. This proves that all *i+1*
element extensions have rank *R(V)*.
But *r(V* union *Y >= r(U) > r(V)* provides the contradiction.

Base *B*,
Circuit *C*,
Closure *σ*,
Greedy *G*,
Independence *I*,
Rank *r*,
Rank *r'*.

**Definition**.
An *r'-matroid M=(S,r')*
is a finite set *S*
and a function *r'* from the set of subsets of
*S* to the set of integers
such that
for every pair of subsets *X,Y* of *S*
the following three conditions
are satisfied.

(R1)' *0 <= r'(X) <= |X|*;

(R2)' if *X* is a subset of *Y*, then
*r'(X) <= r'(Y)*; and

(R3)' * r'(X* union *Y) +
r'(X* intersect *Y) <= r'(X) + r'(Y)*.

**Theorem**. An *r*-matroid
*M=(S,r)* is an *r'*-matroid.

**Proof**.

We set r'=r.

(R1)' Previous Lemma.

(R2)' Previous Lemma.

(R3)' Note that *M* is an *I*-matroid,
and thus we may also use properties
(I1), (I2), (I3).
Let *X,Y* be subsets of *S*.
Choose an independent set *U* in
*X* intersect *Y*, such that *U* is
as large as possible.
Now, choose an independent set *U* union *V*
in *X*,
such that *U* union *V* is as large as possible.
Finally,
choose an independent set
*U* union *V* union *W*
in *X* union *Y*,
such that *U* union *V* union *W*
is as large as possible. Then,
*r(X* intersect *Y) = |U|*,
*r(X) = |U* union *V|*,
*r(X* union *Y) =
|U* union *V* union *W|*, and
*r(Y) >= |U* union *W|*.

Therefore,
*r(Y) >= |U* union *W| =
|U* union *V* union *W| +
|U| - |U* union *V|* =
r(X union *Y) + r(X* intersect *Y) - r(X)*.
This completes the proof.

Base *B*,
Circuit *C*,
Closure *σ*,
Greedy *G*,
Independence *I*,
Rank *r*,
Rank *r'*.

A subset *A* of *S* is *closed* or a
*flat* or a *subspace* of
*M* if for all elements *x* of *S\A*,
*r(A* union *{x}) = 1+r(A)*.
If *x* is an element of *S* and
*A* is a subset of *S* and
*r(A* union *{x}) = r(A)*
we say that *x*
depends on *A* and write *x ~ A*.
For a subset *A* of *S*,
let *σ(A) = {x : x ~ A}*.
We call *σ(A)* the *closure* of
*A*.

**Definition**.
A *σ-matroid M=(S,σ)*
is a finite set *S*
and a function *σ:2*^{S}→2^{S}
such that
for every pair of subsets *X,Y ⊆ S*
and for every pair of elements *x,y ∈ S*
the following four conditions
are satisfied.

(S1) *X ⊆ S(X)*;

(S2) if *Y ⊆ X*, then
*σ(Y) ⊆ σ(X)*;

(S3) *σ(X)=σ(σ(X))*; and

(S4) if *y ∉ σ(X)*
and *y ∈ σ(X ∪ {x})*, then
*x ∈ σ(X ∪ {y})*.

**Theorem**.
A *σ*-matroid is an *I*-matroid, and conversely.

Base *B*,
Circuit *C*,
Closure *σ*,
Greedy *G*,
Independence *I*,
Rank *r*,
Rank *r'*.

**Definition**. A *circuit* of a matroid
*M=(S,r)* is a subset of *S* such that
*r(X) < |X|*, but *r(Y)=|Y|*, for
every subset *Y* of *X*.

**Definition**.
A *C-matroid M=(S,C)*
is a finite set *S* and a collection of
subsets *C* of *S* such that the
following two conditions are satisfied.

(C1) if *X* and *Y* are in *C* and
*X* is a subset of *Y*, then
then *X=Y*; and

(C2) if *X* and *Y* are distinct elements of *C*
and *z* is an element of *X* intersect *Y*,
then there exists an element *Z* in *C*
such that *z* is not in *Z* and *Z* is a
subset of
*X* union *Y*.

**Theorem**.
A *C*-matroid is an *I*-matroid, and conversely.

**Example** (Transversal Matroids).
Let *G* be a bipartite graph with bipartition *(X,Y)*.
We say a vertex *x ∈ X* is *saturated* by a matching *M* if
*x* is incident with some edge of *M*.
Let *F(M)* denote the set of all vertices of *X* saturated by *M*.
We will call *F(M)*
*transversal-independent*.
Let *J* denote the set of all transversal-independent subsets of *X*.
It is obvious that *(X,J)* satisfies axioms (I1) and (I2).

To prove (I3), let *A,B ∈ J*, with *|A| < |B|*.
As above, let *M*_{C} be a matching such that
*F(M*_{C}) = C,
for *C = A,B*.
Now, let *H* be the graph with vertex set *V(G)* and
edge set *M*_{A} ∪ M_{B}.
Using one iteration of
the standard augmenting-path proof
of Hall's theorem, starting with the matching
*M*_{A}, results in a matching
*M* with *|M| = |M*_{A}| + 1 and with
*F(M) = F(A) ∪ {f}*, for some *f ∈ X − A*.
But, the only vertices of *X* with
positive degree in *H* lie in *A ∪ B* and,
hence, *f ∈ B − A*.
Thus, (I3) is satisfied.

**Exercise**. The reader is invited to verify that all matroids on five or fewer elements are transversal-matroids.

**Exercise**. Find a matroid that is not a transversal-matroid. (Hint: the number of elements is not less than six.)

**Exercise**. Find a matroid that is neither a graphic matroid nor a transversal-matroid.

For the next result, *N(Z)* denotes the set of neighbours of *Z* in the graph under discussion.
The sequence of Lemmas is suggested in the text by Gordon and McNulty.
(I'm neither looking up original sources, nor claiming that their proof is not original.)

**Lemma**. Let *M=(X,I)* be a transversal matroid derived from the bipartite graph *G* with bipartition
*(X,Y)*. Suppose that *C* is a circuit of *M*. Then,
*|N(C)| = |C| − 1 = r(C)*.

**Proof**. (We already know that *r(C) = |C| − 1*.)
If *Z ⊆ C* and
*Z ≠ C*,
then *Z* is independent and there is a matching of *G*
saturating *Z*. Hence,
*|N(Z)| ≥ |Z|*.
The special case *|C \ Z| = 1* yields
*|N(C)| ≥ |N(Z)| ≥ |Z| = |C| − 1*.
On the other hand, if *|N(C)| ≥ |C|* as well,
then the subgraph *G'* of *G* induced by
*C ∪ Y* would satisfy
the conditions of Hall's theorem, *G'* would have a matching saturating *C*, and that matching would saturate
*C* in *G*. Thus, *|N(C)| ≤ |C| − 1* and, hence,
*|N(C)| = |C| − 1*.

**Lemma**. Let *M=(X,I)* be a transversal matroid derived from the bipartite graph *G* with bipartition
*(X,Y)*. Suppose that *B* is a base of *M*. Let *F* be a matching of *G* saturating *B*, and let
*W* denote the set of vertices of *Y* saturated by *F*. Then,
for any *x ∈ X \ B*,
*N(x) ⊆ W*.

**Proof**. Let *C* be a circuit in *B ∪ {x}*. Note that
*x ∈ C*. Let *F'* be the subset of *F* saturating
*C \ {x}* and let *Z* denote the set of vertices of *Y* saturated by *F'*. Hence,
*N(C) ⊇ N(C \ {x}) ⊇ Z*. Thus,
*|C| − 1 = |N(C)| ≥ |N(C \ {x})| ≥ |Z| = |C| − 1*. This forces
*N(x) ⊆ N(C) = N(C \ {x}) = Z ⊆ W*.

**Lemma**. Let *M=(X,I)* be a transversal matroid derived from the bipartite graph *G* with bipartition
*(X,Y)*. Suppose that *M* has no coloops (isthmuses) and that *B* is a base of *M*.
Let *F* be a matching of *G* saturating *B*, and let
*W* denote the set of vertices of *Y* saturated by *F*. Then,
for any *x ∈ B*,
*N(x) ⊆ W*.

**Proof**.
Since *x* is not a coloop, *x* is in some circuit *C* of *M*.
We may assume that we have chosen *C* so that
*|C \ B|* is as as small as possible.

Let *x' ∈ C \ B*. Then, *B ∪ {x'}* contains a circuit *C'*. If *x ∈ C'*, then
*|C' \ B| = * and we have the circuit we want. So, suppose that *x ∉ C'*. Now,
*x' ∈ C ∩ C'* and *x ∉ C'*. By an extension of (C2), there is a circuit
*C'' ⊆ (C ∩ C') \ {x'}* with *x ∈ C''*. But,
*C \ B ⊆ (C \ B) \ {x'}*, violating the choice of *C*.
Hence, *x* is in a basic (fundamental) circuit *C* of *M*, with respect to the base *B*.
That is, *C ⊆ B ∪ {x'}*,
*|N(C)| = |C| − 1*,
and *C \ {x}* is independent. Let
*F'* be the subset of *F* saturating *C \ {x'}* and
let *W'* denote the subset of *Y* saturated by *F'*.
But now, *N(x) ⊆ N(C − {x'}) ⊆ W' ⊆ W*.

**Lemma**. Let *M=(X,I)* be a transversal matroid derived from the bipartite graph *G* with bipartition
*(X,Y)*. Suppose that *M* has no coloops (isthmuses) and that *B* is a base of *M*.
Let *F* be a matching of *G* saturating *B*, and let
*W* denote the set of vertices of *Y* saturated by *F*. Then,
for any *x ∈ X*,
*N(x) ⊆ W*.
Thus, *N(X) = W*, and
*|N(X)| = |W| = r(X)*.

**Proof**. See the two previous lemmata.

**Theorem**. Let *M=(X,I)* be a transversal matroid. There is some bipartite graph *G* with bipartition
*(X,Y)*, where *|Y| = r(X)*, such that the transversal matroid of *G* is *M*.

**Proof**. If *M* has no coloops, this is the result of the previous lemma.
Any representation has *|Y| = r(X)*.

If *M* has coloops, delete them. Find any representation of the new transversal matroid,
and add back one disjoint copy of *K*_{2} for each coloop of *M*.

**Edmonds-Fulkerson Matching Matroids**.
Let *G* be a graph. Let *T* denote the set of matchings of *G*.
For a matching *F*, let *V*_{F} denote the
set of vertices saturated by *F*. Let *S = V(G)* and let *I = {K ⊆ V*_{F} : F ∈ T}.
Then, *M(S,I)* is a matroid.

Before starting the proof, we give a definition of matroid favoured by Edmonds.

**Definition**.
An *I"-matroid M=(S,I)* is a finite set S and
a collection of *independent*
subsets *I* of *S*
satisfying the following three conditions:

(I1) *{ } ∈ I*;

(I2) if *X ⊆ Y* and *Y ∈ I*, then *X ∈ I*; and

(I3)" for every *A ⊆ S*, all maximal independent subsets of *A* have the same
cardinality.

This is equivalent to the standard definition of a matroid in terms of independent sets.
**Proof of equivalence**.

**Proof that the Edmonds-Fulkerson matching matroid is a matroid**.
Properties (I1) and (I2) are trivially satisfied.

To prove (I3)", let *A ⊆ S* and let *X,Y* be maximal independent subsets of *A*.
For any *Z ⊆ S*, let *F*_{Z} denote a matching that saturates the vertices of *Z*, and possible other vertices as well.
Consider the subgraph *N* of *G* with *V(N) = V(G)* and
*E(N) = F*_{X} Δ F_{Y}.
Then, *N* is a disjoint union of paths and even cycles.
The endvertices of the paths in *N*which are also vertices of *A* is the set *X Δ Y*.
Suppose that *|X| > |Y|*. Then, *|X \ Y| > |Y \ X|*. Thus, there is a path *P* in *N*
with one end *v* in *X \ Y* and the other end not in *Y \ X*.
Let *K = F*_{Y} Δ E(P).
Then, *K* is a matching which saturates
*Y ∪ {v} ⊆ A*, violating the choice of *Y*.
Hence, *|X| ≤ |Y|*.
Similarly, *|Y| ≤ |X|* and , *|X| = |Y|*, proving (I3)".

**Representable Matroids**. A matroid *M(S,I)* is *representable* if there is a field **F**,
a matrix *A* with entries from **F**, with *M'(S',I')*
the matroid determined by the columns of *A* under linear independence, and a bijection *f:S→S'* such that
*X ∈ I ⇔ f(X) ∈ I'*.

For example, if *G* is an undirected graph, then the circuit matroid of *G* is representable, since the incidence matrix of *G*
(with each loop represented by a column of zeroes) is a matrix *A* over the field of two elements, with a set of columns of *A* independent preceisely when the corresponding set of edges is independent in the circuit matroid.

A more interesting example is provided by transversal matroids.

**Lemma**. Suppose that *A* is an *n × m* matrix with entries from a field
**F** with *|***F**| ≥ n + 1 and with at least one non-zero entry in each row of *A*. Then, there is a vector
*Z=(z*_{1},...,z_{m}) ∈ **F**^{m} such that every entry of *AZ* is non-zero.

**Proof**. Denote the entry in row *i*, column of *A* by
*a*_{i,j}.
We proceed iteratively. At each stage, *Z*^{(k)} will be a vector such that
*AZ*^{(k)} has a non-zero entry in every entry corresponding to a row with a non-zero entry in one of the first *k* columns.
We may start with any *Z*^{(0)}, but for definiteness, let us start with
*Z*^{(0)} = (0,...,0).

Given *Z*^{(k-1)}, we contruct
*Z*^{(k)} by replacing the element in position *k* of
*Z*^{(k-1)} by a variable
*z*_{k} ∈ **F**. Now,
*AZ*^{(k)} = W + z_{k}Q, for some vectors
W,Q ∈ **F**^{m}.
Let *w*_{i} denote the
i^{th} coördinate of
W + z_{k}Q.
Note that if
*a*_{i,k} = 0,
then the value of *w*_{i} does not depend of
z_{k}.
On the other hand, if
*a*_{i,k} ≠ 0,
then we need to avoid the one value of
z_{k} which would make
*w*_{i} = 0.
This imposes at most *n* forbidden values for
z_{k}.
But, *|***F**| ≥ n + 1. Hence, there is a choice for
z_{k} so that
for every *i*,
*1 ≤ i ≤ n*,
*w*_{i} ≠ 0 if
*a*_{i,j} ≠ 0.
Arbitrarily pick one of these allowable values for
z_{k}, and then
Z^{(k)} has the desired property.

**Proof that Transversal Matroids are Representable**.
Let *M* be a transversal matroid and let *G* be a bipartite graph, with bipartition
*(X,Y)* whose transversal matroid (on the set *X*) is isomorphic to *M*.
Arbitrarily order the elements of *X* and *Y* and let
*A = (a*_{i,j}) be the *|Y| × |X|* matrix such that
*a*_{i,j} = 0 if there is no edge
from
*y*_{i} to
*x*_{j} and
*a*_{i,j} = z_{i,j} if there is an edge
from
*y*_{i} to
*x*_{j}, where
*z*_{i,j} ∈ **F**
is a variable whose value is to be determined later.

We now assign the values for the variables
*z*_{i,j}
beginning with those in column one, and proceeding from one column to the next.

Assume the values for *z*_{i,j}
have been set for each column *j*, *j < k*.
Let *K ⊆ X* such that
*k ∈ K ⊆ {1,2,...,k}* and let
R = {x_{j} : j ∈ K}.
If *R* is a
minimal dependent set in *M*, then
*|N(R)| = |R| − 1* and the submatrix
of *A* consisting of the columns indexed by *K* has
*|R|* columns and
at most
*|R| − 1*
non-zero rows. Thus, the columns indexed by *K* are
dependent as vectors with entries in any field.
If *R* is an
independent set in *M*, then the set of columns *R'* indexed by
*K' = K \ {k}* is independent.
Some
*|R'| × |R'|*
submatrix of *A* in the columns indexed by *K'* has non-zero determinant over **F**.
Hence, by column expansion, some
*|R| × |R|*
submatrix *T* of the columns indexed by *K* has
determinant of *T* equal to a linear combination of the variables
*z*_{1,k},z_{2,k},...,z_{|Y|,k},
with at least one of the coefficients non-zero.
We obtain one such linear combination for each independent set containing
*x*_{k}, (and no
*x*_{j} with *j > k*) and there
can be at most
*2*^{k−1} such sets.
By the lemma, there is a choice for
*z*_{1,k},z_{2,k},...,z_{|Y|,k} ∈ **F**,
for *k ≤ n*
if *|***F**| > 2^{n−1}.
Hence, any transversal matroid is representable with respect to any sufficiently large field.

The Edmonds-Fulkerson matching matroids are transversal matroids and are therefore representable.
(The following gives you the main ideas from the Edonds-Fulkerson paper.)

The following theorem, which we state without proof, is a generalization of Tutte's perfect matching theorem.

**Edmonds's Matching Structural Theorem** (Paths, Trees and Flowers; Transversals and Matroid Partitions).
Let *G* be a graph. Let *J* denote the set of vertices which are incident with every maximum cardinality matching of *G*.
Let the connected components of
*G − J* be
*H*_{1},H_{2},...,H_{q}.
Let *U = J ∩ N(V(G) − J)*.
Then, *|V(H*_{i} )| = 2r_{i} + 1, for some integer
*r*_{i},
*1 ≤ i ≤ q*.
Every maximum cardinality matching contains *r*_{i}
edges in *H*_{i},
and contains an edge joining *u* to
*V(G) − J* for every
*u ∈ Q*.

We now construct a bipartite graph *B*, with bipartition
*(X,Y)*, as follows.
Let *X = V(G)*.
Let *Y* be the disjoint unions of sets
*Y*_{1},...Y_{q},J', where

(i) *|Y*_{i}| = |V(H_{i} ) − 1 and each vertex of
*H*_{i} is adjacent
in *B* to each vertex of *Y*_{i}

(ii) *J' = {a' : a∈ J}* and if there is an edge from
*a* to *H*_{i} in *G*, there is an edge from
*a'* to each vertex of
*H*_{i} in *B*; and

(iii) if there is no edge from
*a ∈ J* to any *H*_{i} in *G*, there is an edge from
*a'* to *a* in *B*.

The bipartite graph *B* gives us a transversal matroid on *X*. (We leave it to the reader to convince himself or herself that the
transversal matroid is the same as the matching matroid.)

Something in the other direction is also true: a transversal matroid for a graph *G* with bipartition
*(X,Y)* is a restriction of matching matroid of *G* to the elements
in *X*.

**
****Department of Mathematical Sciences**

Florida Atlantic University

777 Glades Road

Boca Raton, Florida 33431-0991

USA**
Office: Room 237, Science & Engineering**

Phone: (561) 297-3350

Fax: (561) 297-2436

URL: http://www.math.fau.edu/locke/matroid2.htm

Last modified March 19, 2014, by S.C. Locke.