-1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ What have you tried? Have you looked up the definitions in this question? (In particular, "strict acyclic digraph" is not very common, so you might want to include that in your question.) Do the definitions make sense? What do you think the proof should look like, even if you can't fill in the missing pieces? $\endgroup$
    – Misha Lavrov
    Commented Dec 28, 2021 at 18:40
  • $\begingroup$ As stated in the above comment, I don't know what "strict" means, but if you consider a digraph with two vertices and two edges going from vertex $a$ to vertex $b$, then switching the direction of either of the edges will result in a cycle, so this would be a counterexample. $\endgroup$
    – Steven Creech
    Commented Dec 28, 2021 at 19:21
  • $\begingroup$ @MishaLavrov thanks for letting me know the ways I could improve the question. I tried my best to do so. $\endgroup$
    – AmirhosseinMHD
    Commented Dec 28, 2021 at 19:25

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .