森林 G 有 2k 个度数为奇数的顶点，证明 G 中所有的边，分别在 k 条无公共边的轨道上

wilsony

谁能证明？

wilsony

  陆老师愿做下这道题吗?

luyuanhong

题  森林 G 有 2k 个度数为奇数的顶点，证明 G 中所有的边，分别在 k 条无公共边的轨道上。

证  从一个度数为奇数的顶点出发，沿一条边向前，凡是遇到度数为偶数的顶点，就穿过这点，

继续向前，直到遇见一个度数为奇数的顶点，才终止前进。

    将从出发到终止，路上经过的各条边连成的一条轨道，从图中去掉，因为轨道的首尾都是

度数为奇数的顶点，去掉这条轨道后，图中度数为奇数的顶点少了 2 个，变成 2(k-1) 个。

    重复以上的操作，每去掉一条轨道，图中度数为奇数的顶点就会减少 2 个。

    操作到最后，得到 k 条被去除的轨道，图 G 中度数为奇数的顶点数变成了 0 。

    这时，图 G 中只剩下度数为偶数的顶点。

    下面，用反证法证明：这时图 G 中不可能有度数为大于等于 2 偶数的顶点。

    假设有度数为大于等于 2 偶数的顶点，从这点出发，凡是遇到其他度数为偶数的顶点，就

穿过，继续前进，这样一直下去，因为图中其他度数为偶数的顶点是有限的，所以最后必然会返

回到出发点，这样，就会得到一个圈。

    但是，因为 G 是森林，图中不可能有圈，这就产生了矛盾，假设不成立。

    可见，这时图 G 中不可能有度数为大于等于 2 偶数的顶点，只有度数为 0 的孤立点。

    也就是说，除去前面得到的 k 条轨道后，图中已经没有其他的边了，G 中所有的边，都分别

在 k 条无公共边的轨道上。

wilsony

谢谢陆老师！