By triangular inequality, the best Eulerian graph must have the same cost as the best travelling salesman tour, hence finding optimal Eulerian graphs is at least as hard as TSP.
Dar, conform inegalității triunghiului, cel mai bun graf eulerian trebuie să aibă același cost ca cel mai bun drum al comis-voiajorului, prin urmare, găsirea de grafuri euleriene optime este cel puțin la fel de grea ca PCV.