证明 简单图的最大度数小于节点数(离散数学)
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:数学作业 时间:2024/07/27 12:51:08
证明 简单图的最大度数小于节点数(离散数学)
![证明 简单图的最大度数小于节点数(离散数学)](/uploads/image/z/6622049-65-9.jpg?t=%E8%AF%81%E6%98%8E+%E7%AE%80%E5%8D%95%E5%9B%BE%E7%9A%84%E6%9C%80%E5%A4%A7%E5%BA%A6%E6%95%B0%E5%B0%8F%E4%BA%8E%E8%8A%82%E7%82%B9%E6%95%B0%28%E7%A6%BB%E6%95%A3%E6%95%B0%E5%AD%A6%29)
这个很简单~
设简单图G的最大度数为n,设顶点u的度数=n,只要证G中至少含有n+1个顶点.
u有n条边,每条边都有一个异于u的顶点,所以除u外,G中至少还有n个点.
则G中至少有n+1个顶点,证毕!
设简单图G的最大度数为n,设顶点u的度数=n,只要证G中至少含有n+1个顶点.
u有n条边,每条边都有一个异于u的顶点,所以除u外,G中至少还有n个点.
则G中至少有n+1个顶点,证毕!