How Do You Schedule a League So Everyone Plays Everyone?

Start with the number of matches. With 6 teams, team 1 has 5 opponents, team 2 has 4 more (it has already been counted against team 1), team 3 has 3 more, and so on:

$$5 + 4 + 3 + 2 + 1 = 15 \text{ matches.}$$

That is an arithmetic series, so Grade 10’s formula for its sum works: with n teams there are $1 + 2 + \cdots + (n - 1) = \frac{n(n-1)}{2}$ matches. It is the same count as the handshakes at a party: each team has n − 1 opponents, and n(n − 1) counts every match twice, once from each side.

The last column comes from one team’s point of view. Team 1 has n − 1 opponents and meets at most one a round, so no timetable can be shorter than n − 1 rounds. And n − 1 rounds is exactly enough room: n − 1 rounds of $\frac{n}{2}$ matches hold $\frac{n(n-1)}{2}$, every match. So a perfect timetable has no spare room at all: every team plays in every round.

An odd number of teams

With 5 teams, somebody is always left over: a round has room for only 2 matches, with one team resting. There are $\frac{5 \times 4}{2} = 10$ matches, and 10 ÷ 2 = 5, so 5 rounds at least, one more than the 4 opponents each team has. Every team gets exactly one rest. The same holds for any odd number: n teams need at least n rounds, because a round holds at most $\frac{n - 1}{2}$ matches.

There is an old trick for this. Invent an extra team, a ghost, and make a timetable for n + 1 teams. Whoever is drawn against the ghost in a round rests (a bye, in sports words). So the odd case is the even case with one team that never turns up, and from here on we can think about an even number of teams.

Here is how Sushma Miss’s sheet goes wrong, made small. Six teams. The first three rounds look perfectly sensible:

No team plays twice in a round, no pair plays twice. Two rounds left. Try to finish.

Nothing in the first three rounds broke a rule. But they used up every match between {1, 2, 3} and {4, 5, 6}, leaving only matches inside the groups, which can never fill a round. A good timetable plans the end from the start.

How easy is it to fall in? There are 480 ways to choose rounds 1, 2 and 3 for six teams, in that order, each a full round and no pair twice. Our script tried them all: 120, one in four, end in this trap. It then filled whole timetables the way a hurried person would, as the Fill at random button does, a round at a time: go through the matches still to play in a random order, put each in this round if both teams are still free, and start the next round when nothing more fits. Out of 100,000 tries each:

So for ten teams, filling in pairs as they come almost never fits nine Saturdays.

Draw each team as a dot and each match as a line between two dots. With every pair joined, the picture is called the complete graph on n dots, written $K_n$. (A graph here is any set of dots and lines, the same idea as the bridges of Königsberg.)

Now give each round a color, and paint each line in the color of the round it is played in. The rule “no team plays twice in a round” becomes:

the lines meeting at any dot all have different colors.

That is called an edge coloring of the graph (mathematicians call the lines edges and the dots vertices). A set of lines with no dot in common, one round, is called a matching, and a matching that touches every dot, a round where everyone plays, is a perfect matching. The fewest colors that can paint a graph this way is its chromatic index.

So the puzzle, in these words: what is the chromatic index of $K_n$? We have already shown it is at least n − 1 for even n (one dot has n − 1 lines, all different colors) and at least n for odd n. The trap shows that a careless coloring can need more. What we need is a coloring that always works.

Here is a timetable that never gets stuck. For ten teams, put teams 1 to 9 at the corners of a regular nine-sided shape and team 10 in the middle.

• In round 1, team 1 plays the middle team, 10.
• Every other team plays its mirror image in the line through team 1 and the middle: 2 plays 9, 3 plays 8, 4 plays 7, 5 plays 6. Their lines are all parallel.
• In round 2, turn the mirror line on to team 2, and so on.

After 9 rounds the faint lines join every pair, each exactly once. Why does it always work?

Why every pair meets exactly once

Take any two corner teams, say 2 and 7. Going round the shape from 2 to 7 one way takes 5 steps (2, 3, 4, 5, 6, 7); the other way takes 4 (7, 8, 9, 1, 2). The two ways add up to 9, an odd number, so exactly one of them is even. Halfway along the even way, 2 steps from each, is a corner: 9. The mirror line through 9 and the middle swaps 2 and 7, since they are the same number of steps from 9, one each way. That is the only line that swaps them (it must cross the line from 2 to 7 at right angles, through its midpoint), and halfway along the odd way is the middle of a side, not a corner. So in round 9, 2 plays 7, and in no other round. The same works for any two corners.

