Component (graph theory)
Number of components

The number of components of a given finite graph can be used to count the number of edges in its spanning forests: In a graph with n {\displaystyle n} vertices and c {\displaystyle c} components, every spanning forest will have exactly n − c {\displaystyle n-c} edges. This number n − c {\displaystyle n-c} is the matroid -theoretic rank of the graph, and the rank of its graphic matroid. The rank of the 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 m {\displaystyle m} edges, n {\displaystyle n} vertices and c {\displaystyle c} components, the circuit rank is m − n + c {\displaystyle m-n+c}.

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. The components of a graph can be generalized through these interpretations as the 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.

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. 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. Numbers of components play a key role in the Tutte theorem characterizing finite graphs that have perfect matchings and the associated Tutte–Berge formula for the size of a maximum matching, and in the definition of graph toughness.
keywords:existence, detectable_format:number_highlighted_sections[4]