# Landau's Theorem on tournaments

There is a Landau's theorem related to tournaments theory. Looks like the sequence $(0, 1, 3, 3, 3)$ satisfies all three conditions from the theorem, but it is not possible for 5 people to play tournament in such a way (if there are no ties). Did I miss something?

-

## migrated from mathematica.stackexchange.comOct 21 '12 at 22:49

This question came from our site for users of Mathematica.

Are you sure your question is related to Mathematica (TM) "the software"? –  belisarius Oct 21 '12 at 22:41
@belisarius Yes, here is a similar question on the same forum math.stackexchange.com/questions/145662/… –  Pavel Podlipensky Oct 21 '12 at 22:54

Player $A$ loses to everyone.

Player $B$ beats player $A$ and loses to everyone else.

Players $C$, $D$, and $E$ beat each other cyclically, like rock-paper-scissors.

-
I don't think C,D and E can form a cycle as no ties are allowed and each player plays only once with other. Here is a graph I'm trying to draw, but for the E there is no way to have 3 outbound edges without making a cycle with C or D: i49.tinypic.com/es0ls8.jpg –  Pavel Podlipensky Oct 21 '12 at 23:11
There is no requirement that the graph be acyclic. –  Rahul Oct 21 '12 at 23:16

Draw $K_5$, the complete graph on $5$ vertices, and assign directions to just enough edges to give one vertex ($A$ in the picture below) a score (outdegree) of $0$ and another ($B$ in the picture) a score of $1$.

At this point only the red edges have not been assigned orientations, and it’s clear that there are exactly two ways to orient them to gives vertices $C,D$, and $E$ scores of $3$: they must form a cycle, either $$C\to D\to E\to C$$ or $$C\to E\to E\to C\;.$$ Either works to give a tournament with the score sequence $\langle 0,1,3,3,3\rangle$.

-