关于Michael Sipser《计算理论》中3-正则图存在性证明的疑问求助

嘿，我完全懂你读Michael Sipser《计算理论》时卡在这个定理证明上的感受——这类构造性证明光看抽象描述容易犯懵，不如先从具体案例入手，再逆向推导一般规律，会清晰很多。

先从具体小例子拆解 #

我们先拿几个最小的符合条件的n来构造，亲手画一遍就能get到核心思路：

案例1：n=4（最小的大于2的偶数） #

节点集 $V = {v_1, v_2, v_3, v_4}$
构造边集 $E$：

• 每个节点和另外三个节点都连边，也就是完全图 $K_4$。
• 此时每个节点的度数都是3，完美满足3-正则图的定义。

案例2：n=6 #

把6个节点排成正六边形（$v_1$到$v_6$按顺时针顺序排列）：

1. 先给每个节点连相邻的两个节点（比如$v_1-v_2$、$v_2-v_3$、…、$v_6-v_1$），这时候每个节点的度数是2；
2. 再给每个节点连对面的节点（$v_1-v_4$、$v_2-v_5$、$v_3-v_6$），每个节点的度数加1，变成3。

• 这样就得到了一个6节点的3-正则图，你可以自己画一下，每条边都不重复，每个节点刚好有3个邻居。

案例3：n=8 #

用“分组配对”的思路构造：

1. 把8个节点分成两组${v_1,v_2,v_3,v_4}$和${v_5,v_6,v_7,v_8}$；
2. 组内每个节点连相邻两个节点（比如$v_1-v_2$、$v_2-v_3$、$v_3-v_4$、$v_4-v_1$；$v_5-v_6$同理），此时每个节点度数+2；
3. 组间一一配对：$v_1-v_5$、$v_2-v_6$、$v_3-v_7$、$v_4-v_8$，每个节点度数+1。

• 最终每个节点度数刚好是3，完全符合3-正则图的要求。

推广到一般的偶数n（n=2k，k≥2） #

现在回到定理的构造性证明，核心就是把上面案例的思路抽象化：
设n是大于2的偶数，令$n=2k$（k是≥2的整数），构造图$G=(V,E)$：

1. 节点集：$V = {v_0, v_1, ..., v_{n-1}}$（共n个节点）；
2. 边集构造分三步（保证每个节点最终度数为3）：
   • 第一步（循环相邻边）：对每个$i$，添加边$(v_i, v_{(i+1)\mod n})$，每个节点度数+1；
   • 第二步（对称配对边）：对每个$i$，添加边$(v_i, v_{(i+k)\mod n})$，因为$n=2k$，所以每个节点的对称节点唯一且不重复，每个节点度数+1；
   • 第三步（交叉配对边）：对每个$i$，添加边$(v_i, v_{(i+1+k)\mod n})$，这一步利用n是偶数的条件，保证每条边不重复，每个节点度数+1；

• 三步完成后，每个节点的度数刚好是3，且所有边都合法（无重复、无自环），这样就构造出了符合要求的3-正则图。

额外补充：为什么n必须是偶数？ #

这里可以先理解必要性，帮助你更清楚定理的前提：
3-正则图的总度数是$3n$（每个节点3度，共n个节点），而根据图论的基本定理，总度数必须是偶数（每条边贡献2度）。因此$3n$必须是偶数，3是奇数，所以n必须是偶数——这也解释了为什么定理限定n是大于2的偶数。

内容的提问来源于stack exchange，提问作者R.A.K