如何证明DAG存在唯一拓扑序则存在哈密顿路径？是否有反例？

命题证明（唯一拓扑排序 → 存在哈密顿路径） #

采用反证法推导：

• 设DAG $G$ 的唯一拓扑排序为 $T = [v_1, v_2, ..., v_n]$。
• 假设 $G$ 不存在哈密顿路径，则必然存在至少一对相邻节点 $v_i$ 和 $v_{i+1}$（$1 \leq i < n$），图中没有边 $v_i \to v_{i+1}$——否则 $v_1 \to v_2 \to ... \to v_n$ 就是一条哈密顿路径，与假设矛盾。
• 构造新序列 $T'$：将 $T$ 中的 $v_{i+1}$ 与 $v_i$ 交换位置，得到 $[v_1, ..., v_{i-1}, v_{i+1}, v_i, v_{i+2}, ..., v_n]$。
• 验证 $T'$ 是合法拓扑排序：
  • 原拓扑排序 $T$ 中所有边均满足“前节点指向后节点”，而 $v_{i+1}$ 无法指向 $v_i$（否则与 $T$ 是拓扑排序矛盾，DAG中无反向边）；
  • 所有涉及 $v_i$ 或 $v_{i+1}$ 的边，在 $T'$ 中仍保持“前节点指向后节点”的关系：
    • 若有边 $u \to v_{i+1}$，则 $u$ 在 $T$ 中位于 $v_{i+1}$ 之前，要么是 $v_1$ 到 $v_{i-1}$（在 $T'$ 中仍在 $v_{i+1}$ 前），要么是 $v_i$（但不存在 $v_i \to v_{i+1}$ 的边，无需考虑）；
    • 若有边 $v_i \to w$，则 $w$ 在 $T$ 中位于 $v_i$ 之后，在 $T'$ 中仍在 $v_i$ 之后；
    • 其他不涉及这两个节点的边，位置关系与 $T$ 一致，自然满足拓扑排序要求。
• $T'$ 是与 $T$ 不同的拓扑排序，这与 $G$ 有唯一拓扑排序的前提矛盾。因此假设不成立，$G$ 必然存在哈密顿路径。

是否存在反例？ #

不存在反例。上述证明通过反证法严格推导了命题的必然性，任何满足“唯一拓扑排序”条件的DAG，都不可能不存在哈密顿路径。

补充：反向蕴含关系（存在哈密顿路径 → 唯一拓扑排序） #

如你所说，这一方向的证明较为直接：

• 设 $G$ 的哈密顿路径为 $v_1 \to v_2 \to ... \to v_n$，这条路径本身就是一个拓扑排序。
• 对于任意其他可能的拓扑排序，由于路径中每个 $v_i$ 都有边指向 $v_{i+1}$，在拓扑排序中 $v_i$ 必须位于 $v_{i+1}$ 之前，无法交换相邻节点的位置。因此不存在其他合法的拓扑排序，即拓扑排序唯一。

内容的提问来源于stack exchange，提问作者SotirisD