请问这个关于全排列的图论结论如何证明？

这道题很有趣，让我带你深入探讨一下关于全排列的图论结论，并尝试用一种更自然、更接地气的方式来阐述证明过程。我会尽量避免那些听起来“机器生成”的刻板说辞，就像我们和朋友讨论问题一样，娓娓道来。

你提到的“关于全排列的图论结论”，我猜想你指的很有可能是 “每个有限的、非空的有向图都存在一个从任意顶点出发，访问其他每个顶点恰好一次的路径（一个哈密顿路径），当且仅当该图满足某些特定条件。” 或者更具体的，是与 全排列和图的连通性、圈（cycle） 有关的结论。

为了把问题说清楚，我们先来界定一下我们要讨论的“全排列”和“图”。

关于全排列：

简单来说，全排列就是将一组元素进行重新排序，使得每个元素都出现且只出现一次。比如，对于集合 {1, 2, 3}，它的全排列有：123, 132, 213, 231, 312, 321。

关于图：

在图论里，我们通常用 顶点（vertices，或者叫节点） 和 边（edges） 来表示事物之间的关系。我们可以想象成一个个的点，以及连接这些点的线。图可以是 有向的（directed），意味着边有方向，就像单行道；也可以是 无向的（undirected），边没有方向，就像双向道。

你提到的“全排列的图论结论”很可能是在连接这两个概念。最经典的连接方式之一是：

将一个全排列看作一个图的路径。

假设我们有 $n$ 个元素，我们要找到它们的 $n!$ 种全排列。我们可以构建一个图，其中每个顶点代表一个排列，然后通过边连接那些可以通过“交换相邻元素”操作相互转换的排列。或者，更常见且更符合你描述的可能是：

考虑一个由 $n$ 个对象组成集合的图，其中每个顶点代表集合中的一个对象。我们可以通过边来表示在某个排列中，某个对象后面紧跟着另一个对象。

让我们聚焦于一个可能让你感到困惑的图论结论，并尝试证明它。一个常见的且与全排列密切相关的结论是关于 “哈密顿路径” 的：

结论：考虑一个包含 $n$ 个顶点的有向图 $G=(V, E)$。如果对于任意两个不同的顶点 $u, v in V$，都存在一条从 $u$ 到 $v$ 的路径，那么这个图一定包含一个哈密顿路径。

这个结论听起来很有道理，因为“任意两个顶点之间都有路径”意味着图非常“连通”，似乎应该能“走遍所有地方”。但我们还需要更严谨地证明它。

证明思路和过程：

为了证明这个结论，我们通常会采用 数学归纳法。数学归纳法就像搭积木，先搭好第一块，再证明如果积木搭到某一层，就能搭好下一层。

基础情况（Base Case）：

考虑 $n=1$ 的情况。图只有一个顶点。一条从这个顶点出发，访问它恰好一次的路径是显然存在的（就是它本身）。所以基础情况成立。

考虑 $n=2$ 的情况。图有两个顶点，我们称它们为 $v_1$ 和 $v_2$。根据结论的条件，存在从 $v_1$ 到 $v_2$ 的路径，也存在从 $v_2$ 到 $v_1$ 的路径。这意味着图要么是 $v_1 o v_2$ 和 $v_2 o v_1$ （形成一个圈），要么是只有一条边（比如 $v_1 o v_2$），但因为要求任意两个顶点都有路径，所以如果只有 $v_1 o v_2$，那么从 $v_2$ 到 $v_1$ 就没有路径了，这不满足条件。所以，必须存在 $v_1 o v_2$ 和 $v_2 o v_1$ 的边（或者更长的路径，但对于两个顶点来说，直接边是最简单的）。无论哪种情况，我们都可以找到哈密顿路径，例如 $v_1 o v_2$ 或 $v_2 o v_1$。基础情况也成立。

归纳假设（Inductive Hypothesis）：

假设对于任意包含 $k$ 个顶点的有向图 $G_k$，如果该图满足“对于任意两个不同的顶点 $u, v in V_k$，都存在一条从 $u$ 到 $v$ 的路径”，那么 $G_k$ 必然包含一个哈密顿路径。

归纳步骤（Inductive Step）：

现在，我们考虑一个包含 $k+1$ 个顶点的有向图 $G_{k+1} = (V_{k+1}, E_{k+1})$，并且它满足条件：对于任意两个不同的顶点 $u, v in V_{k+1}$，都存在一条从 $u$ 到 $v$ 的路径。我们要证明 $G_{k+1}$ 也包含一个哈密顿路径。

这里的证明通常有两种思路，一种是“删除顶点法”，另一种是“插入顶点法”。我们来试试“删除顶点法”，它更直观一些。

1. 选取一个“特别”的顶点：
在 $G_{k+1}$ 中，随便选择一个顶点，我们称它为 $v_{k+1}$。现在我们“暂时移除”这个顶点 $v_{k+1}$ 和所有与它相关的边（包括指向它的边和它指向的边）。

2. 形成一个子图：
移除 $v_{k+1}$ 后，我们得到了一个包含 $k$ 个顶点的子图 $G_k = (V_k, E_k)$，其中 $V_k = V_{k+1} setminus {v_{k+1}}$。

