Question

1．证明在具有n个顶点的简单无向图G中,至少有两个顶点的度数相同.

Answer 1

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)

即必有度数相同的顶点