题目

证明 若图中只有两个奇数度顶点 则两顶点必连通
怎样证明·~

提问时间：2021-03-18

答案

对于一笔画问题,有两个判断的准则,它们都由欧拉提出并证明[1].
定理一
有限图 G 是链或圈的充要条件是：G为连通图,且其中奇顶点的数目等于0或者2.有限连通图 G 是圈当且仅当它没有奇顶点.
证明：
* 必要性：如果一个图能一笔画成,那么对每一个顶点,要么路径中“进入”这个点的边数等于“离开”这个点的边数：这时点的度为偶数.要么两者相差一：这时这个点必然是起点或终点之一.注意到有起点就必然有终点,因此奇顶点的数目要么是0,要么是2.
* 充分性：
1.如果图中没有奇顶点,那么随便选一个点出发,连一个圈 C1.如果这个圈就是原图,那么结束.如果不是,那么由于原图是连通的,C1 和原图的其它部分必然有公共顶点 s1.从这一点出发,在原图的剩余部分中重复上述步骤.由于原图是有限图,经过若干步后,全图被分为一些圈.由于两个相连的圈就是一个圈,原来的图也就是一个圈了.
2.如果图中有两个奇顶点 u 和 v,那么加多一条边将它们连上后得到一个无奇顶点的有限连通图.由上知这个图是一个圈,因此去掉新加的边后成为一条链,起点和终点是 u 和 v.
定理二
如果有限连通图 G 有 2k 个奇顶点,那么它可以用 k 笔画成,并且至少要用 k 笔画成.
证明：将这 2k 个奇顶点分成 k 对后分别连起,则得到一个无奇顶点的有限连通图.由上知这个图是一个圈,因此去掉新加的边后至多成为 k 条链,因此必然可以用 k 笔画成.但是假设全图可以分为 q 条链,则由定理一知,每条链中只有两个奇顶点,于是 2q ge 2k.因此必定要 k 笔画成.