Graph Components are Equivalence Classes

Theorem

The components of a graph are equivalence classes under the relation is connected to on the set of vertices.

Proof

We have that Graph Connectedness is Equivalence Relation.

The result follows directly from the definition of component.

$\blacksquare$

Sources

• 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): $\S 2.3$: Connected Graphs: Problem $44$