Le transposé garde les composantes, pas le quotient

La preuve tient en une ligne. Il y a un chemin de $u$ à $v$ dans $G^{\mathsf{T}}$ si et seulement s'il y a un chemin de $v$ à $u$ dans $G$ — on lit le même chemin à l'envers. Donc

$$(u⇝v\text{ et }v⇝u)\text{ dans }{G}^{\mathsf{T}}⟺(v⇝u\text{ et }u⇝v)\text{ dans }G,$$

et c'est la même condition, écrite dans l'autre ordre. La relation « mutuellement accessibles » est symétrique : elle ne voit pas la différence entre les deux graphes.

Ce qui change est le quotient. Les arcs entre composantes, eux, sont retournés : si $G$ a un arc $C_i\to C_j$, alors $G^{\mathsf{T}}$ a l'arc $C_j\to C_i$. Le quotient de $G^{\mathsf{T}}$ est celui de $G$ à l'envers. En particulier :

Et c'est exactement le levier de Kosaraju. On veut, pour ramasser une composante et une seule, partir d'une composante dont on ne peut pas sortir. Le premier parcours identifie une source de $G$ ; le retournement en fait un puits ; le parcours ne déborde plus. Le graphe transposé n'est pas une astuce technique : c'est le moyen de transformer « on sait par où entrer » en « on ne peut pas sortir ».