How can I schedule an $8$-team tournament with $7$ rounds of four $1v1$ games such that each team plays all the other seven exactly once?

Question

In my understanding this is $K_8$, and the question is how to obtain a colouring $c:E(K_8) \rightarrow \{1,\dots,7\}$ such that $c^{-1}(j)$ is a matching for every $j =1, \dots ,7$.

Because this way each colour would represent the number of the round $($there must be $7$ rounds and each team must play once in each round, but every team needs to play every other team exactly once in the tournament$)$

The condition that $K_8$ is the complete $8$-vertices graph takes care of the "every team plays every other team exactly once" part, and the matching condition on the colouring ensures every team plays exactly one game at each round.

But even if I wrote this problem in graph theory notation I fail to actually obtain the colouring... How can I obtain that?

Answer 1

Given in a tournament there are $8$ teams and let us consider them from $1$ to $8$

Take a regular $n-1$ sided polygon $($Here we choose heptagon for $8$ teams$)$

Draw horizontal stripes as shown below. Then, join the vertex that has been left out to the centre. Each segment represents teams playing each other in the first round.

So, in the first round the teams $(7, 6), (1, 5), (2, 4) \mbox{and} (3, 8) $ play.

Continue rotating the polygon until it returns to its original position. \begin{array}{c|c|c|c|c|c|c} \mbox{ Round}&\mbox{ A}&\mbox{B}&\mbox{C}&\mbox{D}\\\hline I&(7,6)&(1,5)&(2,4)&(3,8)\\ II&(6,5)&(7,4)&(1,3)&(2,8)\\ III&(5,4)&(6,3)&(7,2)&(1,8)\\ IV&(4,3)&(5,2)&(6,1)&(7,8)\\ V&(3,2)&(4,1)&(5,7)&(6,8)\\ VI&(2,1)&(3,7)&(4,6)&(5,8)\\ VII&(1,7)&(2,6)&(3,5)&(4,8)\\ \ \\ \end{array}

Answer 2

Represent each team by an ordered triple where each term can be zero or one. So our teams are:

Team A = $\{0,0,0\}$

Team B = $\{0,0,1\}$

Team C = $\{0,1,0\}$

...

Team H = $\{1,1,1\}$

Now, in round n, convert the round number, n, to binary, and xor $(\veebar)$ the round number in binary with the team's ordered triple.

So, for example, in round $3$, and $3 = 0,1,1$, so Team B = $\{0,0,1\}$ plays Team $\{0\veebar0, 0\veebar1, 1\veebar1\}$ = $\{0,1,0\}$ which is Team C. Thus in round $3$ Team B plays Team C. Note that this relationship is symmetric, so when Team B plays Team C, Team C also plays Team B, as one would hope.

This will actually go fairly quickly if you do it out on paper.

Answer 3

@JoshB. gives an interesting scheme that seems to only work for powers of 2 (I could be wrong) and @KeyFlex gives the general scheme that I've seen before. But there's an even more general theory going on here.

There's a couple of key-words you are missing that would make looking up this problem easy. A $k$-factor is a $k$-regular graph, meaning every vertex has degree $k$. So a $1$-factor is a matching. A decomposition of the edges of a graph into matchings is then called a 1-factorization, that is, a partition of the edges where each part is a perfect matching. Then your original question is to find a 1-factorization of $K_8$, whereas KeyFlex's scheme will yield a 1-factorization for any $K_n$ where $n$ is even.

More generally we can ask which graphs have a 1-factorization. One can immediately see that the graphs have to be regular, but this condition is not sufficient. See Wikipedia for more information.

P.S. you may also call the kind of tournament you are scheduling a "Round-Robin." This would have also given you the right search results.