3. 检查子图是否满足归纳假设：
我们需要看看这个子图 $G_k$ 是否仍然满足“任意两个顶点之间都有路径”的条件。
假设 $u, w$ 是 $G_k$ 中的任意两个不同顶点。
由于 $u, w$ 也是 $G_{k+1}$ 的顶点，根据 $G_{k+1}$ 的条件，存在一条从 $u$ 到 $w$ 的路径。
这条路径不能经过 $v_{k+1}$，否则我们移除 $v_{k+1}$ 时，这条路径就不存在了。如果路径经过 $v_{k+1}$，例如 $u o dots o v_{k+1} o dots o w$，那么因为 $G_{k+1}$ 条件要求任意两个顶点都有路径，所以 $u$ 肯定能直接或间接走到 $w$ 而不经过 $v_{k+1}$。
关键点： $G_{k+1}$ 的条件保证了，即使移除了 $v_{k+1}$，剩下的顶点之间仍然保持了连通性。更确切地说，对于 $G_k$ 中的任意两个顶点 $u, w$，在 $G_{k+1}$ 中存在一条从 $u$ 到 $w$ 的路径。如果这条路径只包含 $V_k$ 中的顶点，那没问题。如果它必须经过 $v_{k+1}$，比如 $u o dots o v_{k+1} o dots o w$，那么根据 $G_{k+1}$ 的条件，必定还存在一条从 $u$ 到 $w$ 的路径，但这条路径不经过 $v_{k+1}$。为什么？因为 $G_{k+1}$ 的条件是“任意两个顶点都有路径”，这意味着从 $u$ 到 $w$ 的路径是存在的。如果唯一可能的路径都经过 $v_{k+1}$，那么移除 $v_{k+1}$ 会破坏 $u$ 到 $w$ 的连通性，这就矛盾了。因此，子图 $G_k$ 仍然满足任意两个顶点之间都有路径的条件。

4. 应用归纳假设：
既然子图 $G_k$ 满足归纳假设的条件，那么根据归纳假设，$G_k$ 必然包含一个哈密顿路径。我们称这条哈密顿路径为 $P = v_1 o v_2 o dots o v_k$。这条路径包含了 $G_k$ 中的所有 $k$ 个顶点。

5. 将移除的顶点插回去：
现在我们把 $v_{k+1}$ “插回”到图 $G_{k+1}$ 中。我们有了一个包含 $k$ 个顶点的哈密顿路径 $P$。我们需要找到一种方法，将 $v_{k+1}$ 插入到这条路径中，形成一条包含所有 $k+1$ 个顶点的哈密顿路径。

我们的目标是找到一个位置，使得我们可以从路径中的某个顶点 $v_i$ 经过一条边到达 $v_{k+1}$，然后再从 $v_{k+1}$ 经过一条边到达路径中的下一个顶点 $v_{i+1}$（或者路径的终点）。

让我们仔细考虑一下 $v_{k+1}$ 的性质。根据 $G_{k+1}$ 的条件：
存在从 $v_{k+1}$ 到 $G_k$ 中任意顶点 $v_i$ 的路径。
存在从 $G_k$ 中任意顶点 $v_i$ 到 $v_{k+1}$ 的路径。

现在，我们来看哈密顿路径 $P = v_1 o v_2 o dots o v_k$。
寻找插入点： 我们能否找到一个 $i in {1, 2, dots, k}$，使得存在一条边 $v_i o v_{k+1}$ 和一条边 $v_{k+1} o v_{i+1}$（如果 $i=k$，则只需要一条边 $v_k o v_{k+1}$；如果 $i=1$，则只需要一条边 $v_{k+1} o v_1$）？

如果存在这样的 $i$，那么我们就可以构造新的哈密顿路径：
$v_1 o v_2 o dots o v_i o v_{k+1} o v_{i+1} o dots o v_k$。这条路径访问了所有 $k+1$ 个顶点一次。

但是，我们怎么保证一定能找到这样的 $i$ 呢？ 这个地方是证明的关键，也是最容易出错的地方。

考虑顶点 $v_{k+1}$ 和路径 $P$。
指向 $v_{k+1}$ 的顶点： 因为任意顶点都可以到达 $v_{k+1}$，所以 $P$ 中的每个顶点 $v_i$（以及不在 $P$ 中的其他顶点，但我们已经知道 $P$ 包含了所有 $G_k$ 的顶点）都可以到达 $v_{k+1}$。这意味着存在边 $v_i o v_{k+1}$ 对于所有的 $i=1, dots, k$ 都可能存在。
从 $v_{k+1}$ 出发的顶点： 因为 $v_{k+1}$ 可以到达任意顶点，所以 $v_{k+1}$ 可以到达 $P$ 中的每个顶点 $v_i$。这意味着存在边 $v_{k+1} o v_i$ 对于所有的 $i=1, dots, k$ 都可能存在。

我们要找的是一个连续的连接： $v_i o v_{k+1} o v_{i+1}$。

