# Proof

From the definition of connectivity in a directed (or undirected) graph $$G(V,E)$$ it follows that two vertices $$x,y\in V$$ are connected (strongly connected), if there is a path from $$x$$ to $$y$$ (respectively also from $$y$$ to $$x$$. We define the relation "$$\leftrightarrow$$" as follows:

$x\leftrightarrow y\Longleftrightarrow x\text{ and }y\text{ are (strongly) connected.}$

It is sufficient to show that "$$\leftrightarrow$$" defines an equivalence relation on the set $$V$$, because then it follows immediately that any vertex $$v\in V$$ can be chosen as a representative of a unique equivalence class of vertices $$V'\in V/_\leftrightarrow$$ such that the subgraphs (respectively subdigraphs) $$G[V']$$ contain the vertex $$v$$.

We have to show three properties of "$$\leftrightarrow$$" in order to prove, that it is an equivalence relation:

$$(1)$$ Reflexivity: $$x\leftrightarrow x$$ for all $$x\in V$$ This is trivial, since any vertex is connected to itself.

$$(2)$$ Symmetry: $$x\leftrightarrow y\Longleftrightarrow y\leftrightarrow x$$ for all $$x,y\in V$$ This follows immediately from the definition of connectivity (strong connectivity) of $$G$$.

$$(3)$$ Transitivity: If $$x\leftrightarrow y$$ and $$y\leftrightarrow z$$, then $$x\leftrightarrow z$$ for all $$x,y,z\in V$$ If $$P_1=v_0v_1\ldots v_k$$ is a path from $$x$$ to $$y$$ and $$P_2=u_0u_1\ldots u_l$$ from $$y$$ to $$z$$, then we have $$v_0=x$$, $$v_k=u_0=y$$ and $$u_l=z$$. Thus, we can merge both path and create the walk$W:=v_0v_1\ldots v_ku_1\ldots u_l$from $$x$$ to $$z$$. In general, this walk is not a path, since it may contain some identical vertices other then $$v_k=u_0$$. In this case, the walk contains cycles, and we can "short-cut" the walk to create a path by removing any detours. Since, by construction, such a path from $$x$$ to $$z$$ always exists, we have $$x\leftrightarrow z$$.

Thank you to the contributors under CC BY-SA 4.0!

Github:

### References

#### Bibliography

1. Krumke S. O., Noltemeier H.: "Graphentheoretische Konzepte und Algorithmen", Teubner, 2005, 1st Edition