Let $$C \subseteq [r]^m$$ C ⊆ [ r ] m be a code such that any two words of C have Hamming distance at least t. It is not difficult to see that determining a code C with the maximum number of words is equivalent to finding the largest n such that there is an r-edge-coloring of $$K_{m, n}$$ K m , n with the property that any pair of vertices in the class of size n has at least t alternating paths (with adjacent edges having different colors) of length 2. In this paper we consider a more general problem from a slightly different direction. We are interested in finding maximum t such that there is an r-edge-coloring of $$K_{m,n}$$ K m , n such that any pair of vertices in class of size n is connected by t internally disjoint and alternating paths of length 2k. We also study a related problem in which we drop the assumption that paths are internally disjoint. Finally, we introduce a new concept, which we call alternating connectivity. Our proofs make use of random colorings combined with some integer programs.