Determined those positive integers $n$ such that there exists a regular tournament of orders $n$

488 Views Asked by At

Determined those positive integers $n$ such that there exists a regular tournament of orders $n$

I know that a tournament is a oriented complete graph, and every complete graph $K_n $ has $ \left( \begin{array}{ccc} n \\ 2 \\ \end{array} \right) $ edges.

If the graph is $r$-regular then every vertex has degree $r$, by the first theorem of graph theory, the sum degree of all vertices is twice the size, so

$$nr= 2 \left( \begin{array}{ccc} n \\ 2 \\ \end{array} \right) $$ $$nr=(n-1)n$$

$$n=r+1$$

but the book say $n=2r+1$. Did I do something wrong or there is a typo in the book?

2

There are 2 best solutions below

0
On BEST ANSWER

You have the right idea, but you need to be a bit careful. I believe you are referring to the result often known as the handshaking lemma, which says that in an undirected graph, $\sum_{v\in V(G)}\deg(v)=2|E(G)|$. The reason the $2$ is on the right is that, in the sum on the left, each edge is being counted twice (once for each of its endpoints). You can apply a similar idea to a directed graph, say by counting the total of the out-degrees (number of edges leaving a vertex) over all vertices, but now you're not counting each edge twice anymore. So the analogous result for directed graphs is that $\sum_{v\in V(G)}\textrm{outdeg}(v) = |E(G)|$. Applying this to your situation, you get the equality $rn={n\choose 2}$, which leads to $n=2r+1$.

You can also see this just by thinking at what must happen at each vertex. Every vertex has degree $n-1$ and for the tournament to be regular, half those edges must be entering the vertex, and half leaving. Hence you better have $2r=n-1$.

But note that this is only a necessary condition for an $r$-regular tournament to exist. You also need to show that if $n=2r+1$, then there actually exists an $r$-regular tournament.

0
On

The regular in regular tournament is a little different from the regular in regular (undirected) graph: a tournament is regular if the in-degree of every vertex is the same as the out-degree. The $r$ in your book is apparently the in-degree (or out-degree) of each vertex, so it’s half the total degree. Each edge contributes just $1$ to the sum of the in-degrees, so the correct equation is

$$nr=\binom{n}2\;,$$

and hence $n=2r+1$.

It’s also true that there is a regular tournament of every odd order: see this question and answer.