Matroid Base Substitution From Fundamental Circuit

From ProofWiki
Jump to navigation Jump to search


Let $M = \struct {S, \mathscr I}$ be a matroid.

Let $B$ be a base of $M$.

Let $y \in S \setminus B$.

Let $\map C {y,B}$ denote the fundamental circuit of $y$ in $B$.

Let $x \in B$.


$\paren{B \setminus \set x} \cup \set y$ is a base of $M$ if and only if $x \in \map C {y,B}$

That is, $y$ can be substituted for $x$ in $B$ to form another base of $M$ if and only if $x \in \map C {y,B}$.


Necessary Condition

Let $\paren{B \setminus \set x} \cup \set y$ be a base of $M$.

By definition of the fundamental circuit:

$\map C {y,B} \subseteq B \cup \set y$


$\map C {y,B}$ is dependent

Aiming for a contradiction, suppose $x \notin \map C {y,B}$.


$\map C {y,B} \subseteq \paren{B \setminus \set x} \cup \set y$

By matroid axiom $( \text I 2)$:

$\map C {y,B}$ is independent

This contradicts the fact that:

$\map C {y,B}$ is dependent

It follows that:

$x \in \map C {y,B}$


Sufficient Condition

We prove the contrapositive statement.

Let $\paren{B \setminus \set x} \cup \set y$ not be a base of $M$.

We have:

\(\ds \card{\paren{B \setminus \set x} \cup \set y}\) \(=\) \(\ds \card{B \setminus \set x} + \card{\set y}\) Corollary of Cardinality of Set Union
\(\ds \) \(=\) \(\ds \paren{\card B - \card{\set x} } + \card{\set y}\) Cardinality of Set Difference
\(\ds \) \(=\) \(\ds \paren{\card B - 1 } + 1\) Cardinality of Singleton
\(\ds \) \(=\) \(\ds \card B\)

From contrapositive statement of Independent Subset is Base if Cardinality Equals Cardinality of Base:

$\paren{B \setminus \set x} \cup \set y$ is a dependent subset of $M$

From Dependent Subset Contains a Circuit there exists a circuit $C'$:

$C' \subseteq \paren{B \setminus \set x} \cup \set y \subseteq B \cup \set y$

From Matroid Base Union External Element has Fundamental Circuit:

$C' = \map C {y,B}$


$x \notin \map C {y, B}$

From Rule of Transposition we have:

$x \in \map C {y, B} \implies \paren{B \setminus \set x} \cup \set y$ is a base of $M$