Show that every strict acyclic digraph contains an arc whose reversal results in an acyclic digraph.

Question

I was self-studying Bondy's book on graph theory and I was stuck in this question. can anybody help me?

a strict acyclic digraph is a digraph that if node i and j are connected and if j and k the node i and k are also connected.

I tried reshaping the graph in a way that make solving the problem easier but my attempts to solve the problem this way all failed.

thanks for helping.

Answer 1

try using topological sorting i.e, try to name the vertices from 1 to n in an order in which any node with a larger number has no directed edge to a node with a smaller number for example node 1 can have an edge to node 3 but node 3 can't have an edge to node 1. this is the topological representation of an acyclic graph.

then note that for a graph to be strictly acyclic every node with a smaller number has to be connected to any node with a larger number for example 2 should have a directed edge to 3, 4, 5, ..., n. because we know that 2 is connected to 3 and 3 is connected to 4 so 2 also has to be connected to 4 and you can generalize this up to n.

now in the stated topological representation of strict acyclic digraph, consider changing the direction of the directed edge between node 1 and 2 to a directed edge from 2 to 1 and keeping all other edges as before, this way by reversing a directed edge you still get an acyclic digraph but not a strict one.

hope it was helpful.