Graph Connectedness is an Equivalence Relation

Theorem

Let $G = \left({V, E}\right)$ be a graph.

Let $\to$ denote the relation is connected to on the set $V$.

Then $\to$ is an equivalence relation.

Proof

Let $u, v, w$ be arbitrary vertices of a graph $G$.

Checking in turn each of the criteria for equivalence:

Reflexive

By definition, all vertices are connected to themselves.

Hence $\to$ is reflexive.

Symmetric

Suppose $u \to v$. Then by definition there exists a walk $W$ between $u$ and $v$.

Note that there is nothing in the definition of connectedness to insist that the walk has to be in a particular direction.

So by definition, if $u \to v$ then $v \to u$.

Hence $\to$ is symmetric.

Transitive

Suppose $u \to v$ and $v \to w$.

Let:

• $W_1 = \left({u, u_1, u_2, \ldots, u_{k-1}, u_k, v}\right)$ be a walk from $u$ to $v$
• $W_2 = \left({v, v_1, v_2, \ldots, v_{k-1}, v_k, w}\right)$ be a walk from $v$ to $w$.

Then $W = \left({u, u_1, u_2, \ldots, u_{k-1}, u_k, v, v_1, v_2, \ldots, v_{k-1}, v_k, w}\right)$ is a walk from $u$ to $w$.

Hence $u \to w$, and so $\to$ is transitive.

Thus is connected to is an equivalence relation.

$\blacksquare$

Sources

• Gary Chartrand: Introductory Graph Theory (1977): $\S 2.3$: Problem $44$