四色定理之結構性證明

所有「公認的證明」都依賴電腦。「結構性的人類證明」是公開的開放問題。本研究的目標就是嘗試這個方向。

本研究採用三種「結構性」的操作型定義之至少一項：

• (S1) 嚴格：證明不依賴對 ≥ 數十個 bounded-radius configurations 之 case-by-case reducibility 驗證。允許少量（≤ 5 個）小型 unavoidable configurations，但每個 reducibility 證明須具高度結構統一性。
• (S2) 寬鬆：可由人類在 < 100 頁內驗證，不需任何 computer-verified case enumeration。
• (S3) 概念性：將 4CT reduce 為某個獨立成立、且結構更簡單的命題。

這三層構成 sliding scale。本研究主鏈在 (S2) 與 (S3) 上無條件成立；(S1) 取決於對 Grötzsch 7-8 個配置的 audit 結果（見 §7）。

定理（主定理 5.1）：對所有 finite simple planar graph $G$，$\chi(G) \leq 4$，前提為 Grötzsch 1959 定理（Thomassen 2003 短證明）為 (S1)-合格證明。

證明骨架：

1. (4CT-V) ⟺ (4CT-F)（Tutte 1949 + 1954 之 cycle-cocycle duality）
2. (4CT-F) on bridgeless planar reduces to (4CT-F) on 4-edge-connected planar（2-edge-cut + 3-edge-cut splitting + S₃-glueing）
3. 4-edge-connected planar ⟺ dual triangle-free planar（duality）
4. Grötzsch 1959 ⟹ dual 3-colorable ⟹ dual 4-colorable
5. Tutte 1954 flow-coloring duality ⟹ primal 4-flow

• (4CT-V)（Vertex form，主形式）：對所有 finite simple planar graph $G$，$\chi(G) \leq 4$。
• (4CT-T)（Tait 1880）：對所有 bridgeless cubic planar multigraph $G$，$\chi'(G) = 3$（邊染色 3 色）。
• (4CT-D)（Triangulation）：對所有 simple planar triangulation $T$，$\chi(T) \leq 4$。
• (4CT-F)（Tutte 1949 Flow form）：對所有 bridgeless planar graph $G$，存在 nowhere-zero 4-flow（等價於 nowhere-zero $\mathbb{Z}_2 \times \mathbb{Z}_2$-flow）。

本研究主鏈經由 (4CT-F) 走 flow 形式，因為 Tutte 對偶在 flow 語言下最自然。

定義（dual graph）：給定 plane graph $G$ 之 embedding，其 dual $G^*$ 之頂點為 $G$ 之 faces，每邊 $e \in E(G)$ 對應一邊 $e^* \in E(G^*)$ 連接 $e$ 兩側之 faces。

對偶具有 involutive 性質：$(G^*)^* = G$（在 plane embedding 之意義下）。

對 plane graph $G$ 與其 dual $G^*$，

$$\chi(G^*) = \min\{k : G \text{ has nowhere-zero } \mathbb{Z}_k\text{-flow}\}.$$

對 $k = 4$ 之特例：$G^*$ 為 4-colorable ⟺ $G$ 有 nowhere-zero 4-flow。由 Tutte 1949（4-flow ⟺ $\mathbb{Z}_2 \times \mathbb{Z}_2$-flow）將其轉為 $\mathbb{Z}_2 \times \mathbb{Z}_2$ 之 flow 語言，後續 §4 之切割化約即在此語言上操作。

(⟹) 給 $G^*$ 之 proper $k$-coloring $\chi$。對每邊 $e \in E(G)$，定義 $f(e) := \chi(v^*) - \chi(u^*) \pmod k$，其中 $u^*, v^*$ 為 $e$ 兩側之 face。

Nowhere-zero：$u^*$ 與 $v^*$ 在 $G^*$ 中相鄰（透過 $e^*$），故 $\chi(u^*) \neq \chi(v^*)$ ⟹ $f(e) \neq 0$。

