Graph TheoryChallengeEulerian and Hamiltonian Graphs
Eulerian and Hamiltonian Graphs · Challenge problem
A hub office is directly linked to branch offices (a "star"), with no links between the branches themselves. The company wants to add the fewest possible new branch-to-branch links so that there is a single closed tour starting and ending at the hub that visits every branch exactly once. What is the minimum number of new links needed?