claim: we can always move AB to AC, even if BC does not exist, without changing anything else. proof: we have two cases. first, if there exists a path B, X_0, X_1, .... from B to C not going thru A, we consider all X_i connected to A, denote them let there be m of them denoted as Z_i. now it is easy to move AZ_m -> AX_something -> AX_something+1 ... -> AC, AZ_{m - 1} -> AX_{something else} ... -> AZ_{m}, .... AB -> AX_0 .. -> AZ_1 since we always have AX_{something} and AX_{something + 1} but never X_{something}X_{something + 1}. it is also easy to see that any deleted vertices are restored. second, if there does not exist such a path, we can consider moving AB to BC and BC to AC as two applications of the first case. basically just induct, base case of n = 3 is trivial we now outline a two part algorithm to solve the case with n + 1 cities. observe that moves are entirely reversible, so assume we want to move from some configuration P to Q where the vertex of some degree A in P is strictly lower than that of Q. step 1: make the degree of A equal in P and Q. if there exists some vertex X not connected to A and connected to some other vertex Y, it is easy to move XY to AX using the claim, increasing the degree of A by 1 without changing anything. otherwise assume no vertex X not connected to A and connected to something else, that means every vertex must be connected to A to avoid violating connectivity, meaning that the degree of A is maximal and it is impossible for the degree of A in P to be lower of it in Q. step 2: finish. we can independently match P and Q for the respective subsets of the configurations only considering the n vertices that are not A. then it is easy to spam the claim until we can match each edge from A, since the claim is op and lets us do anything.

ezpotd wrote: claim: we can always move AB to AC, even if BC does not exist, without changing anything else. ... No, you cannot do this! This operation preserves the connectivity. Suppose now, the graph is connected but if $AB$ is removed it becomes disconnected, that is, $AB$ is the only edge between two connected components - see the figure. So, if you remove $AB$ and draw $AC$ you arrive at a disconnected graph. That's why you cannot do it through any series of allowed operations.

Attachments:

So, we want to prove that we can switch from one connected graph with a vertex set $V$ to any other connected graph on the same set of vertices and with the same number of edges through a series of allowed operations. Let the two graphs be $G$ and $G'$. Let $T$ be a spanning tree of $G$. We can always make series of operations on $G'$ so that to guarantee that $T$ is present in $G'$. We can start from any vertex $v_0\in T$ (we can call it the root of $T$) and successively construct in $G'$ the edges of $T$ incident to $v_0$ and then all the other edges of $T$, exploiting the fact that $G'$ is connected. After we took care that $T$ is present in $G'$, we can "add" in $G'$ any other edge of $G$ that connects vertices of $T$.