设 G 是连通图，且每个顶点的度数都是偶数，证明：ω(G-v)≤deg(v)／2

wilsony

谁能证明？

luyuanhong

题 设 G 是连通图，且每个顶点的度数都是偶数，证明：ω(G-v)≤deg(v)／2 。

证 因为每个顶点的度数都是偶数，设顶点 v 的度数 deg(v)=2k 。有 deg(v)／2=k 。

   从图 G 中除去顶点 v ，得到图 G-v 。

   因为 v 的度数为 2k ，所以除去 v 后，与它连接的 2k 个顶点的度数都减少了 1 。

这 2k 个顶点，原来的度数是偶数，都变成了奇数。G-v 中有 2k 个度数为奇数的顶点。

   从一个度数为奇数的顶点出发，沿一条边前进，如果遇到度数为偶数的顶点，就穿过，

继续前进，最后必定会遇到一个度数为奇数的顶点，一路经过的各条边，连成了一条轨道，

这条轨道的两个端点，度数都是奇数。将这条轨道、以及与它联通的联通片全部去掉。这一

次操作完成后，G-v 中至少去掉了 2 个度数为奇数的顶点。在 G-v 中，最多只剩下 2(k-1)

个度数为奇数的顶点。

    重复以上的操作，每一次操作，都会去掉一条两端为奇数顶点的轨道、以及与这条轨道联通

的一个联通片，至少使图中减少了 2 个度数为奇数的顶点。

    这样最多操作 k 次，去掉 k 个联通片，就可以使得图中度数为奇数的顶点个数变成 0 。

    因为 G 原来是联通的，去掉顶点 v 后，G-v 中出现 2k 个度数为奇数的顶点，G-v 中各部分

都与这 2k 个度数为奇数的顶点联通。所以，再除去以这 2k 个奇数顶点为端点的 k 条轨道、以及

与这 k 条轨道联通的 k 个联通片后，G-v 中就没有其他的图形了。

   由此可见，G-v 中的联通片，最多只有 k 个，也就是说，必有 ω(G-v)≤k=deg(v)／2 。

wilsony

陆老师，为什么“ 从一个度数为奇数的顶点出发，沿一条边前进，如果遇到度数为偶数的顶点，就穿过，

继续前进，最后必定会遇到一个度数为奇数的顶点“？

luyuanhong

wilsony 发表于 2025-8-31 11:10
陆老师，为什么“ 从一个度数为奇数的顶点出发，沿一条边前进，如果遇到度数为偶数的顶点，就穿过，继续前进，最后必定会遇到一个度数为奇数的顶点“？

在前进路上，遇到一个度数为偶数的顶点，我们必定可以从一条边进，从另一条边出。

以后我们只要保持不走原路，就用掉了这个顶点的两个度数，这个顶点的度数减少了 2 ，

成为一个较小的偶数。下一次如果再遇到这个顶点，我们又可以从一条边进，从另一条边

出，又会用掉这个顶点的两个度数。

由于图中度数为偶数的顶点，只有有限多个，每个顶点的度数也是有限的，我们不断穿越

度数为偶数的顶点，每次都要用掉两个度数，显然，我们不可能永远走下去，所以，最后

必定会遇到一个度数为奇数的顶点。

wilsony

多谢陆老师！