# Sufficient Condition for Tournament Score Sequences

There are $N$ players, and each player plays a match with everyone else exactly once. There is no tie. Each player's score is the number of matches he wins. What constraints can their scores be?

Is every system of scores in which all scores are between $0$ and $N-1$, the sum of scores equal to $N(N-1)/2$, and at most one $0$ score and at most one $N-1$ score achievable in such a matching setting, or there are actually more constraints? If it is the former, how to prove? If it is the latter, what other constraints will sufficient guarantee the set of scores be valid?

For example, for $4$ players, the set of scores cannot be $(3,3,0,0)$ since there can only be one player who wins 3 games.

-

The structures that you are looking at are known as tournaments in graph theory. The number of distinct score sequences for a given number of vertices is in the OEIS.

Your conditions are all necessary but not quite sufficient. The theorem that you are looking for is called Landau's Theorem:

A given non-decreasing sequence of non-negative integers $v_1\leq v_2\leq v_3\cdots\leq v_n$ is a score sequence of a tournament if and only if for each integer $k$ with $1\leq k\leq n$$\sum_{i=1}^kv_i\geq\binom{k}{2}$$ with equality when$k=n\$.

All of the graph theory books that I own contain proofs of this theorem, and there are many different proofs available online. Finally, note that there may be many non-isomorphic tournaments that share a single score sequence.

-
The second proof in the paper available here is especially elementary. –  Brian M. Scott May 16 '12 at 2:45