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
    Note that by requiring $S$ to be a set you are implicitly ruling out any rematches between the same pair of players.2012-05-21
  • 0
    Yes, precisely. It is desired that each player never plays more than once against another player. I should probably add that to the description; and the definition of S was 'weird' like that precisely to avoid rematches.2012-05-21
  • 1
    In graph-theoretic terms, you’re asking whether there is always an $m$-regular simple graph on $p$ vertices when $m and $mp$ is even.2012-05-21
  • 0
    Yes! That is indeed a much simpler way to ask the question, if the reader understands some graph theory. I will add this to the question as well.2012-05-21
  • 0
    This [table of counts of connected k-regular graphs on n vertices](http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html#CRG) seems to support your conjecture.2012-05-21
  • 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