A labyrinth is a system of $2024$ caves and $2023$ non-intersecting (bidirectional) corridors, each of which connects exactly two caves, where each pair of caves is connected through some sequence of corridors. Initially, Erik is standing in a corridor connecting some two caves. In a move, he can walk through one of the caves to another corridor that connects that cave to a third cave. However, when doing so, the corridor he was just in will magically disappear and get replaced by a new one connecting the end of his new corridor to the beginning of his old one (i.e., if Erik was in a corridor connecting caves $a$ and $b$ and he walked through cave $b$ into a corridor that connects caves $b$ and $c$, then the corridor between caves $a$ and $b$ will disappear and a new corridor between caves $a$ and $c$ will appear). Since Erik likes designing labyrinths and has a specific layout in mind for his next one, he is wondering whether he can transform the labyrinth into that layout using these moves. Prove that this is in fact possible, regardless of the original layout and his starting position there.
Problem
Source: Baltic Way 2024, Problem 6
Tags: combinatorics, combinatorics proposed, graph theory
07.01.2025 19:31
We consider the caves as vertices and the corridors as edges of a graph. Initially, the graph is a tree, and it is straightforward to see that after any move, the graph remains a tree. A premove is defined as the action of rebuilding the old edge, deleting the new edge, and having Erik return to the original edge. Clearly, a premove consists of exactly four moves. Thus, it suffices to prove that for any arbitrary vertex \( A \), Erik can transform the graph into one where \( A \) is connected to all other vertices. Initially, Erik moves to an edge adjacent to \( A \), denoted as \( AB \). We will prove that if \( A \) is not yet connected to all other vertices, we can increase the degree of \( A \) such that Erik remains on an edge adjacent to \( A \). If \( B \) is connected to some vertex \( C \neq A \), Erik removes \( AB \), moves through \( B \) to \( BC \), and connects \( AC \). Then, he removes \( BC \), moves through \( C \) to \( AC \), and reconnects \( AB \). If \( B \) is a leaf, there must exist a neighbor \( D \neq A \) connected to some vertex \( E \neq A \). First, Erik removes \( AB \), moves to \( AD \), and connects \( BD \). Next, he removes \( AD \), moves through \( D \) to \( BD \), and reconnects \( AB \). Subsequently, he removes \( BD \), moves through \( D \) to \( DE \), and connects \( BE \). Then, he removes \( DE \), moves through \( E \) to \( BE \), and reconnects \( AB \). Finally, Erik removes \( BE \), moves through \( B \) to \( AB \), and connects \( AE \). Like the first case, we can increase the degree of \( A \) such that Erik remains on an edge adjacent to \( A \). This process continues until \( A \) is connected to all other vertices, completing the proof.