Exactamente 0 o 2 vértices de grado impar.
Un camino de Euler (también conocido como rastro de Euler) en un grafo es un recorrido que pasa por cada arista del grafo exactamente una vez. A diferencia de un camino simple, un camino de Euler te permite visitar los vértices varias veces. Si el camino empieza y termina en el mismo vértice, le decimos circuito de Euler (o tour de Euler). El estudio de estos caminos empezó con el problema de los Siete Puentes de Königsberg, lo que llevó a Leonhard Euler a darse cuenta de que la existencia de tal recorrido depende totalmente de los grados de los vértices (el número de aristas conectadas a un vértice) y de la conectividad del grafo.
La intuición principal se basa en el concepto de "paridad". Imagina que recorres un grafo. Cada vez que entras a un vértice por una arista, tienes que salir de él por una arista diferente para seguir el camino, a menos que ese vértice sea el inicio o el final de tu viaje. Por lo tanto, para cualquier vértice que esté estrictamente "en medio" del camino, las aristas que llegan a él deben venir en parejas (una de entrada y una de salida). Así que cada vértice intermedio debe tener un grado par.
Esta lógica te lleva a las condiciones fundamentales de existencia. Para que exista un camino de Euler, el grafo debe estar conectado (ignorando los vértices aislados) y el número de vértices con grado impar debe estar muy restringido. Específicamente, debe