最小邊覆蓋

最小邊覆蓋是對於給定圖，具有最小可能邊數的邊覆蓋。圖的最小邊覆蓋的大小被稱為圖的邊覆蓋數，記為。

每個最小邊覆蓋都是一個極小邊覆蓋（即，不是任何其他邊覆蓋的真子集），但反之不一定成立。

只有沒有孤立點的圖才具有邊覆蓋（以及因此的最小邊覆蓋）。

圖的最小邊覆蓋可以使用Wolfram 語言計算，使用FindEdgeCover[g]。目前沒有 Wolfram 語言 函式來計算圖的所有最小邊覆蓋。

如果圖沒有孤立點，則

其中 是匹配數， 是的頂點數（Gallai 1959，West 2000）。