证明：任给 e∈E(G)，都有 ω(G)≤ω(G-e)≤ω(G)+1。用 G-v 代替 G-e ，上式未必成立

wilsony

谁能证明？

luyuanhong

题 ω(G) 表示将图 G 分成连通片的个数。

（1）证明：任给 e∈E(G)，都有 ω(G)≤ω(G-e)≤ω(G)+1 。

（2）用 G-v 代替 G-e ，上式未必成立。

证（1）G-e 是从 G 中除去一条边 e 后得到的图。

    从图 G 中除去一条边 e 后，只会发生下列两种情况：

    e 连接的两边的图形，原来是连通的，除去 e 后仍然是连通的。图中的连通片个数

保持不变，即有 ω(G)=ω(G-e) 。

    e 连接的两边的图形，原来是连通的，除去 e 后变成不连通了。这样图中的连通片

个数就会比原来增加 1 个，有 ω(G-e)=ω(G)+1 。

    因为只有上面这两种情况，所以 ω(G)≤ω(G-e)≤ω(G)+1 。

（2）G-v 是从 G 中除去一个顶点 v 后得到的图。

    从图 G 中除去一个顶点 v 后，可以发生多种情况，例如：

    设顶点 v 的度数是 3 ，从 v 伸出 3 条边连接图中 3 个部分。除去 v 后，原来连通成

1 片的这 3 个部分，变成了不连通的 3 片。这样图中的连通片个数就会比原来增加 2 个，

有 ω(G-v)=ω(G)+2 。

    在这种情况下，ω(G-v)≤ω(G)+1 显然是不成立的。

wilsony

谢谢陆老师。