Bulgarian Spring Tournament

Consider a graph $G$ with vertices the binary vectors of length $d$ and edges connecting the pairs of vectors that differ in exactly one position. Let $\mathcal{M}$ be a complete $d$-dimensional pairing. We will prove that for each vertex $\mathbf{x} \in \{0,1\}^d$ of $G$ we can find an alternating cycle of length no more than $2d-2$ among the distance vectors of the most many 2 of $\mathbf{x}$.

Let $\mathbf{x} \in \{0,1\}^d$ have as neighbors $\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_d$ in $G$. Without loss of generality let $\{\mathbf{x}, \mathbf{x}_1\} \in \mathcal{M}$, and the vectors $\mathbf{x}_2, \dots, \mathbf{x}_d$ form pairs in $\mathcal{M}$ respectively with $\mathbf{y}_2, \dots, \mathbf{y}_d$ (which are at distance 2 from $\mathbf{x}$). Notice that each of the vectors $\mathbf{y}_2, \dots, \mathbf{y}_d$ has exactly two neighbors among $\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{y}_d$ in $G$. We will consider two cases:

Case 1. Any of the vectors $\mathbf{y}_2, \dots, \mathbf{y}_d$, say $\mathbf{y}_i$, is a neighbor of $\mathbf{x}_1$ in $G$. Then $\mathbf{x}, \mathbf{x}_1, \mathbf{y}_i, \mathbf{x}_i$ form an alternating cycle of length $4 \le 2d-2$.

Case 2. None of the vectors $\mathbf{y}_2, \dots, \mathbf{y}_d$ is a neighbor of $\mathbf{x}_1$ in $G$. Consider the following algorithm. At the beginning, let's place a token at vertex $\mathbf{x}_2$ and at each step:

* if the token is located at a vertex $\mathbf{x}_i$ for some $i \in \{2, \dots, d\}$, we move it to a vertex $\mathbf{y}_i$;
* if the token is located at a vertex $\mathbf{y}_i$ for some $i \in \{2, \dots, d\}$, we move it to the neighbor of $\mathbf{y}_i$ other than $\mathbf{x}_i$.

Obviously, after no more than $2d-2$ runs of the algorithm, some vertex will be repeated. Since the algorithm describes a walk on the graph $G$ where every odd edge is in $\mathcal{M}$ and every even edge is outside $\mathcal{M}$, it finds an alternating cycle after at most $2d-2$ moves, whence the statement also follows in this case. $\square$