1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Are you familiar with the definitions of (i) rank of a matroid, (ii) graphical matroid? $\endgroup$
    – Yuval Filmus
    Apr 10, 2022 at 5:41
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Yuval Filmus
    Apr 10, 2022 at 5:42
  • $\begingroup$ Thanks for this. This view of summing over all connected components makes everything clear. $\endgroup$
    – Ash Ketchum
    Apr 10, 2022 at 8:17

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.