Condiciones a saber si un grafo es un circuito euler.
1) Un grafo no dirigido G tiene un paseo de Euler si y solo si tiene cero o dos vértices de valencia impar.
2) Si un grafo no dirigido G tiene un circuito de Euler entonces todo vértice de G tiene valencia par, además de ser conexo.
3) Si G es un grafo no dirigido con vértices {v1, v2, ..., vn} y la suma (v1), (v2), ..., (vn) es par, entonces el grafo tiene un circuito de Euler.
4) Un grafo G tiene un camino de Euler de v w si y solo si v y w son los únicos vértices de valencia impar.
EJEMPLOS:
(a) No lo admite porque v4 es un vértice aislado.
(b) No lo admite porque cualquier ciclo utilizará la arista e1 dos veces.
(c) El circuito v1 e1 v2 e2 v1 es euleriano.
(d) El circuito v3 e3 v1 e1 v2 e2 v3 es euleriano.
(e) No admite ningún circuito euleriano.
(f) v1 e1 v2 e2 v3 e3 v4 e4 v2 e5 v5 e6 v1 es un circuito euleriano.
Ejercicio:
Demostrar si existe un circuito euler o no en el siguiente grafo.
siguiendo los siguientes puntos se veran que el rafo si contiene un circuito euler.
Camino euler: a,b,d,e,b,c,e,f,c,a
Referencias: