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: $\mathrm{\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