怎樣證明在N個(gè)頂點(diǎn)的簡(jiǎn)單無向圖中至少有兩個(gè)頂點(diǎn)的度數(shù)相同？D（V1）D（V2）≤| G1 | G2 |-2≤n-2，這與條件相反，因此G只能是連通圖。在圖論中，連通圖是基于連通性的概念。在無向圖G中，

怎樣證明在N個(gè)頂點(diǎn)的簡(jiǎn)單無向圖中至少有兩個(gè)頂點(diǎn)的度數(shù)相同？

D（V1）D（V2）≤| G1 | G2 |-2≤n-2，這與條件相反，因此G只能是連通圖。在圖論中，連通圖是基于連通性的概念。在無向圖G中，如果有一條從頂點(diǎn)i到頂點(diǎn)J的路是連通的（當(dāng)然，必須有一條從J到i的路），那么i和J就是連通的。如果G是有向圖，那么連接I和j的路徑上的所有邊都必須在同一方向上。如果圖中的任意兩點(diǎn)是連通的，則稱為連通圖。如果此圖是有向圖，則稱為強(qiáng)連通圖。如果任意兩個(gè)頂點(diǎn)可以連通，則無向圖稱為連通圖。擴(kuò)展數(shù)據(jù)：如果一個(gè)無向圖G=（V，e）是連通的，則邊的數(shù)目大于或等于頂點(diǎn)的數(shù)目減去1：| e |>=| V |-1，反之亦然。如果G=（V，e）是一個(gè)有向圖，那么當(dāng)邊的數(shù)目大于或等于頂點(diǎn)的數(shù)目時(shí)，它是強(qiáng)連通的：| e |>=| V |，反之亦然。無環(huán)無向圖連通的充要條件是它是樹，等價(jià)于：| e |=| V |-1。