1
$\begingroup$

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 ?

$\endgroup$
2
  • $\begingroup$ For those wondering: a tournament is a directed complete graph. $\endgroup$
    – angryavian
    Sep 20, 2014 at 13:32
  • $\begingroup$ yes, it's an oriented completed graph. $\endgroup$ Sep 20, 2014 at 13:32

1 Answer 1

2
$\begingroup$

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.
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Sep 20, 2014 at 14:34
  • $\begingroup$ @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$. $\endgroup$
    – angryavian
    Sep 20, 2014 at 15:11
  • $\begingroup$ oh, I see, thanks $\endgroup$ Sep 20, 2014 at 22:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .