As an interesting aside: because the network is a tree, there can only be at most three alternative capitals, one of which is of course the next most populous planet NxtPop:
- case 1: NxtPop is directly connected to the capital; then you need at most two more planets, drawn from three groups: the other capital neighbours, the other NxtPop neighbours, and all other planets
- case 2: NxtPop and the capital have a common neighbour; then you need one more planet that is not adjacent to that common neighbour
- case 3: NxtPop and the capital have no common neighbours; then you do not need any other planet.