= Solution
Suppose a <Directed acyclic graph> has a <Hamiltonian path> $(w_1,\ldots,w_n)$. Every edge $(w_j,w_{j+1})$ forces $w_j$ to precede $w_{j+1}$ in every <topological sort>. Transitivity forces the entire order $(w_1,\ldots,w_n)$, so the <topological sort> is unique and every consecutive pair is joined by the requisite edge. No edge can point backwards in this path order, since that edge together with part of the path would form a <directed cycle>.
Conversely, if a <topological sort> $(w_1,\ldots,w_n)$ has an edge from every entry to the next, those edges form a <graph path> through all <vertices> exactly once. Thus \b[the displayed order is itself a <Hamiltonian path>].
The <unique topological ordering criterion> says that uniqueness alone already forces the consecutive-edge condition. If $(w_j,w_{j+1})$ were absent, swapping these adjacent entries would preserve every edge constraint: only their mutual order changes, and a reverse edge is already forbidden by the original <topological sort>. This would produce a second order. Consequently, for a <Directed acyclic graph>, \b[having a <Hamiltonian path>, having a unique <topological sort>, and having consecutive edges in a <topological sort> are equivalent]. The source's $>$ notation is read as “appears earlier”, consistent with its explicitly directed edges.
Back to article page