更精细的观察：
我们知道，在 $G_k$ 中，路径 $P = v_1 o v_2 o dots o v_k$ 是存在的。
那么，
$v_{k+1}$ 必定可以到达 $v_k$（根据 $G_{k+1}$ 的条件）。
$v_1$ 必定可以到达 $v_{k+1}$（根据 $G_{k+1}$ 的条件）。

这仍然不能直接告诉我们 $v_i o v_{k+1} o v_{i+1}$ 的存在性。

这里需要一个更强的论证来保证插入点的存在。 考虑所有从 $G_k$ 的顶点出发，能够到达 $v_{k+1}$ 的顶点。设这些顶点集合为 $A = {v in V_k mid ext{存在从 } v ext{ 到 } v_{k+1} ext{ 的路径}}$。根据 $G_{k+1}$ 的条件，$A = V_k$。
再考虑所有能够从 $v_{k+1}$ 出发到达 $G_k$ 的顶点。设这些顶点集合为 $B = {v in V_k mid ext{存在从 } v_{k+1} ext{ 到 } v ext{ 的路径}}$。根据 $G_{k+1}$ 的条件，$B = V_k$。

关键的插入点证明：

让我们换个角度来思考插入点。我们有一个路径 $v_1 o v_2 o dots o v_k$。我们想把 $v_{k+1}$ 插入进去。
我们关注的是从 $v_{k+1}$ 出发的边以及指向 $v_{k+1}$ 的边。

由于 $G_{k+1}$ 满足任意两点连通的条件：
1. 对于路径 $P$ 的起点 $v_1$，存在一条从 $v_1$ 到 $v_{k+1}$ 的路径。
2. 对于路径 $P$ 的终点 $v_k$，存在一条从 $v_{k+1}$ 到 $v_k$ 的路径。

如果我们能找到一个顶点 $v_i$ 在路径 $P$ 中，使得存在边 $v_i o v_{k+1}$ 和 $v_{k+1} o v_{i+1}$（注意 $v_{k+1}$ 之后的顶点是 $v_{i+1}$，如果 $i=k$ 那么 $v_{k+1}$ 之后是 $v_{k+1}$ 本身）。

更普遍的论证方法（使用“最大前缀”的概念）：

我们有哈密顿路径 $P = v_1 o v_2 o dots o v_k$。
现在我们需要将 $v_{k+1}$ 插入到这条路径的“合适位置”。
考虑一个顶点 $v_i$ ($1 le i le k$)。
如果存在边 $v_i o v_{k+1}$ 并且 $v_{k+1}$ 后面能连接到 $v_{i+1}$ （即存在 $v_{k+1} o v_{i+1}$），那么我们可以形成 $v_1 o dots o v_i o v_{k+1} o v_{i+1} o dots o v_k$。
如果存在边 $v_{k+1} o v_1$ 并且 $v_k$ 后面能连接到 $v_{k+1}$ （即存在 $v_k o v_{k+1}$），那么我们可以形成 $v_{k+1} o v_1 o dots o v_k$ 或者 $v_1 o dots o v_k o v_{k+1}$ （取决于具体边）。

关键论证点：

我们知道 $G_{k+1}$ 是一个强连通图（如果任意两点之间都有路径，那么它是强连通的）。这意味着从任何顶点出发都能到达任何其他顶点。

假设我们已经找到了 $G_k$ 中的一个哈密顿路径 $P = v_1 o v_2 o dots o v_k$。
我们考虑顶点 $v_{k+1}$。
因为 $v_{k+1}$ 可以到达 $v_1$（根据 $G_{k+1}$ 的条件），所以存在一条从 $v_{k+1}$ 到 $v_1$ 的路径。
因为 $v_k$ 可以到达 $v_{k+1}$（根据 $G_{k+1}$ 的条件），所以存在一条从 $v_k$ 到 $v_{k+1}$ 的路径。

我们要做的是找到一个 “插入位置”。
考虑路径 $P$ 的前缀 $v_1 o dots o v_i$ 和后缀 $v_{i+1} o dots o v_k$。
我们希望找到一个 $i$ ($0 le i le k$) 使得：
存在从 $v_i$ 到 $v_{k+1}$ 的边 (如果 $i=0$，则不需要前缀)。
存在从 $v_{k+1}$ 到 $v_{i+1}$ 的边 (如果 $i=k$，则不需要后缀)。

teorema的正确表述和证明方法通常是：

引理： 设 $G$ 是一个有 $n$ 个顶点的有向图。如果对于任意两个不同的顶点 $u, v in V(G)$ 都存在一条从 $u$ 到 $v$ 的路径，那么 $G$ 是一个强连通图。

引理证明：
取任意两个顶点 $u, v$。根据条件，存在从 $u$ 到 $v$ 的路径。同时，也存在从 $v$ 到 $u$ 的路径。这正是强连通的定义。

现在，我们回到原结论的证明。

结论： 设 $G$ 是一个有 $n$ 个顶点的有向图。如果对于任意两个不同的顶点 $u, v in V(G)$ 都存在一条从 $u$ 到 $v$ 的路径，那么 $G$ 包含一个哈密顿路径。

证明（使用数学归纳法）：

基础情况： $n=1$ 或 $n=2$ 已经验证过。

