Fleury算法的证明（续） (2)(证明含所有边)假设P没有包括G中所有的边，令Gm中所 有非零度顶点集合为S(非空)，令S=Vc-S,则vm∈S。 考察序列e1,e2…c,e+1,em。假设j是满足y,∈S,而V1∈S”的最大下标。 如果没有这样的j,G就不连通，矛盾。因为Pm的终点在S中，因此e+1 一定是G,中的割边。 令e是在G中与v,相关联的异于e+1的边（非零度点一定有），根据算法选择 e1(割边)的原则，e也一定是割边。但是，Gm中任意顶点的度数必是偶 数，e在Gm中的连通分支是欧拉图，e在Gm的某个 欧拉回路中，不可能是G的割边。矛盾。 Fleury算法的证明(续) (2) (证明含所有边)假设Pm没有包括G中所有的边，令Gm中所 有非零度顶点集合为S（非空）, 令S' =VG -S, 则vmS' 。 考察序列e1 ,e2 ,…ej ,ej+1 ,…,em。假设j是满足vjS, 而vj+1S’的最大下标。 如果没有这样的j，G就不连通，矛盾。因为Pm的终点在S’中，因此ej+1 一定是Gj中的割边。 令e是在Gj中与vj相关联的异于ej+1的边(非零度点一定有), 根据算法选择 ej+1 (割边)的原则，e也一定是割边。但是，Gm中任意顶点的度数必是偶 数，e在Gm中的连通分支是欧拉图，e在Gm的某个 欧拉回路中，不可能是Gj的割边。矛盾。 vm S’ S vj+1 vj ej+1 v e