n个顶点 度数为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)
即必有度数相同的顶点
若存在d(xi)=n 则不可能存在d(xi)=0
n个d(xi)取n-1个不同的值
由鸽笼原理
必有d(xm)=d(xn)
即必有度数相同的顶点