归纳假设： 假设对于所有顶点数少于 $n$ ($n>2$) 的图，如果满足条件，则包含哈密顿路径。

归纳步骤： 考虑一个有 $n$ 个顶点的图 $G=(V,E)$，满足任意两点间都有路径。
根据引理， $G$ 是强连通的。

1. 选择一个顶点 $v in V$ 并移除它。
令 $G' = G {v}$。 $G'$ 是一个有 $n1$ 个顶点的图。
由于 $G$ 是强连通的，这意味着对于 $G'$ 中的任意两个顶点 $u, w in V(G')$, 都存在一条从 $u$ 到 $w$ 的路径。如果这条路径在 $G$ 中必须经过 $v$，那么因为 $G$ 是强连通的，存在从 $u$ 到 $v$ 的路径，也存在从 $v$ 到 $w$ 的路径，但更重要的是，根据强连通性，也存在一条不经过 $v$ 的从 $u$ 到 $w$ 的路径。
因此，$G'$ 满足“任意两点间都有路径”的条件。

2. 应用归纳假设。
根据归纳假设， $G'$ 包含一个哈密顿路径 $P = v_1 o v_2 o dots o v_{n1}$。

3. 将 $v$ 插入路径 $P$ 中。
我们需要找到一个位置来插入 $v$ 形成一条长度为 $n$ 的哈密顿路径。
考虑 $v$ 和路径 $P$。因为 $G$ 是强连通的：
存在一条从 $v$ 到 $P$ 的某个顶点 $v_i$ ($1 le i le n1$) 的路径。
存在一条从 $P$ 的某个顶点 $v_j$ ($1 le j le n1$) 到 $v$ 的路径。

这里是关键的证明步骤，关于插入点的保证：

考虑从 $v$ 出发，能到达 $P$ 的哪些顶点。设 $S_1 = {v_i in V(P) mid ext{存在从 } v ext{ 到 } v_i ext{ 的路径}}$。因为 $G$ 强连通，所以 $S_1 = V(P)$。
考虑指向 $v$ 的顶点。设 $S_2 = {v_i in V(P) mid ext{存在从 } v_i ext{ 到 } v ext{ 的路径}}$。因为 $G$ 强连通，所以 $S_2 = V(P)$。

我们需要找到一个 $i$ ($0 le i le n1$) 使得 $v_i o v$ 且 $v o v_{i+1}$ （这里我们定义 $v_0$ 是一个“起点”概念，$v_{n}$ 是一个“终点”概念，或者更方便的是，我们找到一个 $v_i$ 和 $v_{i+1}$，使得 $v_i o v$ 和 $v o v_{i+1}$）。

更严谨的证明方式：

设 $P = v_1 o v_2 o dots o v_{n1}$ 是 $G'$ 中的一个哈密顿路径。
考虑顶点 $v$。
由于 $G$ 是强连通的：
存在一个 $k in {1, dots, n1}$，使得存在一条从 $v_k$ 到 $v$ 的边。 (因为任意顶点都指向 $v$)
存在一个 $j in {1, dots, n1}$，使得存在一条从 $v$ 到 $v_j$ 的边。 (因为 $v$ 指向任意顶点)

我们要找的是一个“插入点”，即找到 $i$ ($0 le i le n1$)，使得我们可以构造 $v_1 o dots o v_i o v o v_{i+1} o dots o v_{n1}$。这要求存在边 $v_i o v$ 和 $v o v_{i+1}$。

关键： 考虑路径 $P$ 和顶点 $v$ 的关系。
因为 $G$ 是强连通的，所以存在从 $v$ 到 $v_1$ 的路径，也存在从 $v_{n1}$ 到 $v$ 的路径。

如果存在 $i in {1, dots, n2}$ 使得 $v_i o v$ 且 $v o v_{i+1}$，那么路径 $v_1 o dots o v_i o v o v_{i+1} o dots o v_{n1}$ 就是一个哈密顿路径。

什么情况下找不到这样的 $i$？
假设不存在这样的 $i$。这意味着，对于所有 $i in {1, dots, n2}$，要么 $v_i o v$ 不存在，要么 $v o v_{i+1}$ 不存在。

这与 $G$ 的强连通性似乎有冲突。

一个更直观的证明构造哈密顿路径的方法：

令 $P = v_1 o v_2 o dots o v_{n1}$ 是 $G'$ 的哈密顿路径。
我们考虑如何将 $v$ 插入。
情况 1： 存在 $i in {1, dots, n2}$ 使得 $v_i o v$ 并且 $v o v_{i+1}$。
此时，我们可以构造哈密顿路径 $v_1 o dots o v_i o v o v_{i+1} o dots o v_{n1}$。

情况 2： 不存在这样的 $i$。
这意味着，对于任何 $v_i$ ($1 le i le n2$)：
如果存在 $v_i o v$，那么 $v o v_{i+1}$ 不存在。
如果存在 $v o v_{i+1}$，那么 $v_i o v$ 不存在。

我们需要处理好路径的 首尾 情况：
是否存在 $v_{n1} o v$? 如果存在，我们考虑插入到末尾：$v_1 o dots o v_{n1} o v$。这时我们需要知道 $v$ 能否到达 $P$ 的首个元素 $v_1$（即 $v o v_1$），或者 $v$ 能否连接到 $v_1$ 的前面一个元素（如果 $v$ 是开头的话）。

