Pre-Requisite for Graphs with Unique Topological Sort

Question

Let's assume that a graph in question is a DAG (directed acyclic graph).

Question: can I conclude that such graph will have a unique topological sort if, and only if, only one of its vertices has no incoming edges?

In other words, is having only one vertex with no incoming edges necessary (but not sufficient) to generate a unique topological sort?

Answer 1

A topological sort will be unique if and only if there is a directed edge between each pair of consecutive vertices in the topological order (i.e., the digraph has a Hamiltonian path). Source

A Hamiltonian path just means that a path between two vertices will only visit each vertex once, it does not mean though that one vertex must have no incoming edges. You can have a Hamiltonian path that is in fact a cycle. This would still generate a unique topological sort (of course it would be a cycle as well if that is important to you).

Hope this helps

Answer 2

Haaaaa, ok. sorry for the misunderstanding.

In this case I assume that you are right, here is a sketch of proof:

We have a unique topological sort => We have only one vertex that it is legal to put in the first place => For every vertex, except one, it is not legal to put in the first place => For every vertex, except one, we have incoming edges.

Hope that now I answered your question....

Answer 3

No! The graph below has only one vertex with no incoming edges, and have 2 possible solutions.

1 -> 2
3 -> 4
3 -> 1
4 -> 2

Two solutions are:

2 0 3 1
2 3 0 1