Condiciones para caminos y circuitos eulerianos.
Un camino de Euler (o rastro euleriano) en un grafo es un recorrido que pasa por cada arista del grafo exactamente una vez. Si ese camino empieza y termina en el mismo vértice, le decimos circuito de Euler (o ciclo euleriano). El estudio de estos caminos marca el nacimiento de la teoría de grafos; todo empezó con la solución de Leonhard Euler en 1736 al problema de los Siete Puentes de Königsberg. Euler demostró que era imposible cruzar los siete puentes exactamente una vez y regresar al punto de partida, y con eso estableció un vínculo directo entre la topología de un grafo y los grados de sus vértices.
Para que exista un camino de Euler, tienes que fijarte en dos propiedades fundamentales: la conectividad y la paridad de los vértices. Piénsalo así: cada vez que entras a un vértice por una arista, tienes que salir de ahí por una arista distinta. Por eso, cada vértice intermedio en el camino debe tener un grado par (el mismo número de "entradas" y "salidas"). Las únicas excepciones son los puntos donde empiezas y donde terminas. Si empiezas y terminas en lugares diferentes, deben tener grados impares (una "salida" sin su "entrada" correspondiente para el inicio, y viceversa para el final). Si empiezas y terminas en el mismo lugar (un circuito), entonces cada vértice debe tener un grado par.
En las olimpiadas