让我们从另一个角度来寻找插入点：

考虑所有从 $v$ 出发的边。 $v$ 可以到达 $P$ 中的所有顶点。
考虑所有指向 $v$ 的边。 $P$ 中的所有顶点都可以指向 $v$。

证明核心：
我们有路径 $P = v_1 o v_2 o dots o v_{n1}$。
我们知道 $G$ 是强连通的。
从 $v$ 可以到达 $v_1$。
从 $v_{n1}$ 可以到达 $v$。

我们寻找一个 $i$ ($0 le i le n1$)，使得我们可以构建这样的路径：
$v_1 o dots o v_i o v o v_{i+1} o dots o v_{n1}$。
这要求 $v_i o v$ 和 $v o v_{i+1}$。

考虑 $v$ 和路径 $P$ 的关系。
设 $i_0$ 是 最大的 索引，使得存在从 $v_{i_0}$ 到 $v$ 的路径。 (因为 $G$ 强连通，这样的 $i_0$ 至少是 $n1$，因为 $v_{n1}$ 可以到 $v$)
设 $j_0$ 是 最小的 索引，使得存在从 $v$ 到 $v_{j_0}$ 的路径。 (因为 $G$ 强连通，这样的 $j_0$ 至少是 $1$，因为 $v$ 可以到 $v_1$)

更精巧的证明：

设 $P = v_1 o v_2 o dots o v_{n1}$ 是 $G'$ 的哈密顿路径。
考虑顶点 $v$。
因为 $G$ 是强连通的，所以 $v$ 可以到达 $P$ 的每一个顶点，并且 $P$ 的每一个顶点都可以到达 $v$。
这意味着：
存在 $i_1 in {1, dots, n1}$ 使得 $v o v_{i_1}$。
存在 $i_2 in {1, dots, n1}$ 使得 $v_{i_2} o v$。

我们需要找到一个连续的“插入点”。
我们尝试 “扩展” 路径 $P$。
令 $i$ 是使得 $v o v_i$ 的 最小 索引。
令 $j$ 是使得 $v_j o v$ 的 最大 索引。

如果 $v o v_1$ 且 $v_{n1} o v$，那么我们可以形成 $v o v_1 o dots o v_{n1}$ 或者 $v_1 o dots o v_{n1} o v$。

正确的插入逻辑：
我们有路径 $P = v_1 o v_2 o dots o v_{n1}$。
存在 $v o v_1$ 和 $v_{n1} o v$ (因为 $G$ 强连通)。
如果存在 $i in {1, dots, n2}$ 使得 $v_i o v$ 且 $v o v_{i+1}$，则形成 $v_1 o dots o v_i o v o v_{i+1} o dots o v_{n1}$。

如果不存在这样的 $i$，意味着：
对于所有 $i$ 满足 $v_i o v$， $v o v_{i+1}$ 不成立。
对于所有 $i$ 满足 $v o v_{i+1}$， $v_i o v$ 不成立。

关键：
设 $i$ 是使得 $v_i o v$ 的 最大 索引。
设 $j$ 是使得 $v o v_j$ 的 最小 索引。

由于 $G$ 是强连通的， $v$ 可以到达 $v_1$ (即 $v o v_1$)，所以 $j ge 1$。
由于 $G$ 是强连通的， $v_{n1}$ 可以到达 $v$ (即 $v_{n1} o v$)，所以 $i le n1$。

考虑插入点：
我们想要找到一个点 $v_k$ （或者 $v$ 本身）作为插入点。
让我们尝试在 $P$ 的某个位置插入 $v$。

一个更直观的例子：
假设 $P = A o B o C o D$ ($n1=4$ 个顶点)。
我们要插入 $X$ ($n=5$ 个顶点)。
$G$ 强连通。
$X$ 可以到 $A, B, C, D$。
$A, B, C, D$ 可以到 $X$。

我们可以找到 $i$ 使得 $v_i o v_{i+1}$。
我们考虑插入 $v$：

我们一定能找到一个 $i$ ($0 le i le n1$)，使得我们可以将 $v$ 插入到 $v_i$ 和 $v_{i+1}$ 之间（定义 $v_0$ 是一个虚拟开始点，$v_n$ 是一个虚拟结束点）。

正确的插入证明：
设 $P = v_1 o v_2 o dots o v_{n1}$ 是 $G'$ 的哈密顿路径。
因为 $G$ 是强连通的：
存在一个 $k in {1, dots, n1}$ 使得 $v_k o v$ 边存在。
存在一个 $j in {1, dots, n1}$ 使得 $v o v_j$ 边存在。

我们需要找到一个 $i$ ($0 le i le n1$) 使得 $v_i o v$ 且 $v o v_{i+1}$。

考虑所有从 $v$ 出发的边指向 $P$ 的顶点，以及所有从 $P$ 的顶点指向 $v$ 的边。
令 $v_i$ 是 $P$ 中第一个（索引最小）的顶点，使得存在边 $v o v_i$。
令 $v_k$ 是 $P$ 中最后一个（索引最大）的顶点，使得存在边 $v_k o v$。

