欧拉图的判别(无向图) 定理:无向图G是欧拉图,当且仅当G是连通图,且G中没有奇度顶点 证明:(续) (充分性) 由G为非平凡的连通图可知,G中边数m≥1。对m作归纳 (1)m=1时,由G的连通性和无奇度顶点可知,G只能是一个环,因 此,G为欧拉图 (2)设m≤k(k≥1)时,结论成立,要证明m=K+1时,结论也成立 由G的连通性和无奇度顶点可知:8(G)≥2。又由扩大路径法可以 证明G中存在长度大于或等于3的圈 设C为G中一个圈,删除C上的全部边,得G的生成子图G’。设G有 s个连通分支G'1,G'2,…,G,每个连通分支至多有k条边,且无奇度顶 点,并且设G与c的公共顶点为v(=1s) 55 欧拉图的判别(无向图) (充分性.) 由G为非平凡的连通图可知, G中边数m ≥ 1。对m作归纳。 (1) m = 1时, 由G的连通性和无奇度顶点可知, G只能是一个环, 因 此, G为欧拉图。 (2) 设m ≤ k(k ≥ 1)时, 结论成立．要证明m = K+1时, 结论也成立。 由G的连通性和无奇度顶点可知: δ(G) ≥ 2。又由扩大路径法可以 证明G中存在长度大于或等于3的圈。 设C为G中一个圈, 删除C上的全部边, 得G的生成子图G’。设G’有 s个连通分支G’1, G’2, …, G’s, 每个连通分支至多有k条边, 且无奇度顶 点, 并且设G’i与C的公共顶点为vji*(i = 1..s)。 定理: 无向图G是欧拉图, 当且仅当G是连通图, 且G中没有奇度顶点. 证明: (续)