三頂點圖的全部clique與independent sets

目標與範圍

完整2³子集分類求omega與alpha。

只對完整小圖給exact extrema。

已知條件與符號

• work

• G1 — V={0,1,2}，E={01}，2孤立。

• V,E — 完整頂點與邊集合
• ω,α — clique與independence numbers

規則與來源

• mko_definition · cited — 候選集合逐對核相鄰或不相鄰。單一大小r候選只給omega或alpha的下界；宣稱maximum須遍歷全部頂點子集合或另有全域上界。maximal只代表不能加入頂點，且clique大小只推出chi(G)>=omega(G)。 · mko-clique-and-independent-set
• work · prerequisite — 有限無向簡單圖的邊為無loop、無重複unordered pairs；圖性質須對完整明示V、E逐一檢查。 clique的所有不同點對皆相鄰，independent set的所有不同點對皆不相鄰；ω、α為各自最大基數，maximal指不能再加入頂點。

逐步主鏈

|V|=3

|\mathcal P(V)|=8

\varnothing

\text{both clique and independent, size }0

\{0\},\{1\},\{2\}

\text{all both clique and independent, size }1

\{0,1\}

01\in E\implies\text{clique, not independent}

\{0,2\},\{1,2\}

02,12\notin E\implies\text{independent, not clique}

\{0,1,2\}

02\notin E\implies\text{not clique};\quad01\in E\implies\text{not independent}

\text{all eight subsets classified}

\omega(G)=2,\quad\alpha(G)=2

\{2\}\text{ clique, no vertex addable}

\{2\}\text{ maximal but not maximum since }1<2

局部子步與引理

本稿無局部子步。

逐步反向審查

• S08 · premise_audit · G1, S07, work — clique一般只給chi≥omega，不給chi=omega定理。
• S07 · premise_audit · G1, S06, work — 所有maximum clique為{0,1}；maximum independent為{0,2}、{1,2}。
• S06 · premise_audit · G1, S05, work — 兩種否證使用不同pair，不能混淆。
• S05 · premise_audit · G1, S04, work — 兩pair都逐一核，而非抽樣。
• S04 · premise_audit · G1, S03, work — 一條已存在邊足以否定該pair independent。
• S03 · premise_audit · G1, S02, work — singleton2是maximal clique但未必maximum。
• S02 · premise_audit · G1, S01, work — empty set依此convention保留。
• S01 · premise_audit · G1, work — clique核所有pair相鄰，independent核所有pair不相鄰。

錯誤控制與反例

pair責任

clique缺一pair就失敗；independent多一edge就失敗。

完整極值

1空+3singleton+3pair+1triple=8。

• {2} maximal所以maximum。 → reject — {0,1}是更大clique。
• {0,1,2} independent。 → reject — 它包含原邊01。
• 由omega=2一般推出chi=2。 → reject — 五圈omega2但奇圈不能二色，需三色。

結論與限制

omega=alpha=2；{2}示範maximal不等maximum。

驗證及來源綁定

2 個本稿宣告算術檢查；只支持所列算式。

• source commit: b1b2f1dcf8c50d67a93fe52d95f8eef7b3abba9f
• adopted source SHA-256: ab2452783bc37c6ebfe68daeeaecab2d6cb9f42304f01f7d929a83e3d7698922
• original source SHA-256: b12b9f7e4aa7773c8a1042f9d5b03d1d5d69b4be8c23c84776ee6696a0aeb755
• Lean: NOT_RUN · independent AI: SCOPED_LEAD_AND_BILINGUAL_CONTEXT_REVIEW

同源完整 JSON（含公式、AST、反控制與修訂記錄）