頂點覆蓋

數學敘述

graph須明示有限unique vertices與loop-free、duplicate-free unordered edges。cover audit遍歷全部edges；一條兩端皆不在C的edge即為反例。empty-edge graph的empty set是cover；isolated vertices不必加入；任何cover的superset仍為cover。inclusion-minimal表示刪任何一點都不再cover，minimum表示全體covers中cardinality最小，兩者不可混同。本節點不混用edge cover、independent set或directed cover，也不自動求minimum size。

代表公式（精確 TeX）

V(G,C)=1

成立條件

• edges canonical成排序unordered pairs；candidate subset unique且屬vertex set。
• minimum boundary只在小型完整finite graph exhaustive枚舉全部subsets。

符號作用域

• V — 頂點覆蓋述詞
• G — 有限簡單圖
• C — 候選頂點子集

直觀、定義與常見誤解

全部edges逐一核至少一端被選。

uncovered edge是完整反例witness。

empty/isolated/superset與minimal/minimum boundaries分開。

只覆蓋大多數edges，或把inclusion-minimal當minimum。

已採用的推導導讀

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

前置知識

• 有限簡單無向圖 — finite simple graph。
• 子集合 — candidate vertex subset。
• 量詞與明示論域 — all-edge責任。

驗證界線

本輪只判定vertex covers與小型boundary；minimum vertex cover留待後續節點。

not_formalized

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

下一個義務

加入最小頂點覆蓋。

同源結構化資料

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