# The strongly connected components are the same in a directed graph and its reverse

Last edited: 2026-01-28

Lemma

Let $G = (V,E)$ be a directed graph and $G^R = (V,E^R)$ be its reverse . Both $G$ and $G^R$ have the same strongly connected components.

# Proof

For any two vertices $x,y \in V$ which are strongly connected in $G$ we need a path $p_{x,y}$ connecting $x$ to $y$ and path $p_{y,x}$ connecting $y$ to $x$.

The reverse of the path $p_{x,y}^R$ connects $y$ to $x$ in $G^R$ and $p_{y,x}^R$ connects $x$ to $y$ in $G^R$.

Therefore if two vertices are strongly connected in $G$ they are strongly connected in $G^R$.

As $G = \left (G^R \right )^R$ this also gives us that if two vertices are strongly connected in $G^R$ they are strongly connected in $G$.

Thus by the definition of strongly connected components they must be identical in $G$ and $G^R$.