= Solution
The associated <matroid> is
$$
\boxed{M=(E,\mathcal I),\qquad\mathcal I=\{A\subseteq E:r(A)=|A|\}.}
$$
Thus the <graph>'s <edges> are the <ground set>, and the members of $\mathcal I$ are its <matroid independent sets>.
For the specified rank, if $(V,A)$ is a <forest>, $A$ itself is an allowed choice in the rank maximum, so $r(A)=|A|$. Conversely, if $r(A)=|A|$, some <forest> $F\subseteq A$ has $|F|=|A|$. Finiteness forces $F=A$, so $(V,A)$ is a <forest>. Hence \b[the independent sets are exactly all <forests> in $G$], including the empty <forest> and <forests> with isolated vertices.
The <matroid independence axioms> can also be checked directly. The empty set is a <forest>, and deleting <edges> cannot create a cycle. For exchange, let <forests> $I,J$ have $|I|<|J|$. If every <edge> of $J$ joined vertices within one component of $(V,I)$, its restriction to each component $S$ would have at most $|S|-1$ <edges>. Summing would give $|J|\leq|I|$, a contradiction. Thus some <edge> of $J\setminus I$ joins two components of $I$ and can be added without creating a cycle. This proves augmentation and identifies $M$ as the \b[<graphic matroid>].
Back to article page
