# 三頂點圖的全部clique與independent sets [← 導讀目錄](https://ocme.evemisslab.com/zh-Hant/derivations/) · [原始 MKO](https://ocme.evemisslab.com/zh-Hant/mko/mko-clique-and-independent-set/) 這是使用者已採用的自然語言教學導讀。有限／算術檢查不等於普遍證明；本輪未跑 Lean，各稿審查範圍見其修訂記錄。來源原有的狀態標籤保留為歷史資料。公式保留精確 TeX，不另造語意 AST。 derivation-mko-clique-and-independent-set-01 · ocme-new142-reader-adoption-20261021 ## 目標與範圍 完整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指不能再加入頂點。 ## 逐步主鏈 S01 · implies操作前 |V|=3 操作後 |\mathcal P(V)|=8 條件：無 規則：work · 依賴：G1, work 葉節點依據：work 完整子集數為八。 S02 · implies操作前 \varnothing 操作後 \text{both clique and independent, size }0 條件：無 規則：work · 依賴：G1, S01, work 葉節點依據：work 無頂點對，兩個全稱條件皆空真。 S03 · implies操作前 \{0\},\{1\},\{2\} 操作後 \text{all both clique and independent, size }1 條件：無 規則：work · 依賴：G1, S02, work 葉節點依據：work 三個singleton都無不同頂點pair。 S04 · implies操作前 \{0,1\} 操作後 01\in E\implies\text{clique, not independent} 條件：無 規則：work · 依賴：G1, S03, work 葉節點依據：work 這一pair提供大小二clique。 S05 · implies操作前 \{0,2\},\{1,2\} 操作後 02,12\notin E\implies\text{independent, not clique} 條件：無 規則：work · 依賴：G1, S04, work 葉節點依據：work 另外兩pair提供大小二independent sets。 S06 · implies操作前 \{0,1,2\} 操作後 02\notin E\implies\text{not clique};\quad01\in E\implies\text{not independent} 條件：無 規則：work · 依賴：G1, S05, work 葉節點依據：work 三點集用一個缺邊與一個有邊分別否證兩性質。 S07 · implies操作前 \text{all eight subsets classified} 操作後 \omega(G)=2,\quad\alpha(G)=2 條件：無 規則：work · 依賴：G1, S06, work 葉節點依據：work 無合法三點集且有合法二點見證，得兩exact extrema。 S08 · implies操作前 \{2\}\text{ clique, no vertex addable} 操作後 \{2\}\text{ maximal but not maximum since }1<2 條件：無 規則：work · 依賴：G1, S07, work 葉節點依據：work 孤立點singleton不能擴張成clique，但被大小二clique超過。 ## 局部子步與引理 本稿無局部子步。 ## 逐步反向審查 - 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、反控制與修訂記錄）](https://ocme.evemisslab.com/data/derivations/coverage-20261021/guides/derivation-mko-clique-and-independent-set-01.json)