问题
塔特 1966 证明:4-连通平面三角剖分是哈密顿的( «面全三角 » 的强结构)。猜想: «三角剖分 » 条件可去——每个 4-连通平面图都哈密顿。它与 Barnette 猜想(22 号:3-连通 3-正则二部平面图有哈密顿圈)是 «平面哈密顿 » 版图的两大残余——Barnette 的 «对偶 » 恰是 «4-连通平面 + 面均偶 »( «三角剖分的 «二部版 »»)。
主要概念
塔特机器
塔特的证明走 «Tutte 路 »( «平面图有 « 穿越面 » 的路径 »)+ «拼接 »: «4-连通 » 保证 «Tutte 路 » 的 «拼接 » 不 «破 »; «三角剖分 » 用于 «局部 » 的 «面结构 » 控制。 «去三角 » 的困难: «四边形面 » 的 «拼接 » 会 «碎 »—— «对偶 » 视角: «Barnette 的 « 立方 » 世界 » 与 «本问的 « 对偶 » 世界 » 共享 «3-连接 » 的 «机器 »。
特例进展
①4-连通平面 «弦 » 图( «三角化 » 弱化)已证;② «4-连通 « 欧拉 »»( «面均偶 »—— «Barnette 对偶 »)的情形与 Barnette 猜想等价( «平面 « 对偶 » 保哈密顿 »—— «哈密顿圈 ⟺ « 对偶 » 的 «面 2-染 »»);③ «Barnette–Goodey»: «面为 4-与 6-边形 » 的 «立方 » 图哈密顿( «轻 » 特例已证)。
主要命题与证明
命题 1(塔特定理骨架) 4-连通平面三角剖分哈密顿。
梗概 «Tutte 路 » 定理: «2-连通平面图中 « 指定边 » 的两端有 « 穿越面 » 的路径 »( «3-连通 » 时 « 强 »); «4-连通 » 的 «无割 » 保证 «路 » 的 «两端 » 可 «接 » 成圈—— «面结构 »( «三角 »)用于 «局部 » 补段( «路外 » 顶点的 «面邻 » 结构 »)的 «拼接 » 收尾。□
命题 2(对偶翻译) 平面图 G 哈密顿 ⟺ 对偶 G* 的面可 2-染色( «哈密顿圈 » 的 «内外 » 染 «对偶面 »)—— «4-连通平面 » 的 «对偶 » 是 « « 无割 » 的 « 立方 » 图 »:本猜想 ⟹ «Barnette 型 » 的 «立方 » 陈述( «3-连通 « 平面 » + « 面均偶 » »)。
进展与文献
Tutte 1946( «Tutte 路 »)、1966( «4-连通三角剖分 »);Barnette 1980 的猜想与 Goodey 的特例;Fleischner–... 的 «哈密顿 « 平面 »» 综述;Brinkmann–... 的 «构造性 » 实验( «无反例 » 的穷举到相当规模)。开放核心: «去三角 » 的 «拼接 » 机器( «四边形面 » 的 «局部 » 引理缺失); «Barnette ⟹ 本问 » 的 «桥 »( «对偶 » 的 «精确 » 关系)与 «可读四色 »(48 号)的路标网络。