Leigh.Samphier/Sandbox/Proper Subset of Matroid Circuit is Independent

From ProofWiki
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$.


Then:

every proper subset $A$ of $C$ is independent

Proof

By definition of a circuit of $M$:

$C$ is a minimum dependent subset of $M$

By definition of the minimum dependent subset of $M$:

every proper subset $A$ of $C$ is not a dependent subset

By definition of a dependent subset:

every proper subset $A$ of $C$ is an independent subset

$\blacksquare$

Sources