Filling an NxN table with N numbers 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

 A: 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. 
