Matroid: basis iff size is rank

Dependencies:

1. Matroid: basis
2. Matroid: rank

Let $M = (S, I)$ be a matroid. Let $A$ be an independent set of $X \subseteq S$. Then $A$ is a basis of $X \iff |A| = \operatorname{rank}(X)$.

Proof

Let $B_1$ and $B_2$ be 2 bases of $X$. Assume $|B_1| \neq |B_2|$. Without loss of generality, let $|B_1| < |B_2|$. By the exchange property, $\exists e \in B_2 - B_1, B_1 + e \in I$. But this contradicts the maximality of $B_1$. Therefore, $|B_1| = |B_2|$. This means that all bases of $X$ have the same size.

$A \in I$ and $|A| = r(X)$
$\iff A$ is a maximum-size independent set in $X$
$\implies A$ is a maximal independent set in $X$
$\iff A$ is a basis of $X$.

Since all bases have the same size, they all have size $r(X)$.

Dependency for:

1. Matroid: rank of set increment
2. Matroid: basis of set increment
3. Matroid: expanding to basis
4. Matroid: greedy algorithm

Info:

• Depth: 2
• Number of transitive dependencies: 3

Transitive dependencies:

1. Matroid
2. Matroid: rank
3. Matroid: basis