# Leigh.Samphier/Sandbox/Rank of Matroid Circuit is One Less Than Cardinality

Jump to navigation Jump to search

## 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:

$\map \rho C = \card C -1$

## Proof

By definition of a circuit:

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

Let $x \in C$.

### Lemma

$C \setminus \set x$ is a maximal independent subset of $C$

We have:

 $\ds \map \rho C$ $=$ $\ds \card{C \setminus \set x}$ Leigh.Samphier/Sandbox/Cardinality of Maximal Independent Subset Equals Rank of Set $\ds$ $=$ $\ds \card C - \card{\set x}$ Cardinality of Set Difference with Subset $\ds$ $=$ $\ds \card C - 1$ Cardinality of Singleton

$\blacksquare$