When is round-robin scheduling possible and with in minimal time? Suppose that you have six teams $x_0, x_1, x_2, x_3, x_4, x_5$. Can you schedule round-robin games between them so that if one game is played each day, the series of games can be completed in five weeks?
A naive attempt fails:
$$(x_0,x_1), (x_2, x_3), (x_4, x_5)$$
$$(x_0,x_2), (x_1, x_3) .. oops$$ 
Some care is needed to get this to work. A solution:
$$(x_0,x_3), (x_1, x_5), (x_2, x_4)$$
$$(x_1,x_4), (x_2, x_0), (x_3, x_5)$$
$$(x_2,x_5), (x_3, x_1), (x_4, x_6)$$
$$(x_0,x_1), (x_2, x_3), (x_4, x_5)$$
$$(x_0,x_5), (x_2, x_1), (x_4, x_3)$$
This solution certainly is not easy to generalize. Questions:


*

*Is this in fact always possible for an even number of teams?

*Is there a convenient algorithm for producing the schedule?

*Can this problem be easily expressed in terms of graph theory, combinatorics, or abstract algebra?


In terms of graph theory, what you are asking for is a decomposition of the complete graph on $n$ vertices into $n-1$ perfect matchings.  The vertices are the competitors and the edges are the games.  The edges in a perfect matching determine which games are played in a given week, so, if the edge $uv$ is in matching $i$, then $u$ and $v$ play against each other in week $i$.  Perfect matchings are also called 1-factors, and a decomposition into perfect matchings is called a 1-factorization.
You could also say that it is a proper edge-colouring of the complete graph on $n$ vertices using $n-1$ colours.  The edges in a colour class form a perfect matching.  If the edges are coloured $1,2,...,n-1,$ then team $x$ plays team $y$ in week $i$ if the colour of $xy$ is $i$.
The construction that I was taught is to place vertices all vertices but one evenly around a circle, and place the other vertex, $u$ say, at the centre of the circle.  For each vertex $v$ on the circle, form a matching from the edge $uv$ and all edges whose vertices are reflections of each other in the line through $u$ and $v$.  Each matching can be obtained from the others by rotating around $u$.  
You could also describe it in terms of modular arithmetic.  Suppose that the vertices are $0,1,...,n-2,\infty$.  Matching 0 has edges $\{\infty, 0\},\{1,n-2\},\{2,n-3\},\ldots$.   All other matchings can be obtained by adding modulo $n-1$ to all vertices other than $\infty$.  So


*

*Matching 1 has edges $\{\infty, 1\},\{2,n-1\},\{3,n-2\},\ldots$

*Matching 2 has edges $\{\infty, 2\},\{3,n\},\{4,n-1\},\ldots$

*Matching 3 has edges $\{\infty, 3\},\{4,n+1\},\{5,n\},\ldots$

*$\ldots$


This is equivalent to the construction that Uwe described elsewhere on this page.
