Definitions

# Connected component (graph theory)

In an undirected graph, a connected component or component is a maximal connected subgraph. There are three connected components in the diagram to the right.

Two vertices are defined to be in the same connected component if there exists a path between them. Since this definition doesn't really make sense in an arbitrary directed graph (there could be a path from $x$ to $y$ but not one from $y$ to $x$), for directed graphs one uses the similar concept of a strongly connected component.

A graph is called connected when there is exactly one connected component.

## An equivalence relation

In an undirected graph, the existence of a path between two vertices u and v is an equivalence relation, since:

• There is a trivial path of length zero from any vertex to itself. (reflexivity)
• If there is a path from u to v, it also has a path from v to u. (symmetry)
• If there is a path from u to v and a path from v to w, we can attach them together to form a path from u to w. (transitivity)

The connected components are then the equivalence classes of this relation.

## Connection with the Laplacian

The multiplicity of 0 as an eigenvalue of the Laplacian matrix of a graph is equal to the number of connected components in the graph.

## Complexity Theory

Connected components are useful because often algorithms or theorems can be applied to each connected component individually, taking advantage of it being a connected graph, and combine these solutions to obtain a solution for the entire graph. For example, if we find a minimum spanning tree or a maximum matching for each connected component, their union is a minimum spanning forest or maximum matching for the entire graph.

Many computational problems related to connected components are complete for the complexity class SL, such as:

• Are two vertices in the same connected component? Different connected components?
• Is a graph connected? Not connected?
• Do two graphs have the same number of connected components? Different number of components?
• Is the number of connected components even? Is it odd?

Since SL=L, these problems all lie in L and so can be solved with a deterministic machine in O(log n) space. However, the most practical algorithms for them are randomized algorithms using random walks.