Component (graph theory)

[share]

In graph theory, a component, sometimes called a connected component, of an undirected graph is
a subgraph in which any two vertices are connected to each other by paths, and
which is connected to no additional vertices in the supergraph.

A vertex with no incident edges is itself a component.
A graph that is itself connected has exactly one component, consisting of the whole graph.

[share]

Definition


Let G be a graph.

Let H be a subgraph of G such that:
H is connected
H is not contained in any connected subgraph of G which has more vertices or edges than H has.

Then H is a component of G.


The number of components

The number of components is an important topological invariant of a graph.

In topological graph theory it can be interpreted as the zeroth Betti number of the graph.

In algebraic graph theory it equals the multiplicity of 0 as an eigenvalue of the Laplacian matrix of the graph.

It is also the index of the first nonzero coefficient of the chromatic polynomial of a graph.

Numbers of components play a key role in the Tutte theorem characterizing graphs that
have perfect matchings, and in the definition of graph toughness.