图论问题求助：求证满足特定划分条件的图G存在奇度顶点

嘿，你选反证法的思路完全正确！咱们一步步把这个证明补完整：

前置知识：握手定理 #

首先回忆握手定理：任意图中，所有顶点的度数之和等于边数的2倍，因此这个和一定是偶数。

反证法推导 #

1. 假设前提：假设图G中所有顶点都是偶度顶点（即每个顶点的度数都是偶数）。根据握手定理，G中所有顶点的度数之和必为偶数。

2. 拆分顶点集的度数和
   把顶点集分成A、B两部分，分别计算两部分顶点的度数总和：

   • 对于子集A中的顶点：它们的度数由两部分组成：
     • A内部边贡献的度数：设这部分总度数为$S_A$。因为每条内部边连接A中两个顶点，会给总度数贡献2，所以$S_A$是偶数。
     • 连接到B的边贡献的度数：题目中只有唯一一条边$e$连接A中的$v$和B中的$w$，所以这部分总度数是1。
     • 因此，A中所有顶点的度数总和为 $S_A + 1$。
   • 同理，子集B中所有顶点的度数总和为 $S_B + 1$，其中$S_B$是B内部边的总度数，同样是偶数。

3. 导出矛盾
   根据假设，A中每个顶点都是偶度，所以A的度数总和应该是偶数（偶数相加还是偶数）。但$S_A + 1$是偶数+奇数=奇数，这就和假设矛盾了！
   （同样看B部分，$S_B +1$也是奇数，和B中顶点度数和应为偶数的假设矛盾）

结论 #

既然假设“所有顶点都是偶度”会导出矛盾，那么原命题成立：图G一定存在奇度顶点。

内容的提问来源于stack exchange，提问作者LioH