Question

证明：在两个或两个以上结点的简单图中，至少有两个结点的度数相同。

证明：在两个或两个以上结点的简单图中，至少有两个结点的度数相同。

Answer 1

小狸为您解答～
在n阶简单图中，点的度数在必然在0～n-1之间，共n个不同的度数。

假设: 没有两个点度数相同，即:0～n-1这n个度数必然对应n个点。

证明:
1.若最小度为0，则说明有一个点为孤立点，此时在剩下n-1个点中，最大的度数只能为n-1-1=n-2，0～n-2只对应n-1个点，故，与假设矛盾。
2.若最小度为1，则最大度为n-1，1～n-1只对应n-1个点，故，与假设矛盾。
综上，假设不成立，即2阶以上简单图，恒有两点度数相同！