Caminos que pasan por cada arista una sola vez. Existen si hay 0 o 2 vértices impares.
Un camino de Euler (que también puedes llamar rastro euleriano) en un grafo es un recorrido que pasa por cada arista del grafo exactamente una vez. Un circuito de Euler (o tour euleriano) es un camino de Euler que empieza y termina en el mismo vértice. Este concepto nació del famoso problema de los Siete Puentes de Königsberg, que Leonhard Euler resolvió en 1736 y que es el primer teorema de la teoría de grafos. El problema central pregunta: ¿bajo qué condiciones puedes dibujar una figura sin levantar el lápiz del papel y sin pasar dos veces por la misma línea?
La intuición detrás de los caminos de Euler depende mucho de la paridad de los vértices. Imagina que estás recorriendo un grafo. Cada vez que entras a un vértice por una arista, tienes que salir de él por una arista diferente para continuar el camino, a menos que ese vértice sea el inicio o el final de tu recorrido. Por lo tanto, cada vértice intermedio que visites debe tener un grado par (el mismo número de entradas que de salidas). Si los puntos de inicio y fin son distintos, ellos tienen que ser los "raros" con grado impar. Si el inicio y el fin son el mismo (un circuito), entonces absolutamente todos los vértices deben tener grado par.
En las matemáticas de competencia, como el AIME o la USAMO, los caminos de Euler son herramientas fundamentales para problemas de paridad, recorridos