[proofplan] We verify the three independence axioms in the definition of a [matroid](/page/Matroid) for the family of acyclic edge sets. The empty edge set is acyclic, and acyclicity is inherited by subsets. For augmentation, we compare the number of connected components of two forests: a forest with edge set $F$ has exactly $|V|-|F|$ connected components, so the larger forest has fewer components. This forces some edge of the larger forest to connect two distinct components of the smaller one, and adding such an edge cannot create a cycle. [/proofplan] [step:Define the graphic matroid candidate and verify nonemptiness and hereditary closure] By the definition of the [graphic matroid](/page/Graphic%20Matroid), the candidate independent sets are the acyclic edge sets. Define the family of independent edge sets by \begin{align*} \mathcal I_H := \{F\subseteq E : (V,F)\text{ is acyclic}\}. \end{align*} Thus the graphic matroid candidate is the pair $M(H):=(E,\mathcal I_H)$. The empty edge set $\varnothing \subset E$ belongs to $\mathcal I_H$, since the graph $(V,\varnothing)$ has no cycle. Now let $F \in \mathcal I_H$ and let $A \subset F$. If $(V,A)$ contained a cycle, then the same sequence of edges would be a cycle in $(V,F)$, contradicting $F \in \mathcal I_H$. Hence $A \in \mathcal I_H$. Thus $\mathcal I_H$ is nonempty and closed under taking subsets. [/step] [step:Count the connected components of a finite forest] Let $\mathcal P(E)$ denote the power set of $E$, and let $\mathbb Z_{\ge 0}$ denote the set of nonnegative integers. Define the component-counting map $c:\mathcal P(E)\to \mathbb Z_{\ge 0}$ as follows: for each edge set $F\subset E$, the value $c(F)$ is the number of connected components of the spanning subgraph $(V,F)$, with isolated vertices counted as connected components. [claim:A forest with edge set $F$ has $c(F)=|V|-|F|$ connected components] [/claim] [proof] We prove the claim by induction on $|F|$. If $|F|=0$, then $(V,F)=(V,\varnothing)$ has one connected component for each vertex, so $c(F)=|V|=|V|-|F|$. Assume the formula holds for every forest with $m$ edges, and let $F \subset E$ be a forest with $m+1$ edges. Choose an edge $e \in F$ and set $F' := F \setminus \{e\}$. Removing an edge cannot create a cycle, so $(V,F')$ is a forest. Hence, by the induction hypothesis, \begin{align*} c(F')=|V|-|F'|=|V|-m. \end{align*} Because $F$ is a forest, the endpoints of $e$ lie in two distinct connected components of $(V,F')$; otherwise there would be a path in $(V,F')$ between the endpoints of $e$, and adjoining $e$ would create a cycle in $(V,F)$. The elementary component fact being used is that an edge joining two distinct connected components identifies precisely those two components and leaves every other component unchanged. Therefore adding $e$ to $F'$ merges exactly two connected components and changes no other component, so \begin{align*} c(F)=c(F')-1=(|V|-m)-1=|V|-(m+1)=|V|-|F|. \end{align*} The induction proves the claim. [/proof] [/step] [step:Find an edge of the larger forest crossing two components of the smaller forest] Let $F_1,F_2 \in \mathcal I_H$ satisfy $|F_1|<|F_2|$. By the component count for forests, \begin{align*} c(F_1)=|V|-|F_1|>|V|-|F_2|=c(F_2). \end{align*} We claim that some edge $e \in F_2\setminus F_1$ has endpoints in two distinct connected components of $(V,F_1)$. Suppose, for contradiction, that every edge of $F_2$ has both endpoints in a single connected component of $(V,F_1)$. Then every path in $(V,F_2)$ stays inside one connected component of $(V,F_1)$, so each connected component of $(V,F_2)$ is contained in a connected component of $(V,F_1)$. Since every connected component of $(V,F_1)$ contains at least one vertex and hence contains at least one connected component of $(V,F_2)$, this gives \begin{align*} c(F_2)\ge c(F_1), \end{align*} contradicting $c(F_1)>c(F_2)$. Hence such an edge $e$ exists. Since every edge of $F_1$ has both endpoints in one connected component of $(V,F_1)$, this edge cannot lie in $F_1$, so $e\in F_2\setminus F_1$. [guided] Let $F_1,F_2 \in \mathcal I_H$ satisfy $|F_1|<|F_2|$. Recall that $c(F)$ denotes the number of connected components of the spanning subgraph $(V,F)$, with isolated vertices counted as connected components. The point of counting components is that, inside a forest, every new edge merges two components and never merely adds redundancy. Therefore the larger forest has fewer connected components: \begin{align*} c(F_1)=|V|-|F_1|>|V|-|F_2|=c(F_2). \end{align*} We now prove that some edge of $F_2$ crosses between two connected components of $(V,F_1)$. Suppose the opposite: every edge of $F_2$ has both endpoints inside a single connected component of $(V,F_1)$. Then a path in $(V,F_2)$ cannot move from one connected component of $(V,F_1)$ to another, because each edge of the path remains inside one such component. Hence each connected component of $(V,F_2)$ is contained in a connected component of $(V,F_1)$. This containment forces $(V,F_2)$ to have at least as many connected components as $(V,F_1)$. Indeed, every connected component of $(V,F_1)$ contains at least one vertex, and that vertex belongs to some connected component of $(V,F_2)$ contained inside it. Thus each component of $(V,F_1)$ contains one or more components of $(V,F_2)$, so \begin{align*} c(F_2)\ge c(F_1). \end{align*} This contradicts the strict inequality $c(F_1)>c(F_2)$ obtained from $|F_1|<|F_2|$. Therefore there exists an edge $e\in F_2$ whose endpoints lie in two distinct connected components of $(V,F_1)$. Such an edge is not in $F_1$, since every edge of $F_1$ lies within a single connected component of $(V,F_1)$. Hence $e\in F_2\setminus F_1$. [/guided] [/step] [step:Add the crossing edge without creating a cycle] Let $e\in F_2\setminus F_1$ be an edge whose endpoints lie in two distinct connected components of $(V,F_1)$. We prove that $F_1\cup\{e\}\in \mathcal I_H$. If $(V,F_1\cup\{e\})$ contained a cycle, then that cycle would have to use the edge $e$, because $(V,F_1)$ is a forest. Removing $e$ from the cycle would leave a path in $(V,F_1)$ connecting the two endpoints of $e$. This contradicts the choice of $e$, whose endpoints lie in distinct connected components of $(V,F_1)$. Therefore $(V,F_1\cup\{e\})$ has no cycle, so $F_1\cup\{e\}\in \mathcal I_H$. We have shown that whenever $F_1,F_2\in\mathcal I_H$ and $|F_1|<|F_2|$, there exists $e\in F_2\setminus F_1$ such that $F_1\cup\{e\}\in\mathcal I_H$. Together with nonemptiness and hereditary closure, this proves that $(E,\mathcal I_H)$ satisfies the independence axioms in the definition of a [matroid](/page/Matroid). Since $M(H)$ was defined as $(E,\mathcal I_H)$, the graphic matroid $M(H)$ is a matroid. [/step]