Kirchhoff conservation：對每頂點 $v$，其周圍 $d$ 個 faces 形成 dual cycle $C_v^*$。$v$ 之每邊 $e_i$ 之 flow 為 $f(e_i) = \chi(w_{i+1}^*) - \chi(w_i^*)$。守恆計算為 telescoping sum：

$$\sum_{i=0}^{d-1} f(e_i) = \sum_{i=0}^{d-1} (\chi(w_{i+1}^*) - \chi(w_i^*)) = \chi(w_d^*) - \chi(w_0^*) = 0$$

由 $C_v^*$ closed: $w_d^* = w_0^*$。故 Kirchhoff 守恆律自動成立。

(⟸) 反向構造：給 nowhere-zero flow $f$，沿任 spanning tree 累積 $f$ 值定義 $\chi$。well-definedness 由 Whitney 1932 之 lemma（dual cycle ⟺ primal bond）+ Kirchhoff 對 cocycle 之零和性質保證。

引理 5.4.0（$\mathbb{Z}_2 \times \mathbb{Z}_2$ 之 2 元 zero-sum 唯一性）：在 $\mathbb{Z}_2 \times \mathbb{Z}_2$ 中，對任 $x, y \neq 0$，若 $x + y = 0$，則 $x = y$。

引理 5.2（2-edge-cut splitting）：設 $G$ 為 bridgeless planar 含 2-edge-cut $\{e_1, e_2\}$，將 $G$ split 為 $G_1, G_2$（將 $e_1, e_2$ 之另一端 identify 為 boundary vertex $w_1, w_2$，不 contract）。則：

$$G \text{ 有 nowhere-zero 4-flow} \iff G_1, G_2 \text{ 皆有 nowhere-zero 4-flow}.$$

S₃-action 之 glue：若 $f_1(e_1) = f_1(e_2) = a$ 且 $f_2(e_1) = f_2(e_2) = b$ 且 $a \neq b$，選 $\sigma \in S_3 \cong \mathrm{Aut}(\mathbb{Z}_2 \times \mathbb{Z}_2)$ 使 $\sigma(b) = a$，對 $G_2$ 之每邊 $e$ 套用 $f_2'(e) := \sigma(f_2(e))$。$f_2'$ 仍為 nowhere-zero 4-flow（$\sigma$ 為 group automorphism），且 boundary 自動對齊。

引理 5.5.0：在 $\mathbb{Z}_2 \times \mathbb{Z}_2$ 中，三非零元 $x_1, x_2, x_3$ 滿足 $x_1 + x_2 + x_3 = 0$ 當且僅當 $\{x_1, x_2, x_3\} = \{(1,0), (0,1), (1,1)\}$（即三非零元各一）。

引理 5.3（3-edge-cut splitting）：設 $G$ 為 3-edge-connected planar，3-edge-cut 為 $\{e_1, e_2, e_3\}$。令 $G_1, G_2$ 各 identify boundary 為 $w_1, w_2$（degree 3）。則 $G$ 有 4-flow ⟺ $G_1, G_2$ 皆有。

S₃-action on ordered triples：$\mathbb{Z}_2 \times \mathbb{Z}_2$ 之三非零元有 $3! = 6$ 種 ordered permutations；$|S_3| = 6$。$S_3$ 對此 6 個 ordered triples 之作用為 simply transitive（任兩 triples 由唯一 $\sigma$ 映之）。

選 $\sigma$ 滿足 $\sigma(b_1) = a_1$ 與 $\sigma(b_2) = a_2$。由 $\sigma$ 為 group automorphism：

$$\sigma(b_3) = \sigma(b_1 + b_2) = a_1 + a_2 = a_3$$

第三個 boundary 自動對齊。整個 glue 完全沒有 case analysis。