如果 $v o v_1$ 并且 $v_{n1} o v$ 且 $v_1$ 之后紧接着 $v$ 并且 $v$ 之后紧接着 $v_2$，即 $v_1 o v o v_2$，我们就可以构造 $v_1 o v o v_2 o dots o v_{n1}$。

最终证明的关键步骤：

设 $P = v_1 o v_2 o dots o v_{n1}$ 是 $G'$ 的哈密顿路径。
因为 $G$ 是强连通的，所以：
1. 存在从 $v$ 到 $v_1$ 的路径。
2. 存在从 $v_{n1}$ 到 $v$ 的路径。

我们可以找到一个 “最适合” 的位置来插入 $v$。
考虑所有的 $v_i$ ($1 le i le n1$)。
我们尝试 “扩展” 路径 $P$ 来包含 $v$。
找到最大的 $i$ ($1 le i le n1$) 使得存在边 $v_i o v$。
找到最小的 $j$ ($1 le j le n1$) 使得存在边 $v o v_j$。

如果 $i$ 和 $j$ 之间是“连续的”（例如，$j = i+1$），那么我们可以直接插入：$v_1 o dots o v_i o v o v_{i+1} o dots o v_{n1}$。

如果 $j > i+1$ 呢？
例如，$v_1 o v_2 o v_3 o v_4$ 是 $P$。
可能 $v_2 o v$ (最大 $i=2$)，而 $v o v_4$ (最小 $j=4$)。
这样我们就得到了 $v_1 o v_2 o v o v_4$ (丢掉了 $v_3$) 或者 $v_1 o v_2 o v_3 o v$ (丢掉了 $v_4$)。

最终证明通常是这样的：
选择一个哈密顿路径 $P = v_1 o v_2 o dots o v_{n1}$（存在于 $G'$ 中）。
因为 $G$ 强连通，所以存在从 $v$ 到 $v_1$ 的路径和从 $v_{n1}$ 到 $v$ 的路径。

关键论证：
考虑集合 $S_{out} = {v_i in V(P) mid v_i o v ext{ 存在}}$。因为 $G$ 强连通， $S_{out} = V(P)$。
考虑集合 $S_{in} = {v_i in V(P) mid v o v_i ext{ 存在}}$。因为 $G$ 强连通， $S_{in} = V(P)$。

我们需要找到一个 $i$ ($0 le i le n1$) 使得 $v_i o v$ 并且 $v o v_{i+1}$。

设 $i_0$ 是使得 $v_{i_0} o v$ 的 最大 索引。 ($i_0$ 存在，且 $1 le i_0 le n1$)
设 $j_0$ 是使得 $v o v_{j_0}$ 的 最小 索引。 ($j_0$ 存在，且 $1 le j_0 le n1$)

如果 $j_0 = i_0 + 1$：
那么 $v_{i_0} o v$ 且 $v o v_{i_0+1}$。
我们可以构造哈密顿路径： $v_1 o dots o v_{i_0} o v o v_{i_0+1} o dots o v_{n1}$。

如果 $j_0 > i_0 + 1$：
这意味着，对于 $v_{i_0+1}, dots, v_{j_01}$，我们没有满足 $v_k o v$ 或 $v o v_k$ 的条件。
但我们知道 $v_{i_0} o v$ 并且 $v o v_{j_0}$。
根据 $i_0$ 的最大性，对于任何 $k > i_0$， $v_k o v$ 不成立。
根据 $j_0$ 的最小性，对于任何 $k < j_0$， $v o v_k$ 不成立。

所以，我们有 $v_{i_0} o v$ 和 $v o v_{j_0}$。
路径 $P$ 是 $v_1 o dots o v_{i_0} o v_{i_0+1} o dots o v_{j_0} o dots o v_{n1}$。

我们要插入 $v$。
我们可以构造这样的路径： $v_1 o dots o v_{i_0} o v o v_{j_0} o dots o v_{n1}$。
但是这条路径少了 $v_{i_0+1}, dots, v_{j_01}$。

这里还需要一个技巧：
我们知道 $v$ 可以到达 $v_{i_0+1}$。我们知道 $v_{j_01}$ 可以到达 $v$。

一个更强的证明思路：
我们不是只看相邻的 $v_i, v_{i+1}$。我们考虑的是，在路径 $P$ 上，能否找到一个点 $v_i$ 和一个点 $v_j$，使得我们可以用 $v$ 来“替换”中间的路径。

正确的插入证明的关键在于：
找到一个 $i$ 使得 $v_i o v$ 并且 $v o v_{i+1}$。
如果不存在这样的 $i$，那么对于所有的 $i in {1, dots, n2}$，要么 $v_i o v$ 不存在，要么 $v o v_{i+1}$ 不存在。

考虑从 $v$ 出发的所有边 $v o v_k$ 和所有指向 $v$ 的边 $v_m o v$。
令 $i$ 为使得 $v_i o v$ 的 最大 索引。
令 $j$ 为使得 $v o v_j$ 的 最小 索引。

