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

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 ?

• For those wondering: a tournament is a directed complete graph. Sep 20, 2014 at 13:32
• yes, it's an oriented completed graph. Sep 20, 2014 at 13:32

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.
• you already have edges $w \to v$ , if you add $v \to w$, you will have symmetric arcs, and tournament doesn't contain symmetric arcs, right? Sep 20, 2014 at 14:34
• @DianeVanderwaif The $w$ in the second bullet and the third bullet are different. I partitioned the set of $2k+1$ vertices into two subsets of size $k$ and $k+1$. Sep 20, 2014 at 15:11