25.4. 25.4 Existence of an -tournament with prescribed score sequence

For the -tournament Moon [ 184 ] proved the following extension of Landau's theorem.

Theorem 25.4 (Moon [ 184 ], Kemnitz, Dulff [ 144 ]) A nondecreasing sequence of nonnegative integers is the score sequence of an -tournament if and only if

for , with equality for .

Proof. See [ 144 ], [ 184 ].

Later Kemnitz and Dulff [ 144 ] reproved this theorem.

The proof of Kemnitz and Dulff is based on the following lemma, which is an extension of a lemma due to Thomassen [ 270 ].

Lemma 25.5 (Thomassen [ 270 ]) Let be a vertex of maximum score in an -tournament . If is a vertex of different from , then there is a directed path from to of length at most 2.

Proof. ([ 144 ]) Let be all vertices of such that . If then for the length of path . Otherwise if there exists a vertex , such that then . If for all then there are arcs which implies , a contradiction to the assumption that has maximum score.

Proof of Theorem 25.4. The necessity of condition (25.7) is obvious since there are arcs among any vertices and there are arcs among all vertices.

To prove the sufficiency of (25.7) we assume that the sequence is a counterexample to the theorem with minimum and smallest with that choice of . Suppose first that there exists an integer , such that

Because the minimality of , the sequence is the score sequence of some -tournament .

Consider the sequence defined by , . Because of by assumption it follows that

which implies . Since is nondecreasing also is a nondecreasing sequence of nonnegative integers.

For each with it holds that

with equality for since by assumption

Therefore the sequence fulfils condition (25.8), by the minimality of , is the score sequence of some -tournament . By forming the disjoint union of and we obtain a -tournament with score sequence in contradiction to the assumption that is counterexample.

Now we consider the case when the inequality in condition (25.8) is strict for each , . This implies in particular .

The sequence is a nondecreasing sequence of nonnegative integers which fulfils condition (25.8). Because of the minimality of , is the score sequence of some -tournament . Let denote a vertex of with score and a vertex of with score . Since has maximum score in there is a directed path from to of length at most 2 according to Lemma 25.5. By reversing the arcs of the path we obtain an -tournament with score sequence . This contradiction completes the proof.