# Circuit rank

In graph-theoretic mathematics, the circuit rank, cyclomatic number, or nullity of an undirected graph ${\displaystyle G}$ is the minimum number ${\displaystyle r}$ of edges to remove from ${\displaystyle G}$ to remove all its cycles, making it into a forest. Unlike the corresponding feedback arc set problem for directed graphs, it is easily computed, using the simple formula

${\displaystyle r=m-n+c}$,

where ${\displaystyle m}$ is the number of edges in ${\displaystyle G}$, ${\displaystyle n}$ is the number of vertices, and ${\displaystyle c}$ is the number of connected components.[1]

Under the name of cyclomatic number, the concept was introduced by Gustav Kirchhoff.[2][3]

## Related concepts

The circuit rank is the corank of the graphic matroid of ${\displaystyle G}$,[4] from which it can be seen that a greedy algorithm that removes edges one by one, at each step removing an edge that belongs to at least one cycle of the remaining graph, will necessarily find a set of ${\displaystyle r}$ edges the removal of which leaves ${\displaystyle G}$ acyclic. Alternatively, such a set may be found as the complement of a spanning forest of ${\displaystyle G}$.

The cyclomatic number is also the dimension of the cycle space of ${\displaystyle G}$.[1] Topologically, ${\displaystyle G}$ may be viewed as an example of a 1-dimensional simplicial complex, and its cyclomatic number is the rank of the first (integer) homology group of this complex,[5]

${\displaystyle r=\operatorname {rank} \left[H_{1}(G,\mathbb {Z} )\right]}$,

and because of this the cyclomatic number is also called the first Betti number.[6]

The circuit rank controls the number of ears in an ear decomposition of a graph: in a biconnected graph with circuit rank ${\displaystyle r}$, every open ear decomposition has exactly ${\displaystyle r}$ ears.[7]

Other numbers defined in terms of edge deletion from undirected graphs include the edge connectivity, the minimum number of edges to delete in order to disconnect the graph, and matching preclusion, the minimum number of edges to delete in order to prevent the existence of a perfect matching.

## Almost trees

A graph with cyclomatic number ${\displaystyle r}$ is also called a r-almost-tree, because only r edges need to be removed from the graph to make it into a tree or forest. A 1-almost-tree is a near-tree: a connected near-tree is a pseudotree, a cycle with a (possibly trivial) tree rooted at each vertex.[8]

Several authors have studied the parameterized complexity of graph algorithms on r-near-trees, parameterized by ${\displaystyle r}$.[9][10]