# Strongly connected components in a directed graph

Let $$G$$ be an arbitrary directed graph. Does $$G$$ always have the same strongly connected components on $$G$$ as on $$G^*$$? Here, $$G^*$$ is the inverted graph of $$G$$ (i.e., $$(u,v)\in E \rightarrow (v,u) \in E^*$$).

I'm thinking yes because otherwise the algorithm of Kosaraju would not work at all? But do not have another explanation for this.

• Have you tried proving your suspicion? Try using the definition of strongly connected component. – Yuval Filmus Aug 20 '19 at 20:29
• Your title said the graph is regular but the question says it's arbitrary. I deleted "regular" from the title, since requiring th graph to be regular doesn't change the answer. – David Richerby Aug 21 '19 at 9:19

Two vertices $$x,y$$ lie in the same strongly connected component if there is a directed path from $$x$$ to $$y$$ and a directed path from $$y$$ to $$x$$.
There is a directed path from $$x$$ to $$y$$ in $$G$$ iff there is one from $$y$$ to $$x$$ in $$G^*$$. This easily implies that $$G$$ and $$G^*$$ have the same strongly connected components.