Organizing a chess tournament

Consider that each chess player is the vertex of a graph and each game is an edge between them. We have to find how many graphs with $6$ vertices have exactly $3$ edges per vertex with $3$ distinct neighbors. This is the same as the number of graphs with $2$ edges per vertex because we could consider that edges are the games that are not played.

The only graphs with degree $2$ at each vertex are closed cycles. We either have one cycle of $6$ vertices or $2$ cycles of $3$ vertices. All the other cases create cycles of $1$ or $2$ vertices, which are not possible in this case because a players do not play against themselves, nor do they play twice against the same player.

Each ordering of $6$ vertices corresponds to a unique cycle. However, the reverse ordering and every circular permutation corresponds to the same cycle. So there are $\frac{6!}{2\cdot6} = 60$ cycles of $6$ vertices. To specify a pair of cycles of $3$ vertices you only need to choose $3$ vertices among $6$ . However, choosing the complement specifies the same pair of cycles. So there are ${6 \choose 3} / 2 = 10$ pairs of cycles of $3$ vertices. The final answer is thus $70$ .

Label the players from $1$ to $6$ Without loss of generality, assume that Player $1$ plays against Players $2$ , $3$ , and $4$ . There are $5\choose3 =10$ ways to choose the people who Player $1$ will play, and the other $9$ cases are analogous. We then multiply the total number of cases by $10$ .

Now we consider cases for the people Player $2$ will play with.

Case $1$ : Player $2$ players with Players $3$ and $4$

Now Players $5$ and $6$ has no one to play with yet, while both of them could not play with Player $1$ or $2$ since their games have already been filled. Hence they have to take all the remaining possible $3$ games. Thus Players $5$ and $6$ will both player against both players $3$ and $4$ . However, this is not possible, since player $3$ will end up playing $4$ games.

Case $2$ : Player $2$ plays one of Players $3$ and $4$ and one of Players $5$ and $6$

Without loss of generality, we assume that Player $2$ plays Player $3$ and Player $5$ . The other $3$ cases are analogous, so we just multiply the total number of ways for this case by $4$ .

Player $6$ does not have anyone to play with yet, and he is not allowed to play with Players $1$ or $2$ since they already have $3$ games arranged. Thus he has to play with Players $3$ , $4$ , and $5$ .

Player $5$ will play with Players $2$ and $6$ , but cannot play with Players $1$ and $3$ since they already have $3$ games arranged. Hence he must play with Player $4$ .

Thus it turns out that there is only one way for this arrangement. There are $4$ ways, considering the analogous configurations.

Case $3$ . Player $2$ plays with Players $5$ and $6$

Now we consider cases on whom Player $3$ will play with.

Case $3.1$ . Player $3$ plays with Player $4$ and one of Players $5$ or $6$ .

Without loss of generality, we assume that Player $3$ plays with Players $4$ and $5$ . We just account for the other analogous case by multiplying the number of ways for this subcase by $2$ .

Player $6$ cannot play with Players $1$ and $3$ . Thus, he must play with Players $2$ , $4$ , and $5$ . There are no other games that are left to match.

There is only $1$ way, so considering the other analogous case, there are $2$ ways for this subcase.

Case $3.2$ . Player $3$ plays with Players $5$ and $6$ .

Player $4$ cannot play with Players $2$ or $3$ since they already have $3$ games arranged.

Hence Player $4$ must play with Players $1$ , $5$ , and $6$ .

There are no other games to be arranged, so there is one way.

For Case $3$ , there are $3$ ways in all.

Adding up all the cases, there are $4+3=7$ ways if Player $1$ played Players $2$ , $3$ , and $4$ . Since there are $10$ ways to chose who Player $1$ will play with, there are $(7)(10)=\boxed{70}$ possibilities for the set of $9$ games to be played.

We can count in an organized fashion:

Case 1: P1 plays P2, P3, P4 (He can play any 3 of these 5, for a total of $\binom{5}{3}=10$ choices. P2 plays P1, P3, P5 (In this case, P2 plays one of the players than P1 has played. There are $2\times2=4$ choices, because P2 can play either P3 or P4 and either P5 or P6. P3 plays P1, P2, P6 (From this point forward, there is only one case for each one. P4 plays P1, P5, P6 P5 plays P2, P4, P6 P6 plays P3, P4, P5

There are $10\times4=40$ ways for this to happen in Case 1.

Case 2: P1 plays P2, P3, P4 (Still the same 10 ways) P2 plays P1, P5, P6 (There is only one way; P2 plays the people P1 did not play) P3 plays P1, P4, P5 (3 ways, because P3 plays 2 of the 3 other people {4,5,6}) P4 plays P1, P3, P6 (From this point on, only 1 case for each) P5 plays P2, P3, P6 P6 plays P2, P4, P5

This case contains $10\times3=30$ ways.

So, in total, there are $30+40=\boxed{70}$ different ways that these matches can be played.

(Note that P2 cannot play P1, P3, and P4, for then P5 and P6 will not have enough games)