MathCastle
Graph TheoryHardEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Hard problem

A plow town has intersections A,B,C,D,E,FA,B,C,D,E,F with roads AE,BE,BC,AF,EF,DE,DF,CE,ACAE, BE, BC, AF, EF, DE, DF, CE, AC (nine roads, no others). The plow must start at AA, finish at FF, 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?