对图的新认识

对图的新认识

对于任意的一个图，图中所有点的度数之和为边数*2，在图中每走一次，有三种情况

1.奇点数没变（一种是真没变，一种原奇点减少一个，又新添了一个奇点）

2.奇点数增加2

3.奇点数减少2

连通图中奇点个数一定为偶数，证明如下：

我们来模拟建图的过程

1.一开始所有点都是0，显然偶数

2.加在两个偶点上，奇点数加2

3.加在一奇一偶上，没变，还是偶数

4.加在两个奇点上，奇点数减2，偶数

综上，在建图过程中都保持奇点的个数为偶数，最终也是偶数。