Circuito de Euler y circuitos de Hamilton.

Sea G un grafo sin vértices aislados. Un circuito que tiene todas las aristas de G recibe el nombre de Circuito de Euler. Un circuito euleriano es una trayectoria que empieza y termina en el mismo vertice y recorre cada arista exactamente una vez.

Teorema.

Si G es un grafo contiene un circuito euteriano si y sólo si:

• G es un conexo.
• Cada vértice de G es de grado par.

Entonces si G (un grafo) tiene un grado de vértice de grado 1 no puede tener circuitos (x - x  no se repite arista). Tampoco tiene grado impar porque no se puede salir y entrar en n par de veces 

Trayectoria de Euler.

 Debe comenzar en un vertice de grado impar y termina en otro.

Teorema de Euler.

a) Si una gráfica tiene más de dos vértices de grado impar, entonces no puede tener una trayectoria d Euler.

b)  Si una gráfica conexa tiene exactamente dos vértices de grado par, entonces tiene por lo menos una trayectoria de Euler. Cualquier circuito de Euler debe iniciar en uno de los vértices y terminar en el otro.

Grado de un vértice.

a) El grado de un vértice  es el número de aristas que se encuentran en ese mismo vértice.

b)Un circuito es una trayectoria que inicia y termina en el mismo vértice.

c) Una gráfica es conexa si cualquiera de sus vértices se pueden unir por una trayectoria. Si una gráfica no es conexa se le denominará como disconexa, a los pedazos de unas gráficas se les llamará componentes.