[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*}[/step]

[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: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]