對 bridgeless planar $G$，每次 2-edge-cut 或 3-edge-cut splitting 嚴格減少邊數（split 後兩部分之邊數和等於原邊數，但每部分邊數嚴格小於原圖；由 strong induction）。

反覆 split 直至每部分為 4-edge-connected。Reduction 至 4-edge-connected planar 之 nowhere-zero 4-flow 問題。

定理 3.3（Grötzsch 1959）：每 triangle-free planar graph 為 3-vertex-colorable。

本文之主鏈將 Grötzsch（Thomassen 2003 短證明）作為 black-box external input，不 自行重建 specimens。原因：

1. Thomassen 2003「A short list color proof of Grötzsch's theorem」之原文已是 < 10 頁完整短證明，廣為接受
2. 本主鏈之核心貢獻為「Tutte duality + connectivity reduction → 將 4CT reduce 至 Grötzsch」之鏈，不 為 Grötzsch 之獨立重建
3. 本文之先前嘗試重建 specimens 受 sub-agent 與主 agent 之審查均指出含計算錯誤，自證水準不足以支撐獨立 specimens

依 Phase 4 gap-attack 001 之分析（僅作 reviewer audit 之 informational reference）：

強化命題 $\Phi_T$：對 2-connected triangle-free plane graph + outer face $C$ + 兩相鄰 precolored vertices on $C$，3-coloring 可 extend，except for finite list of forbidden configurations。

結構：

• 對 $|V(G)| + |E(G)|$ 做 induction
• 4 個 reducers（R1: separating short cycle、R2: degree-2 vertex、R3: low-degree boundary vertex、R4: short separating path），由 split-and-glue + S₃-action 統一處理
• 3-4 個 base / boundary configurations（R5: small graphs、F1-F3: specific precoloring patterns），由 case-by-case Kempe-chain argument 處理

總計 7-8 個配置。

(S1) 嚴格定義「≤ 5 個小型 unavoidable configurations + 統一原理」是一個主觀的閾值。在數學文獻中沒有 universally accepted 的「嚴格 (S1)」定義。本研究的 Strict / Moderate / Loose 三層只是把這個主觀性 explicit 化，讓 reviewer 能 explicitly 選擇要在哪一層判定。

更重要的是：(S2) + (S3) 是 mathematically well-defined 的標準（< 100 頁、化約成獨立命題），而本研究主鏈在這兩層上都無條件成立。

典型代表：

• 路線 1（Penrose tensor）：Penrose evaluation $P_{\text{sgn}}(H) > 0$ ⟺ Tait coloring 存在；recursion 含負號故無 closed-form positive recursion
• 路線 6（Tropical / amoeba）：dual symmetry of multivariate Tutte = chromatic-flow duality（已知）；無新代數 input
• 路線 10（Discrete Morse）：critical cell ⟺ 4-coloring 為 Forman 機械之 homotopy invariance 之直接重述

結構性原因：plane embedding 在代數結構中僅以 sign convention / dual symmetry 形式體現，不提供獨立 positivity 工具。

典型代表：

• 路線 3（Minimal counterexample + 統一恆等式）：(P1)-(P6) 結構性質列表配合候選 unifying identity (cycle space Arf invariant)，但等價於 4CT 本身（circular）
• 路線 4（Thomassen potential method）：list 餘量（5-list 之 +1 margin）對 4-coloring 缺失，強化命題之歸納封閉性與弱邊界條件矛盾

結構性原因：「結構性質」與「代數正性」之間之 reduction 必須引入 nontrivial 中間層（如 Grötzsch、Tutte duality），而這正是主鏈的策略——將困難集中於中間層。

典型代表：

• 路線 5（Entropy compression / LLL）：LLL 條件 $ep(\Delta+1) \leq 1$ 對 4-coloring 要求 $\Delta < 1.47$，遠小於 planar triangulation 之實際 $\Delta$
• 路線 13（Glauber dynamics）：chain stationary distribution 存在 ⟺ 4-coloring 存在（chain-based proof 必為 algorithmic 構造或 tautology）

