1
$\begingroup$

Possible Duplicate:
How to construct a k-regular graph?

A match can only be played by exactly two different players. I would've thought this was easier. Simple combinatorics show that the number of matches played would have to be $\frac{1}{2}p\cdot m$ so that either $p$ or $m$ must be even. But is that enough? If either $p$ or $m$ is even (and of course, $m \lt p$ ), does that guarantee I can arrange matches between different players such that each of the $p$ players plays exactly $m$ different matches (that is, there are no rematches)? I will rephrase the question more rigorously:

Let $p, m \in \mathbb N$. Define $I_p = \{ n \in \mathbb N ; n \leq p \} = \{1, 2, ..., p\} \text{ }$ to be the set of players and

$\begin{eqnarray*} (I_p, 2) &=& \{ P\subset I_p ; |P|=2 \}\\ &=&\{\{a,b\} \subset I_p; a\neq b\} \end{eqnarray*}$ the set of all subsets of $I_p$ with two elements to be the set of matches between players.

We will say a set $S \subset (I_p, 2)$ is a valid matchup of $m$ matches per each of $p$ players if $\begin{eqnarray*} f:&I_p& \rightarrow \mathbb N \\ &n&\mapsto |\text{ }\{\text{ }\{n,a\} \in S\ \text{ }\}\text{ }| \end{eqnarray*}$

is the constant function $f \equiv m\text{ }.$ For which choice of $p, m$ is there a valid matchup of $m$ matches per each of $p$ players?

In terms of graph theory, it is equivalent to asking: for which natural numbers $p, m$ is there a $m$-regular simple graph on $p$ vertices?

  • 0
    @GerryMyerson That does appear to answer the question. If both $p, m$ are odd, then it is clear no such graph exists. On the other hand, the construction to which you refer ensures that if either $p$ or $m$ are even, then one such graph exists. The fact that $m \lt p$ also guarantees that the resulting graph is simple, and we are done, I guess.2012-05-21

0 Answers 0