本文最后更新于 2025年4月29日 上午
现有一无向图 G，若存在两个顶点 i,j 满足 d(i)+d(j)≥n 则令 G=G+(i,j)，直到不再有这样的顶点对为止，最终得到的图称为 G 的闭合图，记作 C(G)。
现在我们已知一个显然结论：对于一个图 G，C(G) 是唯一的，这个一感觉就对完了。
我们需要证明：C(G) 存在 H 回路是 G 存在 H 回路的充要条件。
首先我们将 C(G) 分解为 G∪L,L={e1,e2,....,em}。
然后我们只需要证明，对于一个图 G，G′=G+(i,j),d(i)+d(j)≥n 存在 H 回路是 G 存在 H 回路的充要条件就可以通过数学归纳法证明上述命题成立。
以下简称图 G 满足存在 H 回路为 H(G)。
显然，H(G)→H(G′) 是正确的，我们只需要证明 H(G′)→H(G) 的情况即可。
考虑 d(i)+d(j)≥n，且在 G 中不存在边 (i,j)，则对于图 G 一定存在至少两个点 x,y 满足存在边 (x,j),(y,i),(x,y)（鸽巢原理），发现 x,y 本质相同，i,j 也是同样的，所以我们可以直接混淆它们。
假设 G′ 有一 H 回路包含 (i,j)。（若不包含则命题直接成立）
则回路长成这个样子：
i→...→x→y→...→j→i
现在我们取走边 (i,j)，则由上述条件一定有一哈密顿回路：
i→...→x→j→...→y→i
则命题得证。