Grado de vértice

El grado de un vértice se puede definir como la cantidad de aristas que parten desde o hacia un mismo vértice

Rutas y Circuitos de Euler

Ruta de Euler: Una ruta o camino de Euler es una trayectoria que contiene todas las aristas del grafo y recorre una arista exactamente una vez

Condiciones:

El Grafo debe de ser conexo

Exactamente 2 vértices son de grado impar, todos los demás deben de ser de grado par

Se comienza en uno de los vértices de grado impar y se termina en el otro vértice impar

Circuito de Euler

Un circuito de Euler es un Camino de Euler con la diferencia que empieza y termina en el mismo vértice es decir es un camino cerrado que recorre cada arista exactamente una vez

Condiciones:

El grafo es conexo

Todos los vértices son de grado par

Se comienza y se termina en el mismo vertice

Ciclos y Caminos Hamiltonianos

Un camino hamiltoniano, en el campo matemático de la teoría de grafos, es un camino de un grafo, una sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez. Si además el último vértice visitado es adyacente al primero, el camino es un ciclo hamiltoniano.

Coloración de Grafos

En Teoría de grafos, la coloración de grafos es un caso especial de etiquetado de grafos; es una asignación de etiquetas llamadas colores a elementos del grafo. De manera simple, una coloración de los vértices de un grafo tal que ningún vértice adyacente comparta el mismo color es llamado vértice coloración.

Ejemplo: