MathCastle
Graph TheoryChallengeEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Challenge problem

Five landmasses A,B,C,D,EA,B,C,D,E are joined by bridges AB,AC,AD,BC,BE,CD,CE,DEAB, AC, AD, BC, BE, CD, CE, DE (eight bridges, no others). City engineers may close (permanently remove) some bridges to simplify upkeep, but still want SOME walk that crosses every remaining bridge exactly once (not necessarily a closed loop). What is the minimum number of bridges that must be closed?