西安电子科技大学$6.4.1欧拉图软件学院家【引理】在一个结点度数均为偶数的连通无向图G=<V，E>中，必存在一条简单回路证明：(构造法）任取结点v1EV，因为v1度数为偶数,o—○所以必存在边与v1关联。取与v1关联的一条边el，令el=(vl,v2)。若v2=v1，则e1是v1结点上的一条自回路，它就是一条简单回路。否则，v2≠v1。因为v2的度数亦为偶数，所以必存在另外一条边e2≠el，并且e2与v2关联，令e2=(v2,v3)。若v3=v2或v3=v1，则找到一条简单回路。否则，v3≠v2且v3v1，因为v3的度数亦为偶数，所以必存在另外一条边e3与v3关联，并且满足e3≠e2且e3≠el。如此下去，由于G中的结点是有限的，因此必存在一条简单回路。西安电子科技大学 §6.4.1 欧拉图 软件学院 【引理】在一个结点度数均为偶数的连通无向图 G=<V, E>中，必存在一条简单回路。 证明：（构造法） 任取结点v1∈V，因为v1度数为偶数， 所以必存在边与v1关联。 取与v1关联的一条边e1，令e1=(v1 ,v2)。 若v2=v1，则e1是v1结点上的一条自回路，它就是一条简单回 路。否则，v2≠v1。因为v2的度数亦为偶数，所以必存在另外一条 边e2≠e1，并且e2与v2关联，令e2=( v2 ,v3)。 若v3=v2 或v3=v1，则找到一条简单回路。否则，v3≠v2 且 v3≠v1，因为v3的度数亦为偶数，所以必存在另外一条边e3与v3关 联，并且满足e3≠e2且e3≠e1。 . . 如此下去，由于G中的结点是有限的，因此必存在一条简单回路