证明：N个顶点的简单图最少有2个顶点度数一样
发布网友
发布时间：2022-04-22 02:56
共2个回答
热心网友
时间：2023-10-05 11:53
证明：设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中必有两个顶点的度数相同。
相关信息：
若定义域和值域都为有限集，其研究研究的主要理论依据为鸽洞原理（对一个非一对一函数充分性的判别）。
可列集(enumerable)：与自然数集等势的集合，即可以与自然数集进行一一映射的集合（如自然数集、 有理数集、 代数数集等，但不包含实数集、复数集、直线点集、 平面点集等）。
热心网友
时间：2023-10-05 11:53
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)
即必有度数相同的顶点
