Tournament Scores and Degree Constraints

Out-Degrees as Tournament Scores

A tournament represents a contest in which every pair of participants plays exactly once, with one participant winning each contest. Its directed edges record the winners, and the out-degree of a vertex counts its wins. The resulting score sequence is constrained: each contest contributes to exactly one score, and a group of vertices must have played a fixed number of contests among themselves. These observations give useful checks on score calculations and on proposed score lists.

All graphs in this tutorial are finite. A directed graph has directed edges, called arcs. For a vertex $v$, its out-degree $d^+(v)$ is the number of arcs whose tail is $v$, and its in-degree $d^-(v)$ is the number of arcs whose head is $v$.

Definition: A tournament is a directed graph with no loops such that, for every pair of distinct vertices $u,v$, exactly one of the arcs $(u,v)$ and $(v,u)$ is present. The score of $v$ is $d^+(v)$. The list of scores in a chosen vertex order is the labeled score vector. The scores arranged in nondecreasing order form the score sequence.

Thus the labeled vector retains which score belongs to which vertex, while the sorted sequence does not. Write the sorted sequence as $s_1\le s_2\le\cdots\le s_n$, where $n=|V|$. Repeated scores are allowed. A tournament on no vertices has an empty score sequence; the statements below include this case when their formulas allow it.

Total Scores and Basic Bounds

Theorem: In a tournament $T$ on $n$ vertices, the sum of the out-degrees is $n(n-1)/2$. Every vertex has score between $0$ and $n-1$, inclusive.

Proof. First suppose $n\ge 0$. Each pair of distinct vertices contributes exactly one arc, so the number of arcs is the number of such pairs, namely $n(n-1)/2$. Each arc has exactly one tail, and so contributes exactly one to the out-degree of that tail and zero to the other out-degrees. Therefore the sum of all out-degrees equals the number of arcs. A vertex has no loop and can have an arc directed outward to at most each of the other $n-1$ vertices; its score is also nonnegative. For $n=0$, there are no vertices or arcs and the sum is zero, as given by the formula. $\square$

The same reasoning gives a constraint for a specified group of vertices. It is stronger than merely bounding each individual score, because it accounts for contests within the group as well as contests against vertices outside it.

Theorem: Let $S$ be any subset of $k$ vertices in a tournament on $n$ vertices. Then $$ \binom{k}{2}\ \le\ \sum_{v\in S}d^+(v)\ \le\ \binom{k}{2}+k(n-k). $$

Proof. In the sum of scores over $S$, each arc with its tail in $S$ is counted once. Among arcs whose two endpoints lie in $S$, there is exactly one for every pair in $S$, so these contribute $\binom{k}{2}$. Arcs between $S$ and its complement contribute to the sum only when they point from $S$ to the complement. There are $k(n-k)$ pairs with one endpoint in each set, so the number of such outward arcs is between zero and $k(n-k)$, inclusive. Adding this range to the fixed internal contribution proves both inequalities. If $S$ is empty, both sides are zero; if $S=V$, there are no cross-pairs and both bounds equal the total number of arcs. $\square$

Taking $S$ to be the vertices with the $k$ smallest scores gives a convenient condition on the sorted sequence. Taking the $k$ largest gives an upper bound on their total.

\sum_{i=1}^{k}s_i\ge \binom{k}{2}, \qquad \sum_{i=n-k+1}^{n}s_i\le \binom{k}{2}+k(n-k).

These inequalities hold for every integer $k$ from $0$ to $n$. At $k=n$, either bound is the total-score identity. For other values of $k$, they express restrictions on portions of the score sequence. They are necessary conditions: any score sequence of a tournament must satisfy them. In using them here, we do not claim that a list passing a particular selection of these checks is realizable.

Calculating Scores from Arc Sets

Worked Example: A Transitive Tournament

Let $T$ have vertex set $V=\{1,2,3,4\}$ and arc set $A=\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\}$. Each pair appears once, so this is a tournament. Calculate its labeled score vector and sorted score sequence.

Vertex $1$ is the tail of $(1,2),(1,3),(1,4)$, giving $d^+(1)=3$. Vertex $2$ is the tail of $(2,3),(2,4)$, giving $d^+(2)=2$. Vertex $3$ is the tail of $(3,4)$, giving $d^+(3)=1$. No arc has tail $4$, giving $d^+(4)=0$. Thus the labeled vector in vertex order is $(3,2,1,0)$, and the sorted score sequence is $(0,1,2,3)$.

