CODEWITHSUNDEEP
graphdirected-acyclic-graphstopological-sort
Edmeral
Edmeral

Reputation: 185

Multiple hamiltonian paths and topological sorting

We know that if we have a hamiltonian path in a DAG that the topological sorting will be unique, but what if we had multiple hamiltonian paths, wouldn't that mean that there can be multiple topological sortings: a different one for each one of those paths?

Upvotes: 0

Views: 1079

Answers (1)

templatetypedef
templatetypedef

Reputation: 372814

Every DAG either has zero Hamiltonian paths or one Hamiltonian path. Here's one way to see this. Suppose that there are two or more. Look at the first nodes on those Hamiltonian paths that differ from one another; let's call them x and y. This means that in one path, x comes before y, and in the other path, y comes before x. But this means that there's a cycle in the graph: we can go from x to y using a subpath of the first Hamiltonian path and then we can go from y to x using a subpath of the second Hamiltonian path. That's impossible, though, because DAGs can't have cycles.

This means that the claim you're making is vacuously true - "if a graph has two different Hamiltonian paths, then it has two different topological orderings" is true because the antecedent is always false.

Upvotes: 3

Related Questions