3 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$