# Rank of a graph in matroid theory

I was going through the concept of graphs as matroids and I came upon the rank of a graph. Wikipedia lists it as $$n - c$$, $$n = |V|$$, $$c =$$ # of connected components.

I do understand rank and nullity of matrices, and graphs when expressed in their incidence matrix form have a one-to-one correspondence with the rank of its incidence matrix. However, I am not understanding how $$r(G) = |V| - c$$, $$c =$$ # of connected components and the definition of rank as the maximum size of a subforest of $$G$$ are equivalent.

I tried looking it up online but found no satisfactory explanation. Any resources that would be helpful to understand the concept would be great.

• Are you familiar with the definitions of (i) rank of a matroid, (ii) graphical matroid? Apr 10, 2022 at 5:41
• The rank of a graphical matroid is the maximum number of edges which do not close a cycle. In a connected component of size $m$, the maximum number of edges which do not close a cycle is $m - 1$. Summing this over all connected components gives $n - c$. Apr 10, 2022 at 5:42
• Thanks for this. This view of summing over all connected components makes everything clear. Apr 10, 2022 at 8:17

The rank of a graphical matroid is the size of a spanning forest, which consists of a spanning tree in each connected component. A spanning tree for a connected component of size $$m$$ contains $$m - 1$$ edges. Summing this over all connected components, we see that a spanning forest contains $$n - c$$ edges.