If we label the vertices in the first cluster with labels *"row 1", "row
2",* etc. and label the vertices in the second cluster with labels
*"col 1", "col 2",* etc, and label the edges of the *i*-th
one-factor with symbol *i* (*1<=i<=n*), then a one-factorisation
is seen to be the same thing as a latin square: the cell in row *i*,
column *j* is filled with the symbol attached to that corresponding
edge.

If we label the vertices in each cluster with the numbers *1,2,...,n*,
then each one-factor is a permutation on this set. So a one-factorisation
is the same as a set of *n* permutations in the symmetric group
*S _{n}* with the property that, for any pair

In a one-factorisation, the union of any two one-factors forms a
*2*-regular graph on *2n* vertices (in fact, each component is
a cycle of even length). A *perfect one-factorisation* is one in
which the union of any two distinct one-factors is a single cycle of
length *2n*. A more general class of one-factorisations is the class
of *uniform one-factorisations*. A one-factorisation is
*uniform* of *shape* *[k _{1},k_{2},...,
k_{s}]*
provided the union of any two distinct one-factors is a graph with
components of lengths

Viewed as a set of permutations in the symmetric group, we seek
*n* elements of *S _{n}*, say