Por un grafico orientado, un camino (o circuito) euleriano pasa una y sólo una vez por todos los arcos. Análogamente, en el caso no dirigido, una cadena o ciclo euleriano pasa una y sólo una vez por todas las aristas.
El gráfico debe ser fuertemente conexo (o conexo). De hecho, si el gráfico no lo está, no se puede acceder a uno o más subgráficos que contengan enlaces. Observamos que un ciclo o circuito euleriano contiene tantos enlaces que llegan a un vértice como que salen (llegamos a un vértice para salir)
Condiciones necesarias y suficientes del circuito / ciclo euleriano. El gráfico está conectado (o fuertemente conectado). Cualquiera que sea el vértice del gráfico, su grado es par (su grado de salida es igual a su grado de entrada).
Como todos los vértices tienen un grado par, sabemos que hay un circuito. Un camino es una unión de circuitos disjuntos en los bordes. Si eliminamos los bordes de un camino, los grados siempre son iguales. Supongamos que no hay un camino que dé un ciclo euleriano. Si eliminamos un camino con un máximo de aristas del gráfico, entonces los grados permanecen iguales. Pero en este caso, hay un circuito desarticulado de nuestro recorrido máximo. Siendo el curso una unión de circuitos disjuntos, concluimos que el curso inicial no fue máximo. De esto se deduce que el camino máximo contiene todas las aristas del grafo. La demostración es idéntica para el caso orientado.
Considere un grafo que admita una cadena euleriana. Agregar un borde entre el principio y el final de la cadena nos dará un ciclo euleriano. De manera similar, si eliminamos cualquier borde de un ciclo euleriano, tendremos una cadena euleriana.
Con esta transformación deducimos las condiciones necesarias y suficientes para que un grafo tenga una cadena (o camino) euleriana.
Condiciones necesarias y suficientes de la cadena/camino euleriano. El grafo es conexo (o fuertemente conexo). Para todos los vértices del gráfico, excepto posiblemente dos, su grado es par (su grado de salida es igual a su grado de entrada + o – 1 para posiblemente dos vértices.
Problema: gráfico hamiltoniano
En un gráfico dirigido, un circuito o un camino hamiltoniano es un circuito o camino que pasa una vez y solo una vez por todos los vértices. Lo mismo ocurre con el caso no orientado.
Hasta la fecha, no hay condiciones necesarias y suficientes, sino solo condiciones suficientes relacionadas con los grados de los vértices.
Dirac 1952. Un gráfico simple con no vértices (n> 2) cada vértice de los cuales tiene un grado al menos igual an / 2 es hamiltoniano.
Mineral de 1960. Un gráfico simple con no vérticesn> 2) tal que la suma de los grados de cualquier par de vértices no adyacentes sea al menos no es hamiltoniano.
Posa 1962. Un gráfico simple con no vértices (n> 2) tales que para todos k, 0 <k<(n-1)/2 le nombre de sommets de degré inférieur ou égal à k es inferior a k. El número de vértices de grado menor o igual que (n-1) / 2 es menor o igual que (n-1) / 2.
