Editing Component (graph theory) (section)

==Number of components==
The number of components of a given finite graph can be used to count the number of edges in its [[spanning forest]]s: In a graph with <math>n</math> vertices and <math>c</math> components, every spanning forest will have exactly <math>n-c</math> edges. This number <math>n-c</math> is the [[matroid]]-theoretic [[Rank (graph theory)|rank]] of the graph, and  the [[matroid rank|rank]] of its [[graphic matroid]]. The rank of the [[dual matroid|dual cographic matroid]] equals the [[circuit rank]] of the graph, the minimum number of edges that must be removed from the graph to break all its cycles. In a graph with <math>m</math> edges, <math>n</math> vertices and <math>c</math> components, the circuit rank is {{nowrap|<math>m-n+c</math>.{{r|wilson}}}}

A graph can be interpreted as a [[topological space]] in multiple ways, for instance by placing its vertices as points in [[general position]] in three-dimensional [[Euclidean space]] and representing its edges as line segments between those points.{{r|wood}} The components of a graph can be generalized through these interpretations as the [[Connected component (topology)|topological connected components]] of the corresponding space; these are equivalence classes of points that cannot be separated by pairs of disjoint closed sets. Just as the number of connected components of a topological space is an important [[topological invariant]], the zeroth [[Betti number]], the number of components of a graph is an important [[graph invariant]], and in [[topological graph theory]] it can be interpreted as the zeroth Betti number of the graph.{{r|tutte-betti}}

The number of components arises in other ways in graph theory as well. In [[algebraic graph theory]] it equals the multiplicity of 0 as an [[eigenvalue]] of the [[Laplacian matrix]] of a finite graph.{{r|cioaba}} It is also the index of the first nonzero coefficient of the [[chromatic polynomial]] of the graph, and the chromatic polynomial of the whole graph can be obtained as the product of the polynomials of its components.{{r|read}} Numbers of components play a key role in the [[Tutte theorem]] characterizing finite graphs that have [[perfect matching]]s{{r|tutte-matching}} and the associated [[Tutte–Berge formula]] for the size of a [[maximum matching]],{{r|berge}} and in the definition of [[graph toughness]].{{r|chvatal}}