All Bases of Matroid have same Cardinality/Corollary
Jump to navigation
Jump to search
Theorem
Let $M = \struct {S, \mathscr I}$ be a matroid.
Let $B \subseteq S$ be a base of $M$.
Let $X \subseteq S$ be any independent subset of $M$.
Then:
- $\card X \le \card B$
Proof
From Independent Subset is Contained in Maximal Independent Subset :
- $\exists B' \subseteq S : X \subseteq B'$ and $B'$ is a maximal independent subset of $S$
By definition of a base:
- $B'$ is a base of $M$
From Cardinality of Subset of Finite Set:
- $\card X \le \card {B'}$
From All Bases of Matroid have same Cardinality:
- $\card{B'} = \card B$
Hence:
- $\card X \le \card B$
$\blacksquare$