G是n階簡單無向圖,如果圖G中任意兩點的度數(shù)之和大于等于n-1,證明圖G是連通圖
G是n階簡單無向圖,如果圖G中任意兩點的度數(shù)之和大于等于n-1,證明圖G是連通圖
數(shù)學(xué)人氣：703 ℃時間：2020-04-09 08:46:42
優(yōu)質(zhì)解答
假設(shè)G有兩個連通分支G1和G2,那么取v1是G1中度數(shù)最小的頂點,v2是G2中度數(shù)最小的頂點,則d(v1)+d(v2)≤n-2（等號在G1和G2都是完全圖時取到）,這與條件矛盾.
我來回答
類似推薦
- 證明：若n階簡單無向圖G的任意兩個結(jié)點的度數(shù)之和大于等于n-1,則G是連通的.
- 1．證明在具有n個頂點的簡單無向圖G中,至少有兩個頂點的度數(shù)相同.
- 圖論證明,圖G帶v個頂點,e條邊的連通平面圖簡單圖,其中v大于等于3且圈的長度為L.
- 求離散數(shù)學(xué)一個圖的證明 證明:一個連通且每個頂點的度數(shù)都為偶數(shù)的圖一定沒有割邊
- 如何證明小于30條邊的平面簡單圖有一個結(jié)點的度數(shù)小于等于4
- 大氣層是怎樣分層的?有多少層?每層密度怎樣?
- z=x^3y-3x^2y^3的二階偏導(dǎo)數(shù)
- ①已知a²+a-3=0 那么a²（a+4）的值是___
- 莎士比亞十四行詩哪些比較著名?
- 因為1/2×4/3×3/2=1,所以1/2、4/3、3/2三個數(shù)互為倒數(shù).
- 2011年4月1日泰國發(fā)生洪災(zāi),季風(fēng)來自太平洋還是印度洋?
- 1.25:x=2.5:8怎么解
猜你喜歡
- 1（25加4分之3）除以4分之1加4分之1,脫式計算
- 2Can A Chinese Young Lady Become An American Woman?
- 31.宇航員身穿沉重的宇航服,還能行走自如,可能是因為：
- 4描寫春夏秋冬好詞好句
- 5英語翻譯
- 6簡要廉頗和藺相如的故事 200字左右 好的話另加分
- 7伊紅美藍培養(yǎng)基是什么培養(yǎng)基
- 8德語怎么說 我覺得 我認為 相當(dāng)于英語的I think
- 9（一減二分之一）（三分之一減一）（一減四分之一）（五分之一減一）……（2009分之1減1）（,一減2010分之一）
- 10扣取百分之20的手續(xù)費,你必須獲利50元,該定什么價格.
- 11a為和值時適合條件x+y=2a+1和x-y=3a-2的點(x,y)在二象限(第二象限上的點(x,y)滿足x＜0 y＞0)
- 12證明：兩條邊上的高相等的三角形是等腰三角形．