# Graph Connectedness is Equivalence Relation

## Theorem

Let $G = \struct {V, E}$ 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$.

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 = \tuple {u, u_1, u_2, \ldots, u_{k - 1}, u_k, v}$ be a walk from $u$ to $v$
- $W_2 = \tuple {v, v_1, v_2, \ldots, v_{k - 1}, v_k, w}$ be a walk from $v$ to $w$.

Then $W = \tuple {u, u_1, u_2, \ldots, u_{k - 1}, u_k, v, v_1, v_2, \ldots, v_{k - 1}, v_k, w}$ 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

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