MathCastle
Graph TheoryChallengeEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Challenge problem

Four depots 0,1,2,30,1,2,3 are joined by a road between every pair, with lengths 01:301{:}3, 12:412{:}4, 23:223{:}2, 03:503{:}5, 02:602{:}6, 13:713{:}7 (km). 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?