则S≠φ。取S中边数最少的一个,记为G′。因(G’)≥2,故G”含有圈,因而含有闭迹。 设C是G′中一条最长的闭迹。由假设,C不是G′的 Euler闭迹。因此G"\E(C)必有一个 连通分支至少含有一条边。记这个连通分支为G0。由于C是闭迹,故G中没有奇度顶点, 且E(G0)<E(G)。由G′的选择可知,G必有 Euler闭迹Co。由于G′连通,故C必经过Go 中至少一个顶点,从而(C)∩F(C0)≠φ。因此C+C0是G’的一条闭迹,且 E(C+C0)>E(C),这与C的选取矛盾。证毕 充分性的另一种证法(数学归纳法) 无妨设v(G)>1。因G连通且无奇度顶点,故δ(G)≥2,因而必含有圈。 当v(G)=2时,设仅有的两点为uv,则u间必有偶数条边,它们显然构成 Euler回 路 假设v(G)=k时,结论成立。 当v(G)=k+1时,任取v∈V(G)。令S={ν的所有关联边}。记S中的边为 e1,e2,…en,其中m=d(v)为偶数。记G′=G\。对G作如下操作: (1)任取e12e,∈S,设e1=v",e (2)G′=G+vy,S=SVe,e (3)若S=φ,则令G′=G-ν,停止:否则转(1)继续。 这个过程最终得到的G’有k个顶点,且每个顶点在G′中的度与在G中完全一样。由归 纳假设,G中有 Euler闭迹,设为P。将P中上述添加边vv都用对应的两条边e,e,代替 显然获得G的一条 Euler闭迹。证毕。 定理412一个连通图有 Euler迹当且仅当它最多有两个奇度顶点 证明必要性:设连通图G有 Euler迹T,其起点和终点分别为l,va 若∈E(G),则G有 Euler闭迹,由定理4..1,G无奇度顶点。 若lgG,则G+有 Euler闭迹。由定理41.1,图G+l无奇度顶点。故G最多 只可能有两个奇度顶点 充分性:若G无奇度顶点,则由定理41.1,G有 Euler闭迹,自然有 Euler迹。 若G只有两个奇度顶点,设其为u,则给G添加一条新边e=u所得的图G+e的每 个顶点都是偶度顶点。从而G+e有 Euler闭迹。故G有 Euler迹。证毕。 个图G如果有一条欧拉迹或欧拉闭迹,则我们可以沿着欧拉迹或欧拉闭迹连续而不 重复地把G的边画完。因此存在欧拉迹或欧拉闭迹的图通常称为可一笔画的图,或者说它 可一笔画成。如果图G可分解为两条迹或闭迹的并,则G的边可用两笔不重复地画完。同 样地,如果图G可分解为k条迹或闭迹的并,则G可k笔画成。2 则 S ≠ φ 。取 S 中边数最少的一个，记为G′。因δ (G′) ≥ 2 ，故G′含有圈，因而含有闭迹。 设 C 是G′中一条最长的闭迹。由假设，C 不是G′的 Euler 闭迹。因此G′ \ E(C) 必有一个 连通分支至少含有一条边。记这个连通分支为G0 。由于 C 是闭迹，故G0 中没有奇度顶点， 且 ( ) ( ) ε G0 < ε G′ 。由G′的选择可知，G0 必有 Euler 闭迹C0 。由于G′连通，故 C 必经过G0 中至少一个顶点，从而 V (C) ∩V (C0 ) ≠ φ 。因此 C + C0 是 G′ 的一条闭迹，且 ( ) ( ) ε C + C0 > ε C ，这与 C 的选取矛盾。证毕。 充分性的另一种证法（数学归纳法）： 无妨设ν (G) > 1。因 G 连通且无奇度顶点，故δ (G) ≥ 2 ，因而必含有圈。 当ν (G) = 2 时，设仅有的两点为 u,v，则 u,v 间必有偶数条边，它们显然构成 Euler 回 路。 假设ν (G) = k 时，结论成立。 当ν (G) = k +1 时，任取 v ∈V (G) 。令 S = {v 的所有关联边}。记 S 中的边为 m e , e ,"e 1 2 ，其中m = d(v) 为偶数。记G′ = G \ v 。对G′作如下操作： （1） 任取ei , e j ∈ S ，设e v v i = i ，e v v j = j ； （2） i j G′ := G′ + v v ， : \ { , } i j S = S e e ； （3） 若 S = φ ，则令G′ := G′ − v ，停止；否则转（1）继续。 这个过程最终得到的G′有 k 个顶点，且每个顶点在G′中的度与在 G 中完全一样。由归 纳假设，G′中有 Euler 闭迹，设为 P。将 P 中上述添加边 i j v v 都用对应的两条边 i j e , e 代替， 显然获得 G 的一条 Euler 闭迹。证毕。 定理 4.1.2 一个连通图有 Euler 迹当且仅当它最多有两个奇度顶点。 证明 必要性：设连通图 G 有 Euler 迹 T，其起点和终点分别为 u, v。 若uv ∈ E(G) ，则 G 有 Euler 闭迹，由定理 4.1.1，G 无奇度顶点。 若uv ∉G ，则G + uv 有 Euler 闭迹。由定理 4.1.1，图G + uv 无奇度顶点。故 G 最多 只可能有两个奇度顶点。 充分性：若 G 无奇度顶点，则由定理 4.1.1，G 有 Euler 闭迹，自然有 Euler 迹。 若 G 只有两个奇度顶点，设其为 u,v，则给 G 添加一条新边e = uv 所得的图 G +e 的每 个顶点都是偶度顶点。从而 G +e 有 Euler 闭迹。故 G 有 Euler 迹。证毕。 一个图 G 如果有一条欧拉迹或欧拉闭迹，则我们可以沿着欧拉迹或欧拉闭迹连续而不 重复地把 G 的边画完。因此存在欧拉迹或欧拉闭迹的图通常称为可一笔画的图，或者说它 可一笔画成。如果图 G 可分解为两条迹或闭迹的并，则 G 的边可用两笔不重复地画完。同 样地，如果图 G 可分解为 k 条迹或闭迹的并，则 G 可 k 笔画成