离散数学问题：1．证明在具有n个顶点的简单无向图G中，至少有两个顶点的度数相同.

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)
即必有度数相同的顶点