Graph Connectedness is Equivalence Relation

From ProofWiki
Jump to navigation Jump to search

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