En la imagen, ${\displaystyle C=\{1,2,3,4,6,3,5,4,1\}\,}$  es un ciclo euleriano, luego es un grafo euleriano.

Un grafo es una representación, un modelo, compuesto por un número determinado de vértices (nodos) y un número de arcos (aristas) que los relacionan, cada arista o arco tiene la capacidad de relacionar dos nodos. La palabra ciclo se emplea en teoría de grafos para indicar un camino cerrado en un grafo, es decir, en que el nodo de inicio y el nodo final son el mismo, como contrapartida un camino hamiltoniano es un camino que recorre todos los vértices de un grafo sin pasar dos veces por el mismo vértice. Si el camino es cerrado se dice un ciclo hamiltoniano.

Si un grafo admite un ciclo euleriano, se denomina grafo euleriano.

Se elige para iniciar el trazo cualquier punto impar y se terminará en el otro punto o vértice impar.

El origen de la teoría de los ciclos eulerianos fue planteado y resuelto por el propio Leonhard Euler en 1736 en un problema que tiene el nombre de Siete puentes de la ciudad de Königsberg (Prusia oriental en el siglo XVIII y actualmente, Kaliningrado, provincia rusa) dando origen a la Teoría de los grafos.

El problema se enuncia de la siguiente forma: Dos islas en el río Pregel, en Königsberg se unen entre ellas y con la tierra firme mediante siete puentes. ¿Es posible dar un paseo empezando por una cualquiera de las cuatro partes de tierra firme, cruzando cada puente una sola vez y volviendo al punto de partida?

Euler enfocó el problema representando cada parte de tierra por un punto y cada puente, por una línea, uniendo los puntos que se corresponden. Entonces, el problema anterior se puede trasladar a la siguiente pregunta: ¿se puede recorrer el dibujo sin repetir las líneas?

Euler demostró que no era posible puesto que el número de líneas que inciden en cada punto no es par (condición necesaria para entrar y salir de cada punto, y para regresar al punto de partida, por caminos distintos en todo momento).

Dado un grafo conexo (no existen nodos aislados) y no dirigido ${\displaystyle G=(V,E\,)}$ , si ${\displaystyle G\,}$  tiene exactamente dos vértices de grado impar, entonces ${\displaystyle G\,}$  tiene un camino euleriano no cerrado. En caso de que todos los vértices tengan grado par, ${\displaystyle G\,}$  tiene un ciclo euleriano.

Dado ${\displaystyle G(V,E\,)}$  no orientado y conexo; si tiene ${\displaystyle 2k\,}$  nodos de grado impar, entonces ${\displaystyle G\,}$  puede ser escrito como unión de ${\displaystyle k\,}$  caminos (simples) distintos sobre los arcos. Las siguientes expresiones son equivalentes:

1) ${\displaystyle G\,}$  es euleriano;

2) ${\displaystyle \forall v\in \ V}$  con grado ${\displaystyle (v)\geq 2}$  y par.

3) ${\displaystyle G=\coprod _{i=1}^{n}C_{i}}$  todos disjuntos (caminos distintos) en los arcos,

es decir ${\displaystyle C_{i}^{E}\cap \;C_{j}^{E}=\emptyset \;}$  con ${\displaystyle C\prod _{v\in V}(\deg ^{+}(v)-1)!}$ 

o equivalentemente

${\displaystyle C\prod _{v\in V}(\deg ^{-}(v)-1)!}$ 

siendo C cualquier cofactor de la matriz laplaciana de G.

• Problema de los puentes de Königsberg
• Ciclo hamiltoniano
• Problema del cartero chino
• Glosario en teoría de grafos

• "Solutio problematis ad geometriam situs pertinentis", Euler, L.,Comment. Academiae Sci. I. Petropolitanae 8 (1736), 128-140.
• "Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechnung zu umfahren", Hierholzer, C. Mathematische Annalen 6 (1873), 30-32.
• Récréations Mathématiques IV, Lucas, E., Paris, 1921.
• "Deux problemes de geometrie de situation", Fleury, Journal de mathematiques elementaires (1883), 257-261.
• "Discrete Mathematics with Applications", Susanna Epp, Fourth Edition
• "Discreta Mathematics and its application"", Rosen 7.ª edición
• https://en.wikipedia.org/wiki/Eulerian_path