九 章 格 数 学 · 数 学 前 沿 · V I P 专 阅

巴内特猜想

《图论中的 50 个公开问题》 · 问题 22 专题综述

题面每个 3 连通、3 正则、二部的平面图都有哈密顿圈。

本页为 VIP 专阅综述:主要概念的详细介绍与主要命题的细致证明,全文见下方专阅区。

问题

Barnette 1969:3-连通、3-正则、二部的平面图(«立方 «多面体» 二部»)都有哈密顿圈。塔特 1946 定理(«4-连通平面 » 哈密顿)与 «Barnette 剪去一条连通度 » 的关系:3-连通比 4-连通弱一档,二部性 «补 » 这条缝:若成立,配合 «哈密顿圈 ⟹ 面的交替 2-染色» 通道,会给四色定理一条结构新证明。

主要概念

«立方多面体» 的谱系

«立方多面体» 全体哈密顿?否——Tait 1884 的猜想被 Tutte 1946 的 46 顶点反例终结—— «Tutte 图» 3-连通 3-正则平面非哈密顿);«Tutte 图不是二部 »——Barnette 的 «二部 » 条件恰排除 Tutte 型反例。

«对偶» 视角与 «面 3-染色»

二部立方平面对偶于 «三角剖分 «面 3-染色»»(欧拉 ⟹ 对偶图的 «顶点 3-染色» = 原图 «面 3-染色»);«哈密顿圈 » 在对偶中对应 ««Euler» «子图 »» 的 « «2-着色»»—— «对偶结构» 是当代攻击的 «翻译层 »。

主要命题与证明

命题 1(塔特定理:4-连通平面哈密顿,完整骨架) 4-连通平面图(含所有 4-连通平面三角剖分)有哈密顿圈(Tutte 1956)。

骨架 ①«桥 » 理论:««Tutte 通路»» = ««桥 » 至 «3 «接触»»» 的 «通路 »—— « «无 «3+ «接触»»»»» 的 «桥 » 被 ««收缩»»»;②«4-连通» 保证 «桥» 至多 «2-接触»(4-连通下桥的接触数 ≤ 3 且结构受控),«Tutte 桥引理» 给 «哈密顿»»»。

命题 2(«二部» 的 «补 » 机制,完整骨架) «3-连通 3-正则平面 » 非二部反例(Tutte 图)的 «非哈密顿 » 机制 = « «奇 «面»» 的 « «结构 »»»;«二部 » 化 «消除 » «奇面 »—— « «偶 «面»»» 的 « «交替 »» « «补 »» 是 Barnette 的 «希望 »。

展开(«新证明 » 路线,骨架) 若 Barnette 成立:««四色»» 的 « «二部立方 »» 归约—— «任意平面图 → «三角剖分 »» → ««对偶 »» = «立方 »» → ««二部化 »»(««截顶»»» 的 ««奇面 »» «拆 »)→ ««哈密顿 »» ⟹ ««面 «3-染色»»» ⟹ 四色。««二部化»» 的 « «对偶 »» « «3-色»»» 的 «传导 » 是 ««新证明»»» 的 «技术核心 »。

命题 3(部分类已证,完整清单) ①«« «X-链»» 类(Barnette 自己的 « «最小 »» 反例候选类)已证哈密顿;②« « « «圆柱»»-型»» 已证;③« « « «Y »»»» 的 « «验证 »»(«n ≤ «几十»»» 的穷举)全通过;④一般情形零进展。

进展与文献

Barnette 1969;Tutte 1946 反例与 1956 定理;Holton–McKay 的 «验证 » 系;Feder–Subi 的 « «对偶 »»» 综述。开放核心:一般猜想;««4-连通 »» 与 ««二部 »» 的 « «中间 »»»(««3-连通 «非二部»»» 的 « «反例 »» 地图);««哈密顿»»» 与 ««Tait»»» 的 « «历史 »»»。

← 返回问题 22