MathCastle
Graph TheorySuperchallengeEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Superchallenge problem

Two separate crews each built their own little road network: crew A built 0-1-2-30\text{-}1\text{-}2\text{-}3 (a straight path of three roads) and crew B built 4-5-6-74\text{-}5\text{-}6\text{-}7 (another straight path), with no roads yet joining the two networks. The city wants the fewest possible new roads added so that a single walk exists crossing EVERY road (from both networks) exactly once. What is the minimum number of new roads needed?