And each round is a full round: the mirror turns the shape onto itself, so it pairs every corner with another corner; the corner on the line plays the middle, and no other corner lies on the line: its far end is 4½ steps round from its corner either way, the middle of a side. Every corner team plays the middle once, in its own round. That is all 45 matches, in 9 rounds of 5.

The same argument works for any even number of teams: n − 1 is odd, so there is always an odd number of corners. So:

For an even number of teams n, a round robin needs exactly n − 1 rounds; for an odd number, exactly n rounds (use the circle method with the ghost in the middle: the team on the mirror line rests). In the language of graphs, $K_n$ has chromatic index n − 1 when n is even and n when n is odd, and splitting its lines into perfect matchings is called a one-factorization.

The same thing in numbers

Number the corners 1 to 9 round the shape. A corner and its mirror image are the same number of steps from the mirror’s corner r, one each way: r + k and r − k. Their sum is 2r. Going round past 9 wraps back to 1, so the sums are counted by their remainders on dividing by 9 (as in the egg basket puzzle):

$$\text{teams } i \text{ and } j \text{ meet in round } r \text{ when } i + j \text{ and } 2r \text{ leave the same remainder on division by } 9.$$

And in round r, team r itself plays team 10, in the middle.

So you can find any match’s round without drawing anything. When do 2 and 7 meet? 2 + 7 = 9, remainder 0, and 2r = 18 leaves 0 when r = 9: round 9. Since 2 and 9 share no factor, exactly one r from 1 to 9 works for each pair: that is the picture’s “exactly one corner” in numbers.

Chess organizers have used this timetable for well over a century. Their printed versions are called Berger tables, after the Austrian chess master Johann Berger, who published them crediting Richard Schurig’s tables of 1886.

Real leagues add a rule the circle can’t see. One team of each pair plays at home. Leagues try to avoid two home games in a row, or two away games, for fairness: a long run of either helps or hurts a team. Two such rounds in a row are called a break. The Premier League’s fixture list, for example, aims for “a team will never have more than two home or away matches in a row”.

Can a round robin have no breaks at all? Each team would then alternate: HAHAH… or AHAHA…. Try it with 6 teams in your head before reading on.

Here is the argument that it can’t, for any league with an even number of teams, everyone playing every round. Suppose two teams both follow HAHAH…. They are at home in exactly the same rounds, including the round in which they play each other, and one of them must be away then. So at most one team can follow HAHAH…, and likewise at most one AHAHA…. Every other team has at least one break, so

$$\text{breaks} \ge n - 2.$$

The circle method meets this bound, if home and away are chosen well. The middle team is away in odd rounds and at home in even ones. In each mirror pair, one team is k steps past the mirror’s corner, counting up, and the other k steps before it: the one past is at home when k is odd, the one before when k is even. Our script did this for 6 teams:

Four breaks for six teams: the fewest possible. For ten teams it gives eight, and for every even number checked, up to 22, exactly n − 2. The bound is Dominique de Werra’s, from 1980, and papers on sports scheduling call it a well-known fact.

When not everyone plays everyone

Many real schedules aren’t complete round robins: teams play only some of the others. Each is still an edge-coloring puzzle, on a graph with some lines missing. If the busiest team has d matches, at least d rounds are needed. In 1964 Vadim Vizing proved that d + 1 rounds are always enough, whatever the graph. Sometimes d is enough (any league split into two groups where every match is between the groups), sometimes it isn’t (an odd round robin needs d + 1); deciding which is one of the problems computer scientists call NP-complete: no quick method is known for big graphs (Ian Holyer, 1981).

• How Do You Connect Every Village with the Least Cable? Another network puzzle where the greedy way, taken carefully, does work.
• How Does a Map App Find the Quickest Route? Networks with lengths on the lines.
• How Many Handshakes at a Party of 30? (Grades 6–8) The count of the matches, three ways.
• Can You Cross Every Bridge Just Once? (Grades 6–8) Where graphs began.
• Graphs, Maps, Routes and Networks (Grade 10 Computing) Networks in Python.
• Computing, Going Further: Can Four Colors Paint Any Map of Nepal? Coloring the dots instead of the lines. (Coming soon.) And How Can Students Be Matched to Colleges So No One Wants to Swap? Another kind of matching. (Coming soon.)
• Grade 10: Sum of an arithmetic series, the count of the matches.