Let
be an undirected graph. Set
where
.
Show that
is the set of independent sets of a matroid! In particular, the set of spanning forests of an undirected graph
is the set of independent sets of a matroid.
I think the OP means to say that
is a matroid on the ground set
with
being the family of independent sets. I assume here that
is a finite graph (so
and
are finite sets). I don't know how to deal with infinite matroids. The second part of the task is simply showing that
is a matroid, which is implied by the first part.
From here, there are three checkpoints. For the first one, it is easy to see that
, since
and
gives
.
For the hereditary property, let
and
. Write
and
. Then, the edge induced subgraph
of
is a forest, and
. So,
is in
.
For the augmentation property, let
be such that
. WLOG, assume that
and
. In the case
, things are pretty easy. Pick an element
. We have
So,
is in
. If
, then we must have
Because
,
Therefore, the forest
has more connected components than
(recalling that the number of connected components in a forest on
vertices and
edges is
). Therefore, there exists a connected component
of
with vertices from at least two connected components of
. Therefore, there is an edge
of
that connects two distinct connected components of
. Note that
is still a forest. So,
.
Quelle: https://math.stackexchange.com/questions/2995272/show-that-m-kg-is-the-set-of-independent-sets-of-a-matroid