I have been confronted with the following homework question:
Let $M$ be a table of size $N \times N$. A legal filling of $M$ with the numbers $\{1,\dots,N\}$ is one such that each cell of the table has exactly one number and each line and each row contains each number exactly once.
Prove that for any partial filling of $M$, of the first $0 < k < n$ rows, it is possible to completely fill $M$ in a legal way.
Hint: Use bipartite matching
Given a table of size $k \times N$, construct a bipartite graph whose left vertices $c_1,\ldots,c_N$ correspond to the $N$ columns of the table and whose right vertices are $1,\ldots,N$. For each $i$, join $c_i$ to $j$ whenever $j$ does not occur as an entry in column $i$. In other words, the neighbors of $c_i$ are the numbers which do not appear in column $i$ of the given table.
Since the given table contains $k$ entries in each column (and so has $N-k$ entries missing in each column), each left vertex $c_i$ has valency $N-k$. In the given table, each entry has appeared $k$ times and so is missing from exactly $N-k$ columns. Thus, each right vertex $j$ in the bipartite graph has valency $N-k$. Hence, the bipartite graph is regular of valency $N-k$.
The bipartite graph which we constructed satisfies Hall's condition: any subset $S$ in the left vertex set has at least $|S|$ neighbors in the right vertex set. This is because $S$ is incident to $(N-k)|S|$ edges, and each right vertex is incident to exactly $(N-k)$ edges, whence the number of right vertices needed to cover $(N-k)|S|$ edges is at least $|S|$.
By Hall's theorem, the bipartite graph has a perfect matching. A perfect matching is a set of $N$ edges which gives the entries for the next row of the table. This process can be repeated to complete the table. We have shown that any $k \times N$ Latin rectangle can be completed to a Latin square.
