求证:任意有限图的所有顶点度数之和为偶数
证明:任意有限图的所有顶点度数之和为偶数
这是图论里非常基础且经典的结论,咱们顺着思路一步步把证明理清楚:
初始状态分析
先从空图开始——也就是只有顶点、没有任何边的状态。这时候所有顶点的度数都是0,整个图的度数总和为0,0是偶数,符合我们要证明的奇偶性前提。逐条添加边的过程分析
我们逐个往图里添加边,不管添加哪种类型的边,都只会让度数总和增加偶数:- 若添加的是连接两个不同顶点的边:这条边会让这两个顶点的度数各+1,总和总共增加2(1+1)。偶数加偶数还是偶数,所以总和的奇偶性保持不变,依然是偶数。
- 若允许添加自环(连接单个顶点的边):根据图论的度数定义,自环会让该顶点的度数+2(自环在度数计算中算2度),总和同样增加2,奇偶性还是保持偶数不变。
不管我们给这个有限图添加多少条边,每一步操作都不会改变度数总和的奇偶性。初始总和是偶数,所以最终任意有限图的顶点度数之和必然是偶数。
内容的提问来源于stack exchange,提问作者user532588




