假設(shè)G不是連通的
則G至少有兩個連通分支G1和G2,有 |G1|+|G2| ≤ |G| = n
任取G1中一點v1,G2中一點v2
則d(v1)≤|G1|-1,d(v2)≤|G2|-1
d(v1)+d(v2) ≤ |G1|+|G2|-2 ≤ n-2,與條件矛盾
證明：若n階簡單無向圖G的任意兩個結(jié)點的度數(shù)之和大于等于n-1,則G是連通的.
證明：若n階簡單無向圖G的任意兩個結(jié)點的度數(shù)之和大于等于n-1,則G是連通的.
我也搜到“假設(shè)G有兩個連通分支G1和G2,那么取v1是G1中度數(shù)最小的頂點,v2是G2中度數(shù)最小的頂點,則d(v1)+d(v2)≤n-2（等號在G1和G2都是完全圖時取到）,這與條件矛盾.” 我希望有一個正規(guī)的步驟……我確實不懂這個……
我也搜到“假設(shè)G有兩個連通分支G1和G2,那么取v1是G1中度數(shù)最小的頂點,v2是G2中度數(shù)最小的頂點,則d(v1)+d(v2)≤n-2（等號在G1和G2都是完全圖時取到）,這與條件矛盾.” 我希望有一個正規(guī)的步驟……我確實不懂這個……
數(shù)學(xué)人氣：201 ℃時間：2020-04-05 16:53:37
優(yōu)質(zhì)解答
我來回答
類似推薦
- 1．證明在具有n個頂點的簡單無向圖G中,至少有兩個頂點的度數(shù)相同.
- G是n階簡單無向圖,如果圖G中任意兩點的度數(shù)之和大于等于n-1,證明圖G是連通圖
- 如何證明小于30條邊的平面簡單圖有一個結(jié)點的度數(shù)小于等于4
- 離散證明:一個圖包含2n個結(jié)點,每個結(jié)點的度數(shù)大于等于n的簡單圖是連通的
- 設(shè)G是有n個結(jié)點n條邊的簡單連通圖,且G中存在度數(shù)為3的結(jié)點,證明G中至少有一個度數(shù)為1的結(jié)點
- 草字頭+佳 是什么字
- empty what is full,fill what is empty! 永遠(yuǎn)不讓自己空虛,永遠(yuǎn)不讓自己自滿 給點點評
- 16S rRNA基因通用引物1492r/F27,1492和27分別是什么意思?編號么?
- 用短除法分解素因素:42 81 40
- 在長1.6米,寬1.2米的長方形三合板上,裁出半徑是20厘米的圓,最多可裁多少個?
- 線性代數(shù) 設(shè)A,B,C均為n階矩陣,I為n階單位矩陣,且ABC=I,則下列矩陣乘積一定等于I的是哪個?
- 試以下面的方程為例,敘述用分離變量法求解方程的步驟.
猜你喜歡
- 1每天堅持朗讀對學(xué)外語有什么好處?
- 2You are yuji?急.
- 3思密達(dá)到底是什么意思
- 4計算(a的立方-b的立方)+ab(a-3b)-2(b的立方-a的平方b)
- 5求寫英語書面表達(dá)
- 6油酸的作用是什么
- 7請幫忙翻譯：Payment and and Charging
- 8近紅外區(qū)的吸收光譜代表什么含義?
- 9大正方形邊長為15cm,小正方形邊長為10cm.求陰影甲的面積比陰影乙的面積大多少平
- 10有甲乙丙三種文具,若購甲2件,乙1件、丙3件共需23元,若夠甲1件、乙4件、丙5件共需36元,問夠甲一件,乙2件,丙3件共需多少元
- 11Jack has a dog and so have I.____dog and____had a fight
- 12英語翻譯