證明：N個(gè)頂點(diǎn)的簡單圖最少有2個(gè)頂點(diǎn)度數(shù)一樣

數(shù)學(xué)人氣：561 ℃時(shí)間：2020-03-17 21:08:35

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

對(duì)點(diǎn)數(shù)n歸納 n=2成立設(shè)n=k成立n=k+1時(shí) 1）若有一點(diǎn)度數(shù)為0,去掉這點(diǎn),則剩下k個(gè)點(diǎn)必有2個(gè)度數(shù)相同的頂點(diǎn) 2）若每點(diǎn)度數(shù)至少為1,而所有點(diǎn)對(duì)數(shù)都至多為k,k+1個(gè)點(diǎn),度數(shù)都是1至k的整數(shù),由抽屜原理得必定至少有2個(gè)度數(shù)相...