> 英语 >
图论的
Show that a simple graph with at least two vertices there must be two vertices that have the same degree
人气:214 ℃ 时间:2020-04-15 21:21:26
解答
设G是一个n个顶点的简单图,若G含孤立顶点,则它的最大度不超过n-2,由鸽笼原理,一定存在两个点的度数相同;若G不含孤立顶点,则它的最小度大于等于1,最大度小于等于n-1,由鸽笼原理,也一定存在两个点的度数相同.
推荐
猜你喜欢
© 2024 79432.Com All Rights Reserved.
电脑版|手机版