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

推荐答案 2014-11-10

小狸为您解答～
在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阶以上简单图，恒有两点度数相同！

温馨提示：答案为网友推荐，仅供参考

当前网址：http://22.wendadaohang.com/zd/0IC62T6X6.html

相似回答

证明:在两个或两个以上结点的简单图中,至少有两个结点的度数相同。答：证明：设G是具有n个结点的简单图(n≥2)∵每个结点仅能与另外的n-1个结点邻接 ∴每个结点的度数≤n-1 ∴ 在G中结点可能出现的度数为：0, 1, …, n-1 ∵度数是0的结点是孤立点，度数是n-1的结点是邻接其它n-1个结点的 ∴它们不可能同时出现在G中 ∴在G中可出现的度数应分成以下两种...

至少有两个结点的简单图有两个相同度数的结点.答：【答案】：设G是一个具有n个结点的简单图(n≥2)．因为每个结点仅仅能够与另外的n-1个结点邻接，所以，每个结点的度数≤n-1．因此，在G中结点可能出现的度数是0，1，2，…，n-1．由于度数为0的结点是孤立结点，而度数为n-1的结点是邻接其他n-1个结点的，所以，在G中度数为0和度数为n-1的...

大家正在搜

在具有6个节点的无向简单图中证明简单图的最大度小于节点数五个节点三条边的不同构的简单图含5个节点3条边的简单图有几个设简单图所有节点的度之和为12 设g是具有n个节点的简单无向图二叉树中每个节点有两个子节点 n个节点的简单图简单图G有n个节点