证明 简单图的最大度数小于节点数(离散数学)

Xingliu213423 1年前 已收到1个回答 举报

davines 幼苗

共回答了16个问题采纳率:87.5% 举报

这个很简单~
设简单图G的最大度数为n,设顶点u的度数=n,只要证G中至少含有n+1个顶点.
u有n条边,每条边都有一个异于u的顶点,所以除u外,G中至少还有n个点.
则G中至少有n+1个顶点,证毕!

1年前

4
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 16 q. 0.024 s. - webmaster@yulucn.com