頂點覆蓋數

頂點覆蓋數是圖 中最小頂點覆蓋的大小，被稱為圖 的頂點覆蓋數，記為 。

柯尼希-埃格瓦里定理指出，對於二分圖，匹配數（即最大獨立邊集的大小）和頂點覆蓋數相等。

圖 的獨立數 和頂點覆蓋數透過下式關聯：

其中 是頂點計數 (West 2000)。