圖著色

數學敘述

完整核全部邊；非相鄰頂點可同色。一個proper coloring只給chromatic number上界；最優性需另有lower-bound證書，greedy不自動最優。

代表公式（精確 TeX）

C(G)

成立條件

• 完整有限無向簡單圖與每頂點color表。
• 顏色label重命名不改實質partition。

符號作用域

• C — proper頂點著色
• G — 有限圖

直觀、定義與常見誤解

每條邊兩端異色。

使用色數不超過k。

上界不等於chromatic optimum。

要求所有頂點異色，或把greedy色數當最小色數。

已採用的推導導讀

原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。

前置知識

• 有限簡單無向圖 — 完整邊集合。
• 函數映射 — coloring為V到colors總映射。
• 自然數 — k作顏色數上界。

驗證界線

只核指定coloring與上界；不宣稱最優除非有lower bound。

not_formalized

這不表示內容錯誤；只表示尚未登錄可重播的計算或形式證據。

下一個義務

加入chromatic number與clique lower bound。

同源結構化資料

本頁與互動版共用同一個物件與既有語言 edition；未新增證明或人工審定。