0
$\begingroup$

How to prove that for any given graph $G=(V,E)$, the circuit rank is $$|E|- |V| + C,$$ Where $C$ is the number of connected components.

$\endgroup$
1
  • 1
    $\begingroup$ Could you do it if $C=1$? $\endgroup$
    – Casteels
    May 11, 2015 at 10:33

1 Answer 1

1
$\begingroup$

Essentially, we need to delete edges such that each connected component turns into a tree. We know that an $n$-vertex tree has $n-1$ edges, and, more generally, an $|V|$-vertex $C$-component forest (the union of $C$ trees) has $|V|-C$ edges (ref.).

So the minimum number of edges that must be deleted to create an acyclic subgraph is $|E|-(|V|-C)=|E|-|V|+C$, the circuit rank.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .