Graphic matroid
= Graphic matroid
{wiki}
= Cycle matroid
{synonym}
For a finite <undirected graph>, the <graphic matroid> has its <edges> as the <ground set>. A <subset> is a <matroid independent set> when its <edges> form a <forest> on the original <vertices>, including isolated <vertices>. Its <matroid bases> give a <spanning tree> in each <connected component of a graph>; for a <connected graph>, each <matroid basis> is a <spanning tree>.
For a <graph triangle> on <vertices> $P,Q,R$, label the <edges> $a=PQ$, $b=QR$, and $c=PR$, with weights $8,5,6$. The <empty set>, all singletons, and all pairs are <forests>; the triple contains the <graph cycle> $P,Q,R,P$. Thus its eight <subsets> have exactly the independence pattern checked in the <weighted three-vector matroid>, and the same fifteen exchange comparisons pass. The <matroid greedy algorithm> chooses $PQ$, chooses $PR$, and rejects $QR$, producing the heaviest <spanning tree>, of weight $14$.
\Image[/matroid-triangle-and-hereditary-greedy-obstruction.png]
{title=A weighted <graph triangle> admits greedy selection of a <matroid basis>; a hereditary <independence system> without exchange traps a <greedy algorithm> at weight $10$ instead of $12$}
\b[Exchange outline.] Deleting <edges> cannot create a <graph cycle>. If <forests> $I,J$ have $|I|<|J|$, some <edge> of $J$ joins different <connected components of a graph> of $I$: otherwise, within each such component, $J$ would have at most its number of <vertices> minus one <edges>, giving $|J|\leq|I|$. Adding that <edge> keeps a <forest>. This is the <matroid independence axioms> expressed through connectivity.