結構性原因：LLL/dynamics framework 之 power 集中於 sparse high-domain CSP（$k \gg \Delta$），而 4CT 屬 dense low-domain regime，本質非此 framework 之適用區。

路線 9 sub-agent 構造之 Schnyder labeling + Alon-Tarsi argument 看似證明 4-choosability for 3-連通 plane triangulation，但 Voigt 1993 / Mirzakhani 1996 反例顯示此命題為假。

真正 bug 在 Step 3：「$D_{\text{int}} = T_1 \cup T_2 \cup T_3$ 為 acyclic」的假設為假。

• 每個個別 tree $T_i$ acyclic ✓（Schnyder 1989）
• 任兩個 trees 之 union $T_i \cup T_j$ acyclic ✓（Kozik & Podkanowicz 2023）
• 三 trees 之 union $T_1 \cup T_2 \cup T_3$ 含 directed cycles ❌

事實上，3-連通 plane triangulation 之 internal 3-orientations 形成 distributive lattice under cycle-reversal moves（Brehm 2000；Felsner ELJC v11i1r15）——non-acyclicity 為通則，acyclic 為例外。

對未來路線設計之強化原則：若一個 argument 之構造涉及 $k \geq 3$ 個 trees / structures 之 union，默認假設 union 為 acyclic 之前須嚴格驗證——pairwise acyclicity 不 imply $k$-way acyclicity。

任何證明 4CT 的新路徑必須避開以下 9 個陷阱（家族 C「局部 vs 全域」之失敗已涵蓋於 M4「dynamics inadequacy」中，故 9 重排除以 M4 形式列出，不另列 family C）：

1. 不為 quadratic positivity（避 M1）
2. 不為純拓撲下界對偶（避 M2）
3. 不在 4 之 deformation critical point（避 M3 / M6）
4. 不為 dynamics-style local update（避 M4）
5. 不為 polynomial categorification 之 generic-point evaluation（避 M5）
6. 不為純結構性質清單（避家族 B）
7. 不為純 reformulation（避家族 A）
8. 不為 cellular sheaf on plane embedding（避 M7）
9. 不為 higher-tensor framework with face-condition obstruction in $H^k$ for $k \geq 3$（避 M8）

M7（embedding-dependence vs. abstract-graph-invariance）：

$P(G; q)$ 為 abstract graph 不變量（不依 plane embedding）；任何 cellular sheaf / stratified construction on $S^2$ 必為 embedding-dependent。對 $K_4$ 之顯式計算（Round 5 Direction B）：

• 預期 $\chi(\mathcal{F}_4^{K_4}) = P(K_4; 4) = 24$
• 顯式計算：$\chi = 16 - 72 + 96 = 40 \neq 24$
• $\chi$ 之公式為 $qV - q(q-1)E + \sum_f |C_{n_f}|$，依 face vector $\{n_f\}$；但 $P(G; q)$ 不依 face vector

結論：plane-specific cellular categorification 為錯誤路徑——若要使用 plane embedding，必須透過 quotient / moduli 將 embedding-dependent data 規約至 abstract-invariant level。

M8（Hyperpfaffian 之 Dimensional Trivialization）：

• Kasteleyn (Pfaffian, $k=2$): face condition obstruction 在 $H^2(S^2; \mathbb{Z}_2)$；plane $g=0$ 給 trivial、$g \geq 1$ 給 $\mathbb{Z}_2^{2g}$ obstruction——genuinely plane-specific
• Hyperpfaffian (4-tensor, $k=4$): face condition obstruction 在 $H^4(S^2)$；對所有 surface trivially 為零（因 $\dim S^2 = 2 < 4$）——不 distinguish plane vs. non-plane

結論：高階 tensor framework 無法 inherit Kasteleyn 之 plane-specificity。Pfaffian ($k=2$) 為 plane-specific algebra 之 unique sweet spot。

