證明圖G =（V，E）至少有| v | - | E |部件

Question

證明圖表G=(V,E)具有至少|v|-|E|部件

我需要回答用於與例如和完整說明以上問題。

Answer 1

帶有| V |頂點和沒有邊具有| V |組件。添加一個邊可以減少至多一個組件的數量（如果邊上的頂點先前沒有被另一條路徑連接;否則，組件的數量不會減少）。因此加入| E |後組件數量最少邊是| V | - | E |並且沒有| V |的圖頂點和| E |邊緣可以具有比這更少的組件。

Answer 2

要求：每個組件Ci與Vi具有至少|Vi|-1邊緣的頂點。
證明：連接僅包含Vi的子圖，並且最小連通圖是具有|Vi|-1邊的樹。如果Ci的邊緣小於Vi-1 - 它將不會被連接，這與我們如何定義Ci的方式相矛盾。

表示Ei組件Ci中的邊數。
請注意，sum{|Ei| for each Ci} = E，因爲沒有邊緣連接組件Ci和組件Cj（否則它們將自己連接）。 現在，讓我們來總結所有邊緣的所有Ci，我們會得到

|E| =(1) sum { |Ei| } >=(2) sum{|Vi|-1} =(3) |V| - sum{1 | for each Ci} 
            =(4) |V| - #components 
-> 
|E| >= |V| - #components 
#components >= |V| - |E| 

QED

說明在上述證明等式：

（1）相加來了由於沒有交叉成分的邊緣（如上所述），因此每個成分中的所有邊合計爲|E|
（2）來自我們證明的要求
（3）總結| Vi |所有Ci結果|V|
（4）總結1在組件