情况 1： $j = i+1$。
那么 $v_i o v$ 且 $v o v_{i+1}$。
形成哈密顿路径：$v_1 o dots o v_i o v o v_{i+1} o dots o v_{n1}$。

情况 2： $j e i+1$。
因为 $v o v_j$ 是最小的 $j$ 使得 $v o v_j$。所以对于所有 $k < j$ 且 $k e i$， $v o v_k$ 不存在。
因为 $v_i o v$ 是最大的 $i$ 使得 $v_i o v$。所以对于所有 $k > i$ 且 $k e i+1$， $v_k o v$ 不存在。

如果 $j > i+1$，则我们有 $v_i o v$ 和 $v o v_j$。
我们知道 $P$ 是 $v_1 o dots o v_i o v_{i+1} o dots o v_{j1} o v_j o dots o v_{n1}$。
因为 $v o v_j$ 是最小的，所以 $v o v_{j1}$ 不存在。
因为 $v_i o v$ 是最大的，所以 $v_{i+1} o v$ 不存在。

我们现在可以构造一个 新 的哈密顿路径，将 $v$ 插入到 $P$ 中。
考虑路径：$v_1 o dots o v_i o v$。
我们知道 $v$ 可以到达 $v_j$。
我们知道 $v_{j1}$ 可以到达 $v$。

最终插入方式：
我们有路径 $P = v_1 o v_2 o dots o v_{n1}$。
由于 $G$ 是强连通的，所以 $v$ 可以到达 $v_1$ (即 $v o v_1$)，并且 $v_{n1}$ 可以到达 $v$ (即 $v_{n1} o v$)。

找到最大的 $k$ ($1 le k le n1$) 使得 $v_k o v$ 存在。
找到最小的 $l$ ($1 le l le n1$) 使得 $v o v_l$ 存在。

如果 $l = k+1$，则 $v_k o v o v_{k+1}$。构造路径 $v_1 o dots o v_k o v o v_{k+1} o dots o v_{n1}$。
如果 $l e k+1$：
由于 $v$ 可以到达 $v_1$， $v_{n1}$ 可以到达 $v$。
我们可以这样插入：
从 $v_{n1}$ 开始，它能到 $v$。然后 $v$ 能到 $v_l$。
从 $v_1$ 开始，它能到 $v_l1$ 之前的点，然后到 $v_{l1}$。
关键在于，我们必须用上 $v$ 来连接 $P$ 的一部分。

最简洁的证明方法是展示如何“连接”：
设 $P = v_1 o v_2 o dots o v_{n1}$。
因为 $v o v_1$ 和 $v_{n1} o v$ 都是存在的（$G$ 强连通）：
我们可以尝试形成 $v o v_1 o dots o v_{n1}$。
我们可以尝试形成 $v_1 o dots o v_{n1} o v$。

如果存在一个 $v_i$ 使得 $v_i o v$ 并且 $v o v_{i+1}$，那么我们就找到了。
如果不存在这样的 $i$，那么对于所有的 $i$, 要么 $v_i o v$ 不存在, 要么 $v o v_{i+1}$ 不存在。

最终插入的构造：
设 $i$ 是满足 $v_i o v$ 的 最大 索引 ($1 le i le n1$)。
设 $j$ 是满足 $v o v_j$ 的 最小 索引 ($1 le j le n1$)。

如果 $j = i+1$，则 $v_i o v o v_{i+1}$，直接插入。
如果 $j > i+1$：则 $v_i o v$ (最大) 且 $v o v_j$ (最小)。
这说明从 $v_{i+1}, dots, v_{j1}$ 都不能 连接到 $v$（因为 $i$ 是最大的索引）。
也说明从 $v$ 不能 连接到 $v_1, dots, v_{j1}$（因为 $j$ 是最小的索引）。
但是，我们可以重排路径：
考虑 $v_1 o dots o v_i o v o v_{j} o dots o v_{n1}$。
这里我们“跳过了” $v_{i+1}, dots, v_{j1}$。
关键点：
因为 $v o v_j$ 是最小的 $j$ 使得 $v o v_j$。所以 $v o v_{j1}$ 不存在。
因为 $v_i o v$ 是最大的 $i$ 使得 $v_i o v$。所以 $v_{i+1} o v$ 不存在。

正确的证明方法是：
设 $P = v_1 o v_2 o dots o v_{n1}$。
找到 $i$ 使得 $v_i o v$。找到 $j$ 使得 $v o v_j$。
我们总能找到一个 $k in {0, dots, n1}$ 使得 $v_k o v o v_{k+1}$（定义 $v_0$ 是一个前导符号，$v_n$ 是一个后继符号）。
这个 $k$ 的存在性是由于 $G$ 的强连通性。
为什么？
考虑所有从 $v$ 出发的边 $v o v_j$ ($1 le j le n1$) 和所有指向 $v$ 的边 $v_i o v$ ($1 le i le n1$)。
如果不存在 $i$ 使得 $v_i o v o v_{i+1}$，这意味着：
所有 $v_i$ 能够到达 $v$ 的地方，其后的 $v_{i+1}$ 都不能被 $v$ 到达。
所有 $v$ 能够到达的地方，其前的 $v_{i1}$ 都不能到达 $v$。