Check: The out-degree sum is $3+2+1+0=6$, and the pair-count formula gives $4(4-1)/2=6$. For the two smallest scores, the sum is $0+1=1$, equal to $\binom{2}{2}=1$. For the two largest, the sum is $2+3=5$, which is at most $\binom{2}{2}+2(4-2)=1+4=5$. Each score lies between $0$ and $4-1=3$, inclusive.

In this orientation, every arc points from a smaller label to a larger label. The scores decrease along the displayed vertex order, while sorting them gives the familiar increasing list from zero through $n-1$. This is a useful example, but other orientations can have ties or quite different score patterns.

Worked Example: A Tournament with Three Tied Scores

Let $T$ have vertex set $V=\{a,b,c,d\}$ and arc set $A=\{(a,b),(a,c),(a,d),(b,c),(d,b),(c,d)\}$. The six arcs represent the six pairs of distinct vertices, so this is a tournament.

Vertex $a$ has outgoing arcs to $b,c,d$, so $d^+(a)=3$. Vertex $b$ has the outgoing arc to $c$, so $d^+(b)=1$. Vertex $c$ has the outgoing arc to $d$, so $d^+(c)=1$. Vertex $d$ has the outgoing arc to $b$, so $d^+(d)=1$. The labeled vector in order $a,b,c,d$ is $(3,1,1,1)$; its sorted score sequence is $(1,1,1,3)$.

Check: The sum is $3+1+1+1=6$, while the number of arcs is $4(4-1)/2=6$. The sum of the three smallest scores is $1+1+1=3$, meeting the lower bound $\binom{3}{2}=3$. The sum of the three largest is also $1+1+3=5$, at most $\binom{3}{2}+3(4-3)=3+3=6$. The individual scores are all at least $0$ and at most $3$, as required.

Worked Example: A Regular Tournament

Let $T$ have vertex set $V=\{1,2,3,4,5\}$ and arc set $A=\{(1,2),(1,3),(2,3),(2,4),(3,4),(3,5),(4,5),(4,1),(5,1),(5,2)\}$. For each of the ten pairs, exactly one listed arc joins its vertices, so this is a tournament.

Counting tails gives $d^+(1)=2$, from $(1,2),(1,3)$; $d^+(2)=2$, from $(2,3),(2,4)$; $d^+(3)=2$, from $(3,4),(3,5)$; $d^+(4)=2$, from $(4,5),(4,1)$; and $d^+(5)=2$, from $(5,1),(5,2)$. The labeled vector and sorted score sequence are both $(2,2,2,2,2)$.

Check: The score sum is $2+2+2+2+2=10$, matching $5(5-1)/2=10$ arcs. For the three smallest scores, $2+2+2=6$, which is at least $\binom{3}{2}=3$. For the three largest, the sum $2+2+2=6$ is at most $\binom{3}{2}+3(5-3)=3+6=9$. Also, each score is between $0$ and $5-1=4$.

What the Constraints Can Catch

The total-score formula is a quick consistency check: if the out-degrees in a proposed tournament do not sum to the number of arcs, some arc has likely been omitted or counted with the wrong tail. The subset bounds can catch errors that the total alone will not. For instance, a proposed sorted list for a tournament on four vertices must have its two smallest entries summing to at least $\binom{2}{2}=1$. The list $(0,0,3,3)$ sums to $6$, which matches $4(4-1)/2=6$, but its two smallest entries sum to $0$, violating that required bound. It cannot be a tournament score sequence.

Common mistake: counting every contest twice. An arc has a tail and a head, but it contributes only to the out-degree of its tail. For the first example, summing the displayed out-degrees gives $3+2+1+0=6$, not $12$. The value $12$ would count each of the six arcs at both endpoints, incorrectly mixing out-degrees with a count of incident endpoints. A separate check is that the in-degree plus out-degree at each vertex is $n-1$: every other vertex is joined to it by exactly one arc, directed either inward or outward.

Score sequences compress a tournament’s local win counts into a single ordered list. The total and subset bounds provide immediate structural checks, while an explicit arc list lets us recover which vertices achieve each score. These tools do not describe the full orientation: different tournaments can share a score sequence.

Check Your Understanding

Use the definitions and bounds above to answer the following questions.

In a tournament on six vertices, what is the sum of all out-degrees?
Why must every individual score in a tournament on $n$ vertices lie between $0$ and $n-1$, inclusive?
For a set $S$ of three vertices in a tournament on seven vertices, state the lower and upper bounds on $\sum_{v\in S}d^+(v)$.
For the sorted score sequence $(1,1,2,2,4)$, check whether the sum of the two smallest entries satisfies the necessary lower bound.
Explain why a score sequence does not record which vertex has each score.

Tournament Scores and Degree Constraints

What You'll Learn