Latin rectangles

A latin rectangle, where , is an array with rows and columns in which each of symbols occur such that each row contains every symbol once and no symbol occurs more than once in a column.

Any latin rectangle can be completed to form a Latin squareLatin square.

Proof:
Call the symbols , the column and the rows . We can now create a Bipartite graphBipartite graph with vertices where all are connected to every . Now, if a column contains , we ColourColour that edge where is the row where appears in . Now, let be the set of uncoloured edges. The graph is now bipartite and regular with degree since each column contains distinct colours. By TheoremTheorem we know has an edge colouring with at most colours, call them . We can now extend the latin rectangle to a latin square where we put in where is the colour of .

Let be a partial latin rectangle in which the symbols are used, and let be the number of times occurs in . Then can be completed to a latin square if and only if for every .

Proof:
: We know should appear exactly times in the completed square. We also know it appears exactly times among the added rows, and times among the added columns, meaning it appears additional times, so we have : We construct a bipartite graph with vertices where denote the rows, and let be an edge if does not occur in row . We know each row contains distinct symbols, so for every . Now, since , and we know every occurence of is in a different row, we know has an edge to at most rows, so . This means that the maximum degree of our graph is , so by TheoremTheorem there exists an edge colouring with at most colours, call them . Finally, we extend the rectangle to an latin rectangle by putting in where is the colour of the edge . Now, by TheoremTheorem, this can be extended to an latin square.