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

16) Prove: If M=(E, S) is a matroid and A and B are two bases of M, then |A|=|B|

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

We assume that there are two bases $A$ and $B$ with different number of elements. Let $\left|A\right|=m<n=\left|B\right|$. Since the cardinality of $A$ is smaller than the cardinality of $B$ and every subset of $B$ must be an element of the independence set, one can find a set $C\subseteq B$ where $|A|=|C|-1$.

By definition this means there is en element in $C\setminus A$ which we can add to $A$ and get a larger independent set than $A$. But this means that $A$ is not a maximal independent set and therefore not a base of the matroid.