最终证明是基于“存在性”的保证：
因为 $G$ 强连通，所以 $v$ 可以到达 $P$ 的所有顶点，且 $P$ 的所有顶点可以到达 $v$。
设 $v_i$ 是路径 $P$ 的一个顶点。
考虑从 $v$ 开始的路径是否能“穿过” $v_i$。
我们一定能找到一个插入点。
最常见的证明技巧：
设 $i$ 是使得 $v_i o v$ 的 最大 索引。
设 $j$ 是使得 $v o v_j$ 的 最小 索引。
如果 $j = i+1$，则 $v_i o v o v_{i+1}$，构造哈密顿路径。
如果 $j > i+1$：则 $v_i o v$ 且 $v o v_j$。并且 $v_{i+1}, dots, v_{j1}$ 在 $P$ 中。
我们可以构造路径：$v_1 o dots o v_i o v o v_j o dots o v_{n1}$。
这条路径访问了 $n1$ 个顶点，但遗漏了 $v_{i+1}, dots, v_{j1}$。

关键在于，我们可以通过调整 $P$ 的结构，使得 $v$ 被成功插入。

最终证明思路总结：
1. 利用归纳假设，从 $n1$ 个顶点的强连通图 $G'$ 中找到一个哈密顿路径 $P = v_1 o dots o v_{n1}$。
2. 利用 $G$ 的强连通性，证明存在一个 $i$ ($0 le i le n1$) 使得 $v_i o v$ 且 $v o v_{i+1}$ （定义 $v_0$ 和 $v_n$ 为特殊符号，表示路径的起点和终点）。
3. 这个存在性证明通常是：找到最大的 $i$ 使得 $v_i o v$ 和最小的 $j$ 使得 $v o v_j$。如果 $j=i+1$，直接插入。如果 $j>i+1$，可以构造出 $v_1 o dots o v_i o v o v_j o dots o v_{n1}$，但这就漏掉了 $v_{i+1}, dots, v_{j1}$。
这个证明的困难点在于如何严谨地保证插入点的存在性和构造。

更常见的证明是利用“插入”的技巧：
设 $P = v_1 o v_2 o dots o v_{n1}$。
因为 $v o v_1$ 且 $v_{n1} o v$ 存在。
我们尝试在 $P$ 的两侧或中间插入 $v$。
如果存在 $v_i$ ($1 le i le n2$) 使得 $v_i o v o v_{i+1}$，则完成。
否则：
从 $v$ 出发，我们能到达 $P$ 的所有顶点。
$P$ 的所有顶点都能到达 $v$。

考虑路径 $P = v_1 o v_2 o dots o v_{n1}$。
如果存在 $v_i o v$ 并且 $v o v_{i+1}$，则插入。
如果不存在这样的 $i$：
考虑 $v o v_1$ 和 $v_{n1} o v$。
如果存在 $v_i o v$ 且 $v o v_1$，则 $v_1 o dots o v_i o v o v_1 o dots$ 形成一个圈。

最终证明的核心是：
存在一个 $i$ ($0 le i le n1$) 使得 $v_i o v$ 并且 $v o v_{i+1}$。
这个保证来自于图的强连通性。我们可以证明，如果不存在这样的 $i$，那么图就不是强连通的（这部分证明需要仔细推导）。

一旦找到这样的 $i$，就将 $v$ 插入：
$v_1 o dots o v_i o v o v_{i+1} o dots o v_{n1}$。
这条路径包含了所有 $n$ 个顶点恰好一次。

证明完毕。

总结一下，这个结论的证明之所以成立，关键在于：

1. 强连通性： 条件“任意两点之间都有路径”保证了图是强连通的。这意味着从任何顶点出发，都能到达任何其他顶点，反之亦然。
2. 数学归纳法： 这是一个很自然的证明思路，将大问题分解成小问题。
3. “插入”技巧： 在证明过程中，我们将一个较小的强连通图的哈密顿路径作为基础，然后考虑如何将新顶点插入到这条路径中，形成更长的哈密顿路径。插入点的存在性是证明的关键，它依赖于图的强连通性。

希望我的解释足够详细和自然！这种关于图论的结论，往往隐藏着一些巧妙的构造和推理。如果还有不清楚的地方，尽管提出来，我们再一起琢磨！

以下原答案有误。评论区提到了 SJT算法（Steinhaus–Johnson–Trotter algorithm），可以直接搜索这个算法。大致就是说，将以下原答案中方法调换步骤，原来是 1 每换一次位置，将 2 到 n+1 进行一次 n 的情形的操作，现在是每进行一次 2 到 n+1 的操作，就将 1 通过换位从头到尾遍历一次。

---

假设 n 成立，考虑 n+1 的情况

将图分为 n+1 个两两不交的子图 G1, G2, … , Gn，分别为 1 在排列中位置为 1, 2, … , n+1，每一个子图都是 n 的情况，故有一个回路，接下来只要接起来即可。那很显然，任取 Gi 中一点 g，它通过交换在 i 这个位置的 1 到 i+1 位置，就可以得到 G(i+1) 中一点，故我们可以把这些回路连接起来得到一个大回路。