若 Meta-Theorem 為 rigorous theorem，則「結構性證明 of 4CT」fundamentally 不存在於現有代數-拓撲-組合工具集——任何 candidate 必落入家族 A/B/C 或 M1-M8 中至少一者。

Grötzsch reduction（本研究主鏈）雖為 (S2)+(S3) 合格，但其 Grötzsch input 本身不嚴格 (S1)——故「嚴格 (S1) 結構性證明」之存在性 itself 為 open problem。

嚴格化方向：將上述 informal statement 化為 information-theoretic 下界——「任何 4CT 之 (S1)-合格證明必含至少 $\Omega(?)$ bits 之 case-specific 資訊」。此為 attack-spec F1 第二項「結構性下界」之 open problem，本研究未能給出嚴格證明，留待後續研究。

Abstract：A systematic obstacle taxonomy from 17 attempted routes. We systematically analyze why structural proofs of the four-color theorem are difficult, organizing failure modes into three families (A: reformulation tautology, B: structure-algebra gap, C: local-global tension) and 8 informal meta-principles M1-M8. The taxonomy connects 17 attempted routes through standard mathematical frameworks (Penrose tensor, Hodge theory, sheaf cohomology, hyperpfaffian, etc.) to a coherent picture of what makes 4CT structurally hard.

Status：Ready for arXiv preprint submission.

Abstract：An expository note on the three-way tree union obstruction. We identify the precise step at which the naive Schnyder labelings + Alon-Tarsi method fails to give $\mathrm{AT}(\text{planar}) \leq 4$. The bug is at Step 2: the assumption that $D_{\text{int}} = T_1 \cup T_2 \cup T_3$ is acyclic is provably false (Brehm 2000 distributive lattice). This explains both why Kozik–Podkanowicz 2023 must double the red tree (giving bound 5, not 4) and why the underlying conjecture is impossible (Voigt 1993 / Mirzakhani 1996).

Honest scope：This is an expository note. No new mathematical result is claimed. The contribution is structural exposition: stating the naive argument cleanly, locating the precise step where it fails, and connecting the failure to both Kozik's bound 5 and the Voigt–Mirzakhani impossibility.

Abstract：The four-color theorem as a conditional reduction to Grötzsch's theorem via Tutte's flow-coloring duality. We present an explicit chain reducing 4CT to Grötzsch 1959 via Tutte 1954 cycle-cocycle duality + S₃-action on the three nonzero elements of $\mathbb{Z}_2 \times \mathbb{Z}_2$. The reduction is folklore (implicit in Tutte's planar 3-flow conjecture), but our explicit chain with $S_3$-action arguments for 2-cut and 3-cut splitting is to our knowledge the cleanest published treatment.

Critical disclaimer：This paper explicitly acknowledges that the reduction is folklore. Contributions are: (a) explicit chain with $S_3$-action arguments; (b) (S1)/(S2)/(S3) sliding scale audit framework; (c) clean exposition; (d) honest audit (Thomassen 2003 has 7-8 unavoidable configurations, exceeding strict (S1)).

• Hadwiger conjecture for $k=5$：「無 $K_5$ minor 之 graph 為 4-colorable」。Wagner 1937 證明此等價於 4CT，故不繞道。Hadwiger for $k \geq 6$ 已由 RSST 等利用 4CT 推出。
• Tutte-Beraha conjecture：planar triangulation 之 chromatic polynomial 在 $Q \in [4, \infty)$ 嚴格正。在 $Q = 4$ 即 4CT；在 $Q > 4$ 由 Birkhoff-Lewis 1946。本研究主鏈不訴諸 Tutte-Beraha，故無循環。
• Tait conjecture：Tait 1880 conjecture「3-connected cubic planar 含 Hamiltonian cycle」已由 Tutte 1946 反駁（不等價於 4CT 之 Tait 形式）。