  In this paper, we exhibit an irreducible Markov chain $M$ on the edge
$k$-colorings of bipartite graphs based on certain properties of the solution
space. We show that diameter of this Markov chain grows linearly with the
number of edges in the graph. We also prove a polynomial upper bound on the
inverse of acceptance ratio of the Metropolis-Hastings algorithm when the
algorithm is applied on $M$ with the uniform distribution of all possible edge
$k$-colorings of $G$. A special case of our results is the solution space of
the possible completions of Latin rectangles.
