  Feder and Subi conjectured that for any $2$-coloring of the edges of the
$n$-dimensional cube, we can find an antipodal pair of vertices connected by a
path that changes color at most once. We discuss the case of random colorings,
and we prove the conjecture for a wide class of colorings. Our method can be
applied to a more general problem, where $Q_n$ can be replaced by any graph
$G$, the notion of antipodality by a fixed automorphism $\phi \in Aut(G)$. Thus
for any $2$-coloring of $E(G)$ we are looking for a pair of vertices $u,v$ such
that $u= \phi(v)$ and there is a path between them with as few color changes as
possible. We solve this problem for the toroidal grid $G=C_{2a} \square c_{2b}$
with the automorphism that takes every vertex to its unique farthest pair. Our
results point towards a more general conjecture which turns out to be supported
by a previous theorem of Feder and Subi.
