TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 17

17) Let G = (V, E) be an undirected graph. Set M_k(G) = (E, S) where S={A⊆E|A=F∪M where F is a forest and |M|≤k}.

Prove that M_k(G) is a matroid.

Theory

A matroid M=(E,S), where E is a finite set and S is a subset of the power set of E s.t:

• non emptiness: The empty set is in S. (S is therefore not an empty set itself i.e. not empty)
• S is downward closed: if $s\in S$ and $t\subseteq s$ then $t\in S$
• S has the exchange property: if $s,t\in S$ and $|t|=|s|+1$, then there exists an element $x\in t\setminus s$ s.t. $s\cup \{x\}\in S$

Solution

A=Fa u Ma
B=Fb u Mb
|B|>|A|

now you have to show the different possible cases how you can select an edge from B and put into A.

This link could help a little bit: https://web.archive.org/web/20180730233732/https://matheplanet.com/matheplanet/nuke/html/viewtopic.php?topic=211896

Solution (Warning: the solution listed below seems wrong ) (the case k>0 is missing. so it cannot be complete...)

for k=0 there's nothing to show as this was done in the lecture - the interesting part begins with k>0

Proof for k=0

$M_{0}(G)=(E,S)$ $F\in S$ iff F is a forest

$\{\}$ is in S

It contains no cycles and therefore it's a forest

S is downward closed

S is downward closed, as every subgraph of a forest is also a forest and therefore also independent (i.e. $\in S$)

the exchange property holds in S

Let $F_{1},F_{2}\in S$ be forests where $|F_{1}|=|F_{2}|+1$

The number of vertices is given by $|V|=|F_{1}|+k_{1}=|F_{2}|+k_{2}$ where $k_{i}$ is the number of trees in the forest. Therefore $k_{1}=k_{2}-1$, which means that there must exist an edge in $F_{1}\setminus F_{2}$, which connects two trees in $F_{1}$.

Proof für k>0

The first two axioms still hold true.