Cyclomatic number
the minimum number of edges to remove from a graph to eliminate all its cycles
In graph theory, a branch of mathematics, the cyclomatic number, circuit rank, cycle rank, corank or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or forest.
The concept was introduced and called the cyclomatic number by Gustav Kirchhoff.
Formula
The cyclomatic number of a graph equals the number of independent cycles in the graph, the size of a cycle basis. Unlike the corresponding feedback arc set problem for directed graphs, the cyclomatic number r is easily computed using the formula:
r
=
e
−
v
+
c
,
{\displaystyle r=e-v+c,}
where e is the number of edges in the given graph, v is the number of vertices, and c is the number of connected components.
It is possible to construct a minimum-size set of edges that breaks all cycles efficiently, either using a greedy algorithm or by complementing a spanning forest.
The cyclomatic number can be explained in terms of algebraic graph theory as the dimension of the cycle space of the graph, in terms of matroid theory as the dual rank of its graphic matroid, and in terms of topology as one of the Betti numbers of a topological space derived from the graph. It counts the ears in an ear decomposition of the graph, forms the basis of parameterized complexity on almost-trees, and has been applied in software metrics as part of the definition of cyclomatic complexity of a piece of code.
For hypergraphs
The cyclomatic number of a hypergraph can be derived by its Levi graph, with the same cyclomatic number but reduced to a simple graph. It is
r
=
g
−
(
v
+
e
)
+
c
,
{\displaystyle r=g-(v+e)+c,}
where g is the degree sum (and the number of edges in the Levi graph), e is the number of hyperedges in the given hypergraph, v is the number of vertices, and c is the number of connected components.
The degree sum of a hypergraph is the sum of the degrees of all the vertices, reducing to 2e for a simple graph, or ke for a k-uniform hypergraph.
This brief starts where responsible research should: with the source description of “Cyclomatic number” as the minimum number of edges to remove from a graph to eliminate all its cycles. Everything that follows is an evidence route, not borrowed authority.
Why this record matters
The subject matters to the general reference register because the source frames it as the minimum number of edges to remove from a graph to eliminate all its cycles. Its deeper value depends on whether names, dates, institutions and citations support that framing.
The citation trail is more important than the brevity of the summary: it shows where individual claims can be examined in context. The source revision retrieved here is dated Nov 23, 2025. The linked authority identifier is Q5121616. None of the 0 selected statements returned an explicit reference.
The absence of detail may reflect summary conventions rather than a lack of surviving documentation. The lead is largely declarative, so disagreement and counter-evidence require a deliberate search beyond the opening account. Authority statements aid reconciliation but still require their own references, qualifiers and ranks to be checked.
How to read it
Use the entry as an orientation point, then follow its citations and revision history. Names, dates and institutional relationships should be checked against the original record.
- Subject orientation
- Search vocabulary
- Locating named sources
The closest primary source, responsible institution and strongest cited specialist reference.
Three-step research path
- Establish the record: confirm the title “Cyclomatic number”, its source revision and the description used here.
- Expand the search: follow Cyclomatic number primary sources, Cyclomatic number archive and Cyclomatic research across catalogues and specialist indexes.
- Test the account: compare the strongest cited source with the responsible institution’s current record and note any disagreement.
Questions for further research
- Which source most directly establishes the central claim about “Cyclomatic number”?
- What terminology or title could unlock a more precise catalogue search?
- Which cited source is closest to the event, object or claim?
Search terms from this dossier
This entry incorporates text from “Cyclomatic number” on English Wikipedia. Contributors are listed in the page history. Text is available under the Creative Commons Attribution-ShareAlike 4.0 License. Selected authority identifiers and statements are retrieved from Wikidata under CC0; their references and qualifiers remain part of the verification path.