设无向简单图G有9个结点。证明：G中至少存在两个度数相同的结点。

设无向简单图G有9个结点。证明：G中至少存在两个度数相同的结点。
【正确答案】：证明：用反证法。假设图G中任意两点的度数均不相同。 因为图G是无向简单图，故其结点度数均小于等于8. 因此，可能的度数列为0，1，2，3，4，5，6，7，8.事实上，上述序列不可能是一个图的度数列。因为若存在一个8度的结点，则在无向简单图中，该结点必须与其他8个结点均邻接，也就意味着其他结点中不可能存在0度的结点。矛盾
【题目解析】： 既无平行边也无环的无向图图称为无向简单图。设无向图G 的顶点集，则称为图G的度数列。