例1下面图中谁是欧拉图？谁是非欧拉图但存在欧拉 迹？谁是非欧拉图且不存在欧拉迹？ G G: 解：G是欧拉图；G,是非欧拉图，但存在欧拉迹；G 中不存在欧拉迹。 例2证明：若G和H是欧拉图，则G×H是欧拉图
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 8 例1 下面图中谁是欧拉图？谁是非欧拉图但存在欧拉 迹？谁是非欧拉图且不存在欧拉迹？ G1 G2 G3 解：G1是欧拉图；G2是非欧拉图，但存在欧拉迹；G3 中不存在欧拉迹。 例2 证明：若G和H是欧拉图，则 是欧拉图。 G H
证明：首先证明：对任意m∈V(G),v∈V田，有： d(u)+d()=d(u,v)》 事实上，设z是u的任意一个邻点，一定有(u,v)的一个 邻点(z,v),反之亦然。同理，对于v的任意一个邻点w, 一定有(u,v)的一个邻点(u,w),反之亦然。即：(u,)在乘 积图中邻点个数等于u在G中邻点个数与v在H中邻点个 数之和。 所以，G,H是欧拉图，那么G×H顶点度数为偶数 其次证明： GxH 是连通的 (4,y),(42,y2)∈V(G×H) 由于G,H都是欧拉图，所以都连通。 设最短的u1-u2路
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9 证明：首先证明：对任意u ∈V(G), v ∈V(H),有： du dv d uv ( ) ( ) (( , )) 事实上，设z是u的任意一个邻点，一定有(u, v)的一个 邻点(z, v),反之亦然。同理，对于v的任意一个邻点w， 一定有(u, v)的一个邻点(u, w), 反之亦然。即: (u, v)在乘 积图中邻点个数等于u在G中邻点个数与v在H中邻点个 数之和。 所以，G ,H是欧拉图，那么 顶点度数为偶数。 G H 其次证明： 是连通的。 G H 11 2 2 ( , ),( , ) ( ) u v u v VG H 由于G, H都是欧拉图，所以都连通。设最短的u1--u2路