Balkan Mathematical Olympiad Shortlisted Problems

Let a longest path of the graph be $P=V_1{V}_2\dots V_k$.

Case 1: $P$ consists of all vertices and there is no edge between $V_1$ and $V_k$. Swap vertices $V_i$ increasing $i$ from $1$ to $k$. $V_1$ and $V_k$ will never be lonely, as they will connect after the first swap and disconnect after the last swap. Vertex $V_i$ for $2\le i\le k-1$ will never be lonely as it will be connected to $V_{i+1}$ before it is swapped and to $V_{i-1}$ after it is swapped (because $V_{i-1}$ was swapped before).

Case 2: $P$ consists of all vertices and there is an edge between $V_1$ and $V_k$. Thus $V_1{V}_2\dots V_k{V}_1$ is a cycle that contains all vertices. As the graph is not complete, there exist $2$ vertices which are not connected, $V_a$ and $V_b$ ($a<b$). Swap $V_a$, then $V_i$ for $a+1\le i\le b-1$ (one path from $V_a$ to $V_b$ along the cycle), then $V_i$ for $a-1,a-2,\dots ,1,n,n-1,\dots ,b+1,b$ (the other path along the cycle). $V_a$ and $V_b$ will be connected during the procedure. For other vertices, the same argument as in Case 1 holds (they are always connected to at least one of the $2$ neighbours on the cycle).

Case 3: $P$ does not contain all vertices. Notice that $P$ must contain at least $3$ vertices, because otherwise every vertex would have a degree of $1$, which is impossible because the number of vertices is odd. Any swap ordering in which we swap first $V_1$, last $V_k$, other vertices $V_i$ in increasing order doesn't cause any vertices besides possibly $V_1$ and $V_k$ to be lonely. For internal vertices $V_i$ the same argument from Case 1 holds. Vertices outside of $P$ are not connected to $V_1$ and $V_k$ (otherwise, the longer path would exist). As we swap $V_1$ first and $V_k$ last, they will be connected to $V_1$ before their swap and to $V_k$ after. If $P$ contains at least $4$ vertices, then if we swap $V_1$, then $V_2$, then vertices outside of $P$, then remaining vertices of $P$, we notice that $V_1$ and $V_k$ will always be connected to some vertex outside $P$ or to their respective neighbors on $P$. If $P$ contains $3$ vertices, then we swap $V_1$, then one of the outside vertices, then $V_2$, then the remaining outside vertices, then $V_k$. Similarly to above, $V_1$ and $V_k$ will always be connected either to their neighbour in $P$ or to some outside vertex.