Un grafo ammette un ciclo Euleriano se e solo se e' connesso e tutti i nodi hanno grado pari. Siccome qui si richiede che ogni arco venga percorso ALMENO una volta, vuol dire che siamo chiamati ad aggiungere archi (per duplicazione di archi gia' esistenti) in modo tale da assicurare tali due proprieta'. Si noti che la proprieta' di connessione non puo' essere introdotta con l'aggiunta di archi paralleli ad archi gia' esistenti. Il fatto che ogni istanza abbia una soluzione ammissibile e' garantito dall'esistenza in ciascuna istanza di uno spanning tree (l'albero DFS).