:::info
### Definition
:::


:::info
#### heredity
:::

I: 收集 S 的 independent subsets
如果 B 是一個 S 的 independent subset → B ∈ I
假如有另一個 A，是 B 的subset (A 沒有其他條件限制)，A 也是 S 的independent subset

:::info
#### exchange property
:::

如果有兩個 independent subset A, B ⊆ S
W.L.O.G 假設 A 比 B 小（A 的元素個數比 B 少）
則必存在 x 在 B 中但不在 A 中，且將 A 聯集此 x，也會是一個 S 的independent subset

---


>Graphic Matroid 常用於 MST，為打字方便以下都以 M(G)表示
---
:::success
### Thm
:::

> Pf:
> 假設 A 是一個 maximal independent subset，suppose ∃B: 另一個 maximal independent subset，因為matroid有exchange property，所以∃x ∈ B-A，代表我們可以再將 A 擴大成 A∪{x}
> 矛盾 A 是 maximal independent subset