3连通平面图的连通生成子图（讲义）.md

3连通平面图的连通生成子图（讲义）

汇报人：李岳昆

问题背景

哈密尔顿问题在一般图论上有充分或必要的刻画。本部分讨论平面图的哈密尔顿问题，围绕一个问题展开：4 连通平面图是哈密尔顿的，该问题首次被惠特尼(Whitney)提出，是他在证明了 4 连通极大平面图是哈密尔顿的，随后提出的进一步猜想。该问题后来被塔特(Tutte)证明，后经托马森(Thomasson)进一步简化证明并做了推广：4 连通平面图不仅是哈密尔顿的，且是哈密尔顿连通的。

• 欧拉图：遍历每一条边，源于著名的柯尼斯堡七桥问题。
• 哈密尔顿图：遍历每一个顶点，源于著名的正十二面体环球旅行问题。

塔特与托马森的证明过程都使用了如下的归纳论点：

他们首先将图分割成几个子图，最后将子图的哈密尔顿圈合并成整个图的哈密尔顿圈。这种证明过程可以迅速用**分治(divide and conquer)**的方法解决。然而，由于分解后的子图并不总是（边） 不相交的，即使是验证该算法为多项式时间的有界性也并不容易。塔特定理引入了内部4连通图，该证明是在托马森证明的基础上，避免了分解成相交子图。证明思路十分具有建设性，并因此产生了一种寻找哈密尔顿圈的简易算法。

虽然原来的图是 4 连通的，但是被分解成的子图不再是 4 连通的。然而，他们继承了一些很好的属性，我们称之为 “内部 4 连通”。类比塔特与托马森的证明过程，此处我们同样定义“内部3连通”图，进而讨论3连通图上的因子理论。

为什么是连通生成子图？

为了找到图中的哈密尔顿圈，我们要保留原图中所有的点，同时去掉一些“没用”的边（如图所示），这正是**生成子图（Spanning Subgraph）**的定义。

通常来说，为了寻找哈密尔顿圈，我们希望每个节点的度都为2——这就意味着每个节点都没有“多余的边”，遍历该节点只需要“一进一出”即可完成。由此引出：**二度节点都是对我们有利的节点，不需要考虑在二度节点上去掉某条边。**记二度点集为 $W(G)$。

我们的目标是什么？

寻找哈密尔顿圈，就要明确哪些点的边是“多余”的，进而去掉这些没用的度。当前已经知道：二度节点是自己人，我们需要找到敌人是谁。

最首要的问题，是敌人究竟有多少？即“边多余”的节点有多少？我们不妨换个角度思考：破掉一个哈密尔顿圈需要几个点？答案是两个。

当然，由于题目中给出的研究条件是：3连通图。我们还要考虑在圈的内部存在多连通情况，因此本文中我们破掉一个哈密顿圈最少需要的点可能是两个，也可能是三个，我们要一起讨论。

能破掉哈密顿圈的点就是我们要严格监控的对象，这些点在某种程度上决定着整个图是否存在哈密尔顿圈。

定理阐述

**定义 ：**对于平面图 $G$ ，若其任意顶点 $v$ 在 $G$ 的生成子图 $F$ 中都有： $a\leqslant deg_F(v) \leqslant b$ ，则称 $F$ 为 $G$ 的一个 $[a,b]$ -因子。

记 $G$ 中与 $v$ 相邻的点集为 $N_G(v)$ ，$(u,v)$ 代表点 $u$ 和 $v$ 之间的边，$\delta (G)$ 为 $G$ 中最小的度。一个连通因子就是一个连通的生成子图，一个连通的[2,2]-因子就是一个哈密尔顿圈，且连通的[1,k]-因子就是一个最大度为 $k$ 的生成树，因子理论的成果目前并是不很多，本部分我们着重探讨平面图。

一个令人熟知的结论便是塔特的：4连通图都有[2,2]-因子。巴纳特证明了所有3连通图都有 2连通的[2,15]-因子，Gao证明了所有3连通图都有 2连通的[2,6]-因子，此外Gao还证明了存在没有[2,5]-因子的 3连通图。通过假设最小度大于等于4，我们证明了该问题的边界：[2,3]-因子。

定理 1 ：$G$为最小度大于等于4的 3连通图。对于任意三个点：$u,v,s: (u, v), (v, s)\in E(G)$，$G$ 总存在一个连通的[2,3]-因子 $F$，包含边$(u,v), (v,s)$ 使得 $deg_F (u)=2, deg_F (v)=2$，且 $deg_F(s)=3$.

