Leigh.Samphier/Sandbox/Bound for Cardinality of Matroid Circuit

Theorem

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

Let $C \subseteq S$ be a circuit of $M$.

Let $\rho: \powerset S \to \Z$ denote the rank function of $M$.

Then:

$\card C \le \map \rho S + 1$

Proof

By definition of a circuit:

$C$ is dependent
$C \ne \O$

Let $x \in C$.

$C \setminus \set x \subsetneq C$
$C \setminus \set x \in \mathscr I$

We have:

 $\ds \map \rho S$ $\ge$ $\ds \card{C \setminus \set x}$ Definition of Rank Function $\ds$ $=$ $\ds \card C - \card{\set x}$ Cardinality of Set Difference with Subset $\ds$ $=$ $\ds \card C - 1$ Cardinality of Singleton $\ds \leadsto \ \$ $\ds \map \rho S + 1$ $\ge$ $\ds \card C$ Adding 1 to both sides of the equqrion

$\blacksquare$