Question

证明：在n阶无向简单图中，至少有两个顶点，其度数相同(n≥2)。

Answer 1

【答案】：[证明]设G是n阶无向简单图，图G中各个顶点的度数最多为n-1，因此图G中各个顶点的度数只可能是0，1，2，…，n-1。但当图G中有一个顶点的度数为n-1时，表明这个顶点与图G中的其他n-1个顶点都有边关联，因此图中其他n-1个顶点的度数至少为1。在这种情况下，图G中各点的度数只可能是1，2，…，n-1，共有n-1种，而图G仅有n个顶点，所以由鸽洞原理可知．图G中必有两个顶点的度数是相同的。
当图G中没有一个顶点的度数为n-1时，则图中各顶点的度数只可能是0，1，…，n-2，共有n-1种，同样由鸽洞原理可知，图G中必有两个顶点的度数相同。