Editing Cyclomatic number (section)

== 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 graph]]s, the cyclomatic number {{mvar|r}} is easily computed using the formula:
<math display=block>r = e - v + c,</math>
where {{mvar|e}} is the number of edges in the given graph, {{mvar|v}} is the number of [[vertex (graph theory)|vertices]], and {{mvar|c}} is the number of [[component (graph theory)|connected components]].
<ref name="berge">{{citation|title=The Theory of Graphs|first=Claude|last=Berge|authorlink=Claude Berge|publisher=Courier Dover Publications|year=2001|isbn=9780486419756|pages=27–30|contribution=Cyclomatic number|url=https://books.google.com/books?id=h5BjnaoKyOwC&pg=PA27}}.</ref>

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 (vector space)|dimension]] of the [[cycle space]] of a graph, in terms of [[matroid theory]] as the corank of a [[graphic matroid]], and in terms of [[topology]] as one of the [[Betti number]]s 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 metric]]s as part of the definition of [[cyclomatic complexity]] of a piece of code. The concept was introduced and called the cyclomatic number by [[Gustav Kirchhoff]].<ref name="Kotiuga2010">{{citation|author=Peter Robert Kotiuga|title=A Celebration of the Mathematical Legacy of Raoul Bott|url=https://books.google.com/books?id=mqLXi0FRIZwC&pg=PA20|year=2010|publisher=American Mathematical Soc.|isbn=978-0-8218-8381-5|page=20}}</ref><ref name="Hage1996">{{citation|author=Per Hage|title=Island Networks: Communication, Kinship, and Classification Structures in Oceania|url=https://books.google.com/books?id=ZBdLknuP0BYC&pg=PA48|year=1996|publisher=Cambridge University Press|isbn=978-0-521-55232-5|page=48}}</ref>