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?
Landau's Theorem on tournaments
1
$\begingroup$
graph-theory
-
0@belisarius Yes, here is a similar question on the same forum http://math.stackexchange.com/questions/145662/sufficient-condition-for-tournament-score-sequences – 2012-10-21
2 Answers
4
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.
-
0There is no requirement that the graph be acyclic. – 2012-10-21
1
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$.