# One-to-one correspondence between n-edge-colourings of $K_{n,n}$ and Latin squares

I need help with this. I don't know how to do this (especially case b) ).

a) An $n \times n$ array $A = (a_{ij})$, whose entries are taken from some set $S$ of $n$ symbols, is called a Latin square of order $n$ if each symbol appears precisely once in each row and precisely once in each column of $A$. Show that there is a one-to-one correspondence between $n$-edge-colourings of $K_{n,n}$ in colours $1, 2, \dots , n$ and Latin squares of order $n$ in symbols $1, 2, \dots, n$.

b) Deduce from the (below) Theorem the following assertion, a special case of a conjecture due to J. Dinitz.

For $1 \leq i\leq j \leq n$, let $S_{ij}$ be a set of $n$ elements. Then there exists a Latin square $A = (a_{ij})$ of order $n$ using a set $S$ of $n$ symbols such that $a_{ij} \in S_{ij} \cap S$, $1 \leq i \leq j \leq n$.

Theorem: Every simple bipartite graph $G$ is $\Delta$-list-edge-colourable.

• I don't understand the assertion in part (b). Are $S_{ij}$ and $a_{ij}$ only defined for $i\le j$? And what if the sets $S_{ij}$ happen to be pairwise disjoint, so that the elements $a_{ij}$ are pairwise distinct? What is the "set $S$ of $n$ symbols" supposed to be in that case? – bof Mar 5 '17 at 0:53 Basically, the symbol $s$ in cell $(a,b)$ maps to the edge $\text{row}_a \text{col}_b$, say, of color $s$. The list $L$ assigned to cell $(a,b)$ maps to the edge $\text{row}_a \text{col}_b$ which is also assigned the list $L$. The theorem implies a $\Delta$-list-edge-coloring exists, which we convert back to give a $n \times n$ matrix which we can show has no repeated symbols in the rows and columns.