TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 10

10) Let G = (V, E) be a simple and directed graph and G_R its reduction. Prove that G_R is acyclic!

Solution

given the graph $G=(V,E)$
the reduction $G_{R}=(V_{R},E_{R})$

Assume there is a cycle in $G_{R}$. All vertexes along the cycle are in the set $C\subset V_{R}$
within these cycle: $\exists v,w\in C:vSw$ (there is a walk between any of these nodes)

$\Rightarrow C$ is a strongly connected component of $G_{R}$ and therefore also of $G$
$\Rightarrow V_{R}$ does not include all strongly connected components of $G$ which is clearly a contradiction to the fact fact that the reduction includes all strong connected components of $G$

Therefore $G_{R}$ is acyclic