Prove that there exist regular tournament of every odd order but there is no regular tournament of even order.

Question

Prove that there exist regular tournament of every odd order but there is no regular tournament of even order.

Here is what I got so far.

Let $T$ be our regular tournament of order $n$. Since $T$ is regular tournament $id(u)=od(u)$ for every $u \in V(T)$. Since $t$ is a tournament $deg(u)=n-1$, thus $id(u)=id(u)=\frac{n-1}{2}$.

If $n$ is even then $\frac{n-1}{2}$ isn't a whole number, which can't be degree of $u$, so there is no egular tournament of even order.

For $n$ is odd, $od(u)=id(u)= k$ for $n=2k+1$. But i'm not sure how to prove this for every odd number. By induction ?

Answer 1

Yes, induction works. Suppose you have a regular tournament of order $n=2k+1$. The following procedure produces a tournament of order $n+2$.

• Add two new vertices $v$ and $v'$.
• For $k$ of the old vertices $w$, add edges $w \to v$ and $v' \to w$ so that $id(w)=od(w)$ still holds.
• For the remaining $k+1$ old vertices $w$, add edges $v \to w$ and $w \to v'$ so that $id(w)=od(w)$ still holds.
• Then $od(v)-id(v)=1$ and $od(v')-id(v')=-1$. Add the edge $v'\to v$ to finish.