cycle rank | cyclomatic number | graph Betti number | graph nullity

The circuit rank γ, also denoted μ or β and known as the cycle rank, (first) graph Betti number, cyclomatic number, or graph nullity, is the smallest number of graph edges which must be removed from an undirected graph on m graph edges and n nodes such that no graph cycle remains. It is given by μ = m - n + c, for a graph with c connected components. The concept was first introduced by Gustav Kirchhoff who referred to it as "cyclomatic number". The circuit rank gives the number of independent cycles in the cycle basis of a graph (Harary 1994, pp. 37-40; White 2001, p. 56).

Balaban index | Betti number | cactus graph | connected component | edge count | graph cycle | vertex count