[proofplan]
The rank of $A$ in the cycle matroid is the largest size of an acyclic subset of $A$. We compute this maximum inside the spanning subgraph $(V(G), A)$ by decomposing it into connected components. On each component, a maximal acyclic edge set is a tree on that component's vertices and therefore has one fewer edge than the number of vertices in that component. Summing these componentwise contributions gives $|V(G)| - c(A)$, and taking $A = E(G)$ gives the rank of the whole matroid.
[/proofplan]
[step:Translate matroid rank into the largest size of a forest inside $A$]
Let $H_A$ denote the spanning subgraph of $G$ with vertex set $V(G)$ and edge set $A$. By definition of the cycle matroid $M(G)$, a subset $I \subset E(G)$ is independent in $M(G)$ exactly when the subgraph $(V(G), I)$ contains no cycle, that is, when $I$ is a forest in $G$. Hence
\begin{align*}
r_{M(G)}(A) = \max\{|I| : I \subset A \text{ and } (V(G), I) \text{ is a forest}\}.
\end{align*}
Thus the problem is to compute the maximum number of edges in a forest contained in $H_A$.
[/step]
[step:Choose a maximal forest component by component]
Let the connected components of $H_A$ be
\begin{align*}
C_1, C_2, \dots, C_m,
\end{align*}
where $m = c(A)$. For each index $i \in \{1, \dots, m\}$, let $V_i \subset V(G)$ be the vertex set of $C_i$, and write $v_i := |V_i|$.
For each component $C_i$, choose a spanning tree $T_i$ of $C_i$. Since $C_i$ is connected and finite, such a spanning tree exists: among all connected spanning subgraphs of $C_i$, choose one with the fewest edges; if it contained a cycle, removing an edge from that cycle would preserve connectedness, contradicting minimality. The edge set of $T_i$ has exactly $v_i - 1$ edges, because a finite tree on $v_i$ vertices has $v_i - 1$ edges.
Define
\begin{align*}
F := E(T_1) \cup E(T_2) \cup \cdots \cup E(T_m).
\end{align*}
The components $C_i$ are edge-disjoint, so
\begin{align*}
|F| = \sum_{i=1}^{m} |E(T_i)| = \sum_{i=1}^{m} (v_i - 1) = \sum_{i=1}^{m} v_i - m.
\end{align*}
Since the sets $V_1, \dots, V_m$ partition $V(G)$, we have $\sum_{i=1}^{m} v_i = |V(G)|$. Therefore
\begin{align*}
|F| = |V(G)| - c(A).
\end{align*}
The subgraph $(V(G), F)$ is a forest, because each restriction to a component is a tree and there are no edges of $F$ between distinct components.
[/step]
[step:Show no forest contained in $A$ can be larger]
Let $I \subset A$ be any subset such that $(V(G), I)$ is a forest. For each $i \in \{1, \dots, m\}$, define
\begin{align*}
I_i := I \cap E(C_i).
\end{align*}
Then $(V_i, I_i)$ is a forest on the vertex set $V_i$, so every connected component of $(V_i, I_i)$ is a tree. If these components have vertex sets of sizes $w_{i,1}, \dots, w_{i,k_i}$, then their edge counts are $w_{i,1}-1, \dots, w_{i,k_i}-1$. Hence
\begin{align*}
|I_i| = \sum_{j=1}^{k_i} (w_{i,j} - 1) = \sum_{j=1}^{k_i} w_{i,j} - k_i = v_i - k_i \le v_i - 1.
\end{align*}
Summing over $i$ gives
\begin{align*}
|I| = \sum_{i=1}^{m} |I_i| \le \sum_{i=1}^{m} (v_i - 1) = |V(G)| - c(A).
\end{align*}
[guided]
We now prove that the forest constructed in the previous step is as large as possible. Let $I \subset A$ be any independent set of the cycle matroid. By the definition of $M(G)$, this means that $(V(G), I)$ is a forest.
The spanning subgraph $H_A = (V(G), A)$ has connected components $C_1, \dots, C_m$, where $m = c(A)$. For each component $C_i$, with vertex set $V_i$ and $v_i = |V_i|$, define
\begin{align*}
I_i := I \cap E(C_i).
\end{align*}
This separates the chosen forest edges according to the connected components of $H_A$. Since no edge of $A$ joins two distinct components of $H_A$, the sets $I_1, \dots, I_m$ partition $I$ as edge sets, and therefore
\begin{align*}
|I| = \sum_{i=1}^{m} |I_i|.
\end{align*}
Fix an index $i \in \{1, \dots, m\}$. The graph $(V_i, I_i)$ is a subgraph of the forest $(V(G), I)$, so it is again a forest. Let its connected components have vertex sets of sizes $w_{i,1}, \dots, w_{i,k_i}$, where $k_i$ is the number of connected components of $(V_i, I_i)$. Each connected component of a finite forest is a tree, and a finite tree with $w_{i,j}$ vertices has exactly $w_{i,j}-1$ edges. Therefore
\begin{align*}
|I_i| = \sum_{j=1}^{k_i} (w_{i,j} - 1).
\end{align*}
The component vertex sets partition $V_i$, so
\begin{align*}
\sum_{j=1}^{k_i} w_{i,j} = v_i.
\end{align*}
Substituting this into the edge count gives
\begin{align*}
|I_i| = v_i - k_i.
\end{align*}
Since $k_i \ge 1$ whenever $V_i$ is nonempty, we obtain
\begin{align*}
|I_i| \le v_i - 1.
\end{align*}
Summing this estimate over all connected components of $H_A$ gives
\begin{align*}
|I| = \sum_{i=1}^{m} |I_i| \le \sum_{i=1}^{m} (v_i - 1).
\end{align*}
Because the component vertex sets $V_1, \dots, V_m$ partition $V(G)$ and $m = c(A)$, the right-hand side is
\begin{align*}
\sum_{i=1}^{m} (v_i - 1) = |V(G)| - c(A).
\end{align*}
Thus every independent subset $I \subset A$ has size at most $|V(G)| - c(A)$.
[/guided]
[/step]
[step:Conclude the rank formula and specialize to the whole graph]
The previous two steps give both inequalities. The forest $F \subset A$ constructed componentwise has size $|V(G)| - c(A)$, so
\begin{align*}
r_{M(G)}(A) \ge |V(G)| - c(A).
\end{align*}
Every independent subset $I \subset A$ has size at most $|V(G)| - c(A)$, so
\begin{align*}
r_{M(G)}(A) \le |V(G)| - c(A).
\end{align*}
Therefore
\begin{align*}
r_{M(G)}(A) = |V(G)| - c(A).
\end{align*}
Taking $A = E(G)$, the spanning subgraph $(V(G), E(G))$ is $G$ itself, so $c(E(G)) = c(G)$. Hence
\begin{align*}
r(M(G)) = r_{M(G)}(E(G)) = |V(G)| - c(G).
\end{align*}
This proves both assertions.
[/step]
