**Definition**: Consider the cycles of length $4$ in the torus. Let us call a subgraph of the torus a right-up diagonal if it consists of $2k$ such $4$-cycles, and the $i$-th cycle's up right corner is the $i+1$-st cycle's left-down corner. Every edge of the torus can be naturally double covered with right-up cycles. Let us call a path *tight* if it is contained in a right up diagonal.

**We will prove slightly more.**

**Theorem**: In every $2$-coloring of the torus graph, there is a tight path that changes colors at most $k-1$ times.

**Proof**:

**Definition**: We define the right-up diagonal of length $l$ similarly to the right up diagonal ($1 \leq l \leq 2k$), but there are only $l$ connected 4-cycles. The original right up diagonal (of length $2k$) is similar to a circle, but all the other shorter ones are similar to paths (or diagonal arcs as we are on a torus). Thus the diagonals of length $l$ have a natural beginning and endpoint, which coincides if the diagonal is of length $2k$.

**Lemma**: Consider all the right-up diagonals of length $l$ and all the left-up diagonals of length $l$. The average number of minimal color changes needed to get from the beginning to the endpoint of a diagonal, such that we can not leave the diagonal is at most $l$.

**Proof**: Consider a $4$-cycle. There is a right-up and a left-up diagonal containing this cycle. If (WLOG) at the right-up diagonal we have to change colors twice in this cycle, it must happened this way: We arrived to the bottom left vertex of the cycle with our path having (WLOG) the color blue. Both edges adjacent to this vertex and belonging to this cycle were red, and the other two edges blue. Thus the left-up diagonal containing this cycle does not have to change colors at this cycle, as there is a red and a blue monochromatic path between the bottom right and the top left vertices. Thus on the average a single $4$-cycle can not cause more than $1$ color change. $ \square $

**Corrolary**: As in a diagonal of length $k$, the beginning and endpoints of the diagonal are antipodal. We have that the average number of necessary color changes from a point to its antipodal pair using only tight paths is at most $k$. (Actually when we averaged, we took into account all the four possible diagonals connecting these points, and the best tight path in every such diagonal.)

So we will have such a path with only $k-1$ color changes unless the average is exactly $k$ and *every* such path with minimal color changes has to change colors *exactly* $k$ times. Consider now diagonals of length $2k$. By the lemma we have that the average number of paths with minimal number of color changes from the beginning to the endpoint (which is the same point) is at most $2k$ (not counting that maybe we arrive with a different color when we close the cycle). but every diagonal of length $2k$ is the union of two diagonals of length $k$ where we have that we need $k$ color changes. Thus if the average number of color changes is $2k$ but we always need at least $2k$ changes, we conclude that in every right-up and every left-up diagonal, there is a $2k$ cycle that changes colors exactly $2k$ times. (now we can count all the color changes, as after an even number of color changes, in the end we always arrive with the starting color)

Now we will work with these cycles.

**Definition**: Let us call a vertex in a right-up diagonal subgraph *central*, if every cycle of length $2k$ in this subgraph, passes through this vertex. There are $2k$ central and $4k$ non central vertices in every right-up diagonal of length $2k$. Every vertex is central in precisely one right-up diagonal of length $2k$.

Consider a right up diagonal of length $2k$ and the associated cycle with $2k$ color changes. If such a cycle has a color change at a central vertex, we have a path along this cycle to the antipodal pair of this vertex with at most $k-1$ changes. Thus we can assume that every such cycle has its color changes at non-central points. But then the cycles have to change its color at every non-central point as there are $2k$ color changes. Thus if there are antipodal non-central points on this cycle, we have exactly $k-1$ color changes between them.

The only case left to examine is when we have such a cycle, and every non-central point on the cycle is such that its antipodal pair is not on the cycle. We could change the cycle along a $4$-cycle of the right-up diagonal. (As every $4$-cycle has two common edges with our $2k$ cycle and two other edges.) So if we change the cycle this way and the number of color changes is still $2k$, we are done.

If for every $4$-cycle we can not change our cycle without increasing the number of color changes, we will conclude that every $4$-cycle is colored properly (adjacent edges have different colors): Let C_4 be a $4$-cycle on a right-up diagonal. The associated cycle with $2k$ color changes shares exactly two edges with this cycle. At the associated cycle, there are no color changes at the central vertices, and there is always a color change at non-central vertices. Thus the change of the cycle along this $4$-cycle increases the number of color changes, the $4$-cycle had to be colored properly. (draw a nice picture)

There is only one coloring where every $4$-cycle is colored properly, and at this coloring it is easy to find tight paths connecting antipodal vertices. $\square$