MathCastle
Graph TheoryChallengeEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Challenge problem

A hub office is directly linked to 55 branch offices 1,2,3,4,51,2,3,4,5 (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?