TU Wien:Diskrete Mathematik für Informatik VU (Rubey)/Beispiel17

Let $G=(V,E)$ be an undirected graph. Set $M_{k}(G)=(E,S)$ where $S=\{F\cup M|F\subseteq E,(V,F)acyclic,M\subseteq E,|M|\leqslant k\}$.

Show that $M_{k}(G)$ is the set of independent sets of a matroid! In particular, the set of spanning forests of an undirected graph $G=(V,E)$ is the set of independent sets of a matroid.

I think the OP means to say that $M_{k}(G)=(E,S)$ is a matroid on the ground set $E$ with $S$ being the family of independent sets. I assume here that $G$ is a finite graph (so $V$ and $E$ are finite sets). I don't know how to deal with infinite matroids. The second part of the task is simply showing that $M_{0}(G)$ 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 $\emptyset \in S$, since $F=\emptyset$ and $M=\emptyset$ gives $\emptyset =F\cup M\in S$.

For the hereditary property, let $F\cup M\in S$ and $T\subseteq F\cup M$. Write $T_{F}=T\cap F$ and $T_{M}=T\cap M$. Then, the edge induced subgraph $G[T_{F}]$ of $G$ is a forest, and $|T_{M}|\leq |M|\leq k$. So, $T=T_{F}\cup T_{M}$ is in $S$.

For the augmentation property, let $F_{1}\cup M_{1},F_{2}\cup M_{2}\in S$ be such that $|F_{1}\cup M_{1}|<|F_{2}\cup M_{2}|$. WLOG, assume that $M_{1}\cap F_{1}=\emptyset$ and $M_{2}\cap F_{2}=\emptyset$. In the case $|M_{2}|>|M_{1}|$, things are pretty easy. Pick an element $m\in (F_{2}\cup M_{2})\setminus (F_{1}\cup M_{1})$. We have ${\big |}M_{1}\cup \{m\}{\big |}=|M_{1}|+1\leq |M_{2}|\leq k.$ So, $(F_{1}\cup M_{1})\cup \{m\}=F_{1}\cup {\big (}M_{1}\cup \{m\}{\big )}$ is in $S$. If $|M_{2}|\leq |M_{1}|$, then we must have $|F_{2}|-|F_{1}|\geq {\big (}|F_{2}|-|F_{1}|{\big )}+{\big (}|M_{2}|-|M_{1}|{\big )}={\big (}|F_{2}|+|M_{2}|{\big )}-{\big (}|F_{1}|+|M_{1}|{\big )}.$ Because $F_{1}\cap M_{1}=F_{2}\cap M_{2}=\emptyset$, $|F_{2}|-|F_{1}|\geq |F_{2}\cup M_{2}|-|F_{1}\cup M_{1}|>0.$ Therefore, the forest $F_{1}$ has more connected components than $F_{2}$ (recalling that the number of connected components in a forest on $n$ vertices and $m$ edges is $n-m$). Therefore, there exists a connected component $C$ of $F_{2}$ with vertices from at least two connected components of $F_{1}$. Therefore, there is an edge $e$ of $C$ that connects two distinct connected components of $F_{1}$. Note that $F_{1}\cup \{e\}$ is still a forest. So, $(F_{1}\cup M_{1})\cup \{e\}=(F_{1}\cup \{e\})\cup M_{1}\in S$.

Quelle: https://math.stackexchange.com/questions/2995272/show-that-m-kg-is-the-set-of-independent-sets-of-a-matroid