Cycle Matroid is Matroid

Theorem

Let $G = \struct {V, E}$ be a graph.

Let $\struct {E, \mathscr I}$ be the cycle matroid of $G$.

Then $\struct {E, \mathscr I}$ is a matroid.

Proof

It needs to be shown that $\mathscr I$ satisfies the matroid axioms $(\text I 1)$, $(\text I 2)$ and $(\text I 3)$.

Matroid Axiom $(\text I 1)$

$\ds \O \subset E$ is the empty subgraph, which does not contain any cycles.

Hence, by definition of the cycle matroid, $\ds \O \in \mathscr I$.

Matroid Axiom $(\text I 2)$

This theorem requires a proof. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{ProofWanted}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

Matroid Axiom $(\text I 3)$

This theorem requires a proof. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{ProofWanted}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

Sources

• 1976: Dominic Welsh: Matroid Theory ... (previous) ... (next) Chapter $1.$ $\S 3.$ Examples of Matroids