定理证明

• 外部圈为简单圈时，内部3连通图是2连通的（上述破圈引理）$\Rightarrow$ 若 $u,v$ 为两个割点，则整个图分成两个连通分量 $\Rightarrow$ 若其中一个割点在外部圈上，则去掉该点后，整个图可变成线性I3CP图
• 定义 1：对于生成子图 $F$ 中 $deg_F(v_1)=1$ 和 $deg_F(v_2)=2$ 两个点，如果在原图二度节点集合中去掉这两个点，二度节点存在哈密尔顿路；在非二度节点中去掉这两个点，非二度节点存在哈密尔顿圈，那么我们就称 $F_G(v_1,v_2)$ 为原图 $G$ 的一个连通因子。

定义1说明了一件什么事情？除了这两个特殊的点 $(v_1,v_2)$，其他的点几乎完成了哈密顿连通的证明，因此这两个点成为了限制整个图的因子，我们要着重关注。

• **引理 5：**令 $G$ 为2连通的I3CP图，假设对于所有 $v\in Inn(G)$，$deg_G(v)\geqslant 4$。那么对于任何 $v_1 \in Out(G)$ 和 $v_2\in V(G)-{v_1}$，存在一个连通因子 $F_G(v_1 , v_2)$。

当一个连通的I3CP图 $G$ 是线性且为可分离的，我们就把这些块命名为 $B_1, B_2, B_3, ..., B_n$，以便 $$ V(B_{k-1})\cap V(B_k)={b_k},\quad 2\leqslant k \leqslant n $$

• 引理 7 ：让 $G$ 是一个可分离的线性I3CP图，其块末端都不是 $K_2$。同时在每个区块 $B_i$ 中，对于所有$v\in Inn(B_i)$，$deg_{B_i}(v)=4$。那么对于任何 $v_1 \in Out(B_1)-{b_2}$ 和任何 $v_2\in V(B_n)-{b_n}$，存在一个满足定义 1 的连通因子 $F(v_1, v_2)$。

• 我们将 $G$ 嵌入到平面中，使 $v\in Out(G)$。那么 $H:=G-{v}$ 是一个2连通的I3CP图，$u, s\in Out(H)$。通过对 $H$ 适用引理 5，有一个满足定义 1 的连通因子 $F_H(u, s)$。注意，由于 $\delta(G)=3，W(H)=\phi$，那么 $$ F=F_H(u, s)\cup (v, u)\cup(v, s)​ $$ 是一个理想的连通[2，3]-因子。这样就完成了定理 1 的证明。

引理证明

上面的证明都是十分显然的，需要证明的部分只有引理5 和引理7：

引理5的证明

令 $C$ 为 $G$ 的边界圈，$G'$ 为 $G-{v_1}$.

• Case 1：$G'$ 是条路

我们将得到的路径命名为 $P=(b_1,b_2,\cdots,b_{n+1})$ ，注意到 $b_1$ 是二度节点，因此， $P\cup (b_{n+1},v_1)$ 是 $G$ 的理想因子，除非 $v_2=b_1$，若 $v_2=b_1$ 则考虑 $P\cup(b_1,v_1)$ 同理。

• Case 2：$G'$ 是2连通的

显然 $G'$ 是一个2连通的I3CP，且对于 $v\in Inn(G'), \quad deg_{G'}(v)\geqslant 4$，令 $N_{G}(v_1)\cap C = {b_1,b_2}$. 当 $v_2 \notin {b_1,b_2}$ ，令 $v_1' := b_1, \quad v_2' := b_2$ ，$v_3' := v$ 对于任意的点 $V(G')-{b_1,b_2}$ 根据 定理6 的归纳假设，存在一个连接因子 $F$，因此$Out(G')-Out(G)\subset Inn(G)$，$deg_{G'}(v)\geqslant deg_G(v)-1\geqslant 3$ 对于所有的 $v\in Out(G')-Out(G)$。因此 $W(G')-{b_1,b_2}\subset W(G)$。我们通过加一条边 $(b_1, v_1)$ 将 $F_G(v_1,v_2)$ 变成 $F_{G'}(v_1',v_2',v_3')$ ，因此这满足上述连通因子F的定义，且是一个理想的连通因子F。

• Case 3：$G'$ 是分离的但不是一条路

由上面定理知：$G'$ 是线性I3CP的，