设 G 是连通图，已知 V(G)≥2 且 E(G)＜V(G) ，证明 G 中至少有两个度数为 1 的顶点

wilsony

谁能证明？

luyuanhong

题  设 G 是连通图，已知 V(G)≥2 且 E(G)＜V(G) ，证明 G 中至少有两个度数为 1 的顶点。

证  因为 G 是连通图，已知 V(G)≥2 ，所以可以从有一条边连接的两个点开始，每次在已有

点上连接一条边，逐步生成整个图。

    最初时，只有一条边、两个点，所以 E(G)=1 ，V(G)=2 ，E(G)=V(G)-1＜V(G) 。

    这时的两个点都是度数为 1 的点，即 G 中有两个度数为 1 的顶点。

    以后每次添加一条边，有下列几种情况：

    一种情况，是添加的一条边的另一个端点与已有的点重合，这时边数增加 1 ，点数不增加，

这样原来 E(G)=V(G)-1＜V(G) 就会变成 E(G)=V(G) ，与已知 E(G)＜V(G) 矛盾，所以这种

情况不可能。

    另一种情况，是添加的一条边的另一个端点不与已有的点重合，这时边数和点数都增加 1 ，

保持 E(G)=V(G)-1＜V(G) 。

    这种情况又可以细分成两种情形：

    一种情形，是在原来一个度数为 1 的顶点上添加一条边，这个度数为 1 的顶点变成度数 2 ，

但是添加一条边的另一个端点的度数是 1 ，所以 G 中仍然至少有两个度数为 1 的顶点。

    另一种情形，是在原来一个度数大于 1 的顶点上添加一条边，原来度数为 1 的顶点没有减少，

而添加一条边的另一个端点的度数是 1 ，G 中又增加了一个度数为 1 的顶点。

   总之，不管哪一种情形，G 中总是至少有两个度数为 1 的顶点。

wilsony

   多谢陆老师！