作业帮 > 综合 > 作业

无向图G中恰有两个奇度定点,证明两个奇度定点必然联通

来源:学生作业帮 编辑:作业帮 分类:综合作业 时间:2024/05/14 08:33:27
无向图G中恰有两个奇度定点,证明两个奇度定点必然联通
首先,不管无向图有几条边,一条边总连着2个顶点,所以:
无向图所有顶点度数之和为偶数!
也得到,无向图的任一联通部分也是无向图且适用上述结论.
现有奇度顶点A,在它所在的联通部分,必存在另一点B是奇度顶点,使得该联通部分满足一开始我说的那个结论.
因为G中恰有2个奇度顶点,所以A所在联通部分就是无向图G!因为A、B联通,所以命题得证!