Supongamos que tenemos un grafo conexo G = (V, E); entonces, las siguientes declaraciones son equivalentes: Un camino euleriano (un camino que no es cerrado, pero que utiliza todas las aristas de G apenas una vez y solamente una vez) existe si y solamente si G es conectado y tiene dos vértices de valencia impar.
Un enlace-T mínimo puede ser obtenido por un algoritmo de correspondencia ponderada que usa O(n3) pasos computacionales.
Tal camino existe si y solamente si cada nodo del grafo es de grado par.
En este último caso, es más simple considerar el problema alternativo siguiente: en vez de permitir de pasar varias veces por la misma arista, se duplican las aristas del grafo en donde se permite pasar dos veces.
Obviamente, el problema planteado entonces es del mismo tipo, pero ahora aplicado a un grafo diferente.
Entonces, la solución óptima consiste en encontrar el camino más corto del nodo u al nodo v (utilizando por ejemplo el algoritmo de Dijkstra), completando el grafo con las aristas de este camino.