问答题
证明：无向简单图中一定存在度数相同的两个结点．
【正确答案】
因为在n个结点的简单图的度序列(d
1
，d
2
，…，d
n
)中，d
1
≤d
2
≤…≤d
n
≤n-1，若d
1
，d
2
，…，d
n
中没有两个相等，则(d
1
，d
2
，…，d
n
)=(0，1，2，…，n-1)．删去G中的孤立结点v
0
(deg(v
0
)=0)，余下的子图G'有n-1个结点且存在度为n-1的结点，故G'不是简单图．这与前提矛盾，故d
1
，d
2
，…，d
n
中至少存在两个相等的度数，即存在两个等度结点．
【答案解析】
提交答案
关闭