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

来源:学生作业帮助网 编辑:作业帮 时间:2024/11/30 12:25:23
证明 简单图的最大度数小于节点数(离散数学)
xj@EEwC1[~@J%BUiӦ 1FP4B&?3o2 t@![޹l>{ \ʊ[! Ct'va(#s؅jP MGܣD

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

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