In the country of Drilandia, which has at least three cities, there are bidirectional roads connecting some pairs of cities such that any city can be reached from any other. Two cities are called close if one can reach the other by using at most two intermediary cities. The mayor, Drilago, fortified the road system by building a direct road between each pair of close cities that were not already connected. Prove that after the expansion, there exists a journey that starts and ends at the same city, where each city except the first is visited exactly once, and the first city is visited twice (once at the beginning and once at the end).
Problem
Source: XII International Festival of Young Mathematicians Sozopol 2023, Theme for 10-12 grade
Tags: combinatorics
Seicchi28
06.01.2025 16:18
The abridged problem is as follows: Given a connected graph $G$, simultaneously for each pair of vertices $u$, $v$ with distance at most $3$, connect them if they are not connected yet. We shall show there exist a hamiltonian cycle from the resulting graph. Take any spanning tree $T$ of $G$, and root it at any vertex $v$. We will describe the construction of such cycle starting from $v$. The main claim, which is sufficient for solving this problem, is that if the size of tree is more than $1$, then it's possible to construct a hamiltonian path starting from the root and ending in a direct child of the root. We prove this by strong induction on the size of the tree. The base cases are trivial. Now, we perform the induction step. Let $c_1$, $c_2$, $\dots$, $c_t$ be the direct children of $v$. For a vertex $x$, define $T(x)$ as the subtree of the tree which is rooted at $x$. We start the path from $v$ to $c_1$. If the size of $T(c_1)$ is greater than $1$, then by the induction hypothesis, there is a hamiltonian path starting from $c_1$, passing through all vertices in $T(c_1)$ and ending at $d_1$, a direct child of $c_1$. Since \[d(d_1, c_2) \le d(d_1,c_1) + d(c_1, v) + d(v, c_2) = 3,\]$d_1$ and $c_2$ are connected by a new edge, so we could move from $d_1$ to $c_2$. Otherwise, the size of $T(c_1)$ is $1$ and we move from $c_1$ to $c_2$ since their distance is at most $2$. Continue this process until the last subtree, where we end up either at $c_t$ or its direct child $d_t$. For the former case, since $c_t$ is a direct child of $v$, the induction hypothesis is proved. Otherwise, we end up with the hamiltonian path $v-c_1-\star-d_t$. Since the distance between $v$ and $d_t$ is at most $2$, they are connected by a new edge. Now, the new path $v-d_t-\textcolor{red}{\star}-c_1$ is a hamiltonian path (the red star is the reversed black star), and the last vertex is a direct child of $v$, proving our induction hypothesis.