Suppose we have an arbitrary directed graph $G$.
We create a related new graph $G'$ by reversing every edge in $G$.
Is this statement true or false?: $G$ is acyclic if and only if $G'$ is acyclic.
Reversing a directed graph preserves acyclicness
directed graphsgraph theory
Best Answer
Suppose $G$ has a cycle; call this path $C$. Reversing every edge in $C$ to produce $C'$, this reverse cycle exists in $G'$. Thus, $G$ having a cycle implies $G'$ having a cycle.
By the same reasoning, if $G'$ has a cycle, then it can be reversed to find a cycle in $G$. Thus, $G'$ having a cycle implies $G$ having a cycle.
Putting these two facts together, $G$ has a cycle if and only if $G'$ has a cycle.
And we can take the negation of both sides to say the same thing about acyclicness.