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

數(shù)學(xué)人氣：222 ℃時間：2020-03-14 22:57:12

優(yōu)質(zhì)解答

n個頂點(diǎn) 度數(shù)為d(xi)(1≤i≤n)
則d(xi)可以取0,1,2...,n-1
可以取n個不同的值
若存在d(xi)=0 則不可能存在d(xi)=n
n個d(xi)取n-1個不同的值
由鴿籠原理
必有d(xm)=d(xn)
即必有度數(shù)相同的頂點(diǎn)
若存在d(xi)=n 則不可能存在d(xi)=0
n個d(xi)取n-1個不同的值
由鴿籠原理
必有d(xm)=d(xn)
即必有度數(shù)相同的頂點(diǎn)