作业帮 > 数学 > 作业

证明:G图中v为偶次顶点,dG(v)

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/06/01 08:29:00
证明:G图中v为偶次顶点,dG(v)
ω(G-v)≤dG(v)/2
此题应该是每个顶点的度为偶数.
1)v不是割点,则显然成立
2)若v是割点,则设ω(G-v)=n,取其中一个分支G1,点v与G1连的边数只能是偶数,即在G1中连 的边数至少是2,同理对其余的分支也成立,所以分支数最多是
dG(v)/2
所以命题成立.