MathCastle
Graph TheoryChallengeEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Challenge problem

Four depots 0,1,2,30,1,2,3 have roads 01:1001{:}10, 12:312{:}3, 23:323{:}3, 03:203{:}2, and a direct road 02:1502{:}15 (five roads total, no others). A crew based at depot 00 must clear every road and return to 00, duplicating roads where that is cheapest. What is the minimum total distance the crew must drive?