Question

联通图中的奇点数必定是偶数,这是为什么?

Answer 1

从一个点出发算“出”,到达一个点算“进”.

对偶点而言,必定每次都是：先“进”后“出”或先“出”后“进”.

所以,当一个偶点为出发点时,必然也是结束点.

对奇点而言,必定有一次是：有“出”无“进”或有“进”无“出”；

所以,当有奇点存在时,奇点必然是出发点或结束点.

可得：

当一个偶点为出发点时,不能有奇点存在；

当有奇点存在时,奇点个数只能是两个,一个点为出发点,另一个为结束点.

所以,联通图中的奇点数必定单是偶数,而且只能是0或2.