Graph TheoryHardEulerian and Hamiltonian Graphs
Eulerian and Hamiltonian Graphs · Hard problem
A plow town has intersections with roads (nine roads, no others). The plow must start at , finish at , and clear every road, retracing a road (building a short duplicate stretch) only where necessary. What is the minimum number of roads that must be duplicated?