Union of Matroid Base with Element of Complement is Dependent

From ProofWiki
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 \in S \setminus B$.


Then:

$B \cup \set x$ is a dependent superset of $B$


Proof

From Set is Subset of Union:

$B \subseteq B \cup \set x$

Because $x \in B \cup \set x$ and $x \notin B$:

$B \ne B \cup \set x$

Hence:

$B \subsetneq B \cup \set x$

By definition of base:

$B$ is a maximal independent subset

Hence:

$B \cup \set x \notin \mathscr I$

$\blacksquare$