Tournaments and Their Basic Structure

From Complete Graphs to Tournaments

A tournament is a directed model of pairwise comparisons: for every two distinct participants, exactly one is declared to defeat, precede, or point toward the other. The word “tournament” does not imply that the directions come from a consistent overall ranking. Its basic structure is determined by a simple rule for each pair of vertices, and that rule gives an exact count of the arcs and a useful degree identity.

Throughout, a digraph is finite and has no loops or multiple arcs. An arc from $u$ to $v$ is written $(u,v)$, or $u\to v$. The out-degree $d^+(v)$ of a vertex $v$ is the number of arcs leaving $v$; its in-degree $d^-(v)$ is the number entering $v$. We write $V(T)$ for the vertex set and $A(T)$ for the arc set of a digraph $T$.

Definition: A tournament $T$ is a digraph obtained by orienting every edge of a complete graph: for each pair of distinct vertices $u,v$, exactly one of $u\to v$ and $v\to u$ is an arc of $T$. There are no loops, and there is not an arc in both directions between a pair.

Thus an orientation chooses one direction for each undirected edge of the complete graph. It neither deletes a pair nor assigns both directions to it. A tournament on $n$ vertices has one arc for every unordered pair of distinct vertices. We allow $n=0$ as well as positive $n$; the definition then applies vacuously to the empty vertex set.

Counting the Arcs

Theorem: If a tournament $T$ has $n$ vertices, then $$ |A(T)|=\frac{n(n-1)}{2}. $$

Proof. The unordered pairs of distinct vertices of $T$ are exactly the edges of the complete graph on $n$ vertices. There are $\binom{n}{2}=n(n-1)/2$ such pairs. By the definition of a tournament, each pair contributes exactly one arc, so the number of arcs equals the number of pairs. When $n=0$, there are no pairs and the formula gives $0(0-1)/2=0$, as required. $\square$

The count is about unordered pairs, not ordered pairs. For example, the two ordered pairs $(u,v)$ and $(v,u)$ represent the two possible directions for one pair; a tournament includes exactly one of them. This distinction is important both when writing the arc set and when checking a proposed count.

Worked Example: Listing Every Arc on Four Vertices

Let $T$ be the tournament with $V(T)=\{1,2,3,4\}$ and $A(T)=\{(1,2),(1,3),(2,3),(2,4),(3,4),(4,1)\}$. Equivalently, its arcs are $1\to2$, $1\to3$, $2\to3$, $2\to4$, $3\to4$, and $4\to1$.

First check that every unordered pair appears once. The six pairs are $12,13,14,23,24,34$; their directions in the list are, respectively, $1\to2$, $1\to3$, $4\to1$, $2\to3$, $2\to4$, and $3\to4$. Hence the list defines a tournament. The formula gives $4(4-1)/2=4\cdot3/2=6$ arcs, agreeing with the list.

Now count outgoing and incoming arcs vertex by vertex. Vertex $1$ sends arcs to $2,3$, so $d^+(1)=2$, and receives the arc from $4$, so $d^-(1)=1$. Vertex $2$ sends arcs to $3,4$ and receives the arc from $1$, giving $d^+(2)=2$, $d^-(2)=1$. Vertex $3$ sends an arc only to $4$ and receives arcs from $1,2$, giving $d^+(3)=1$, $d^-(3)=2$. Vertex $4$ sends an arc to $1$ and receives arcs from $2,3$, giving $d^+(4)=1$, $d^-(4)=2$.

Check: The out-degree total is $2+2+1+1=6$, and the in-degree total is $1+1+2+2=6$. Both totals equal the six listed arcs.

How Each Pair Contributes to the Degrees

For any vertex $v$, each of the other $n-1$ vertices forms exactly one pair with $v$. The arc for that pair either leaves $v$ or enters $v$, and cannot do both. Therefore its contribution is counted exactly once in $d^+(v)+d^-(v)$.

Theorem: In a tournament $T$ on $n$ vertices, every vertex $v$ satisfies $$ d^+(v)+d^-(v)=n-1. $$ Moreover, $$ \sum_{v\in V(T)}d^+(v)=\sum_{v\in V(T)}d^-(v)=|A(T)|=\frac{n(n-1)}{2}. $$

Proof. Fix a vertex $v$. There are $n-1$ other vertices. For each such vertex $u$, exactly one of $v\to u$ and $u\to v$ is present. The first contributes one to $d^+(v)$, and the second contributes one to $d^-(v)$. Thus each of the $n-1$ pairs contributes one to their sum, proving $d^+(v)+d^-(v)=n-1$.

For the sum of out-degrees, count the arcs by their tails: each arc has exactly one tail, and contributes one to the out-degree of that tail. Hence $\sum_{v\in V(T)}d^+(v)=|A(T)|$. Counting instead by heads gives $\sum_{v\in V(T)}d^-(v)=|A(T)|$. The arc-counting theorem gives $|A(T)|=n(n-1)/2$, proving both equalities. If $n=0$, all three sums and the arc count are empty sums or zero, so the statements hold in that case too. $\square$

The first identity is local: it applies separately to each vertex. The two sum identities are global: they count the same arcs in two different ways. Together they provide quick checks on a written tournament or a degree calculation.

Worked Example: A Five-Vertex Tournament

Define $T$ by $V(T)=\{1,2,3,4,5\}$ and $A(T)=\{(1,2),(1,3),(2,3),(2,4),(3,4),(3,5),(4,5),(4,1),(5,1),(5,2)\}$. In arrow notation these are $1\to2,1\to3,2\to3,2\to4,3\to4,3\to5,4\to5,4\to1,5\to1,5\to2$.

There are $\binom{5}{2}=5\cdot4/2=10$ unordered pairs. The displayed directions cover $12,13,14,23,24,25,34,35,45,15$ once each: the directions are $1\to2$, $1\to3$, $4\to1$, $2\to3$, $2\to4$, $5\to2$, $3\to4$, $3\to5$, $4\to5$, and $5\to1$, respectively. So the arc list contains exactly one direction for every pair.

Counting from the arc list, vertex $1$ sends arcs to $2,3$ and receives arcs from $4,5$; thus $d^+(1)=2$, $d^-(1)=2$. Vertex $2$ sends arcs to $3,4$ and receives arcs from $1,5$, so its two degrees are $2,2$. Vertex $3$ sends arcs to $4,5$ and receives arcs from $1,2$, also giving $2,2$. Vertex $4$ sends arcs to $1,5$ and receives arcs from $2,3$, again giving $2,2$. Vertex $5$ sends arcs to $1,2$ and receives arcs from $3,4$, again giving $2,2$.

Check: For each vertex, $d^+(v)+d^-(v)=2+2=4=5-1$. The total out-degree is $2+2+2+2+2=10$, as is the total in-degree, and the arc formula gives $5(5-1)/2=5\cdot4/2=10$.

Reversing a Direction

Changing the direction of one arc preserves the tournament condition: the same pair is still represented by exactly one arc. The arc count is therefore unchanged. Only the degree counts at the two endpoints change; the tail loses one outgoing arc and gains one incoming arc, while the head gains one outgoing arc and loses one incoming arc.

Worked Example: Reversing One Arc

Start with the four-vertex tournament from the first example, and reverse $1\to3$ to $3\to1$. The new vertex set is still $V(T)=\{1,2,3,4\}$, and the new arc set is $A(T)=\{(1,2),(3,1),(2,3),(2,4),(3,4),(4,1)\}$. The other five directions have not changed.

Before reversal, the degree pairs $(d^+(v),d^-(v))$ for $1,2,3,4$ were $(2,1),(2,1),(1,2),(1,2)$. Reversing $1\to3$ removes one outgoing arc from $1$ and one incoming arc to $3$, then adds one incoming arc to $1$ and one outgoing arc from $3$. The new pairs are therefore $(1,2),(2,1),(2,1),(1,2)$. Directly from the new list: $1$ sends only to $2$ and receives from $3,4$; $2$ sends to $3,4$ and receives from $1$; $3$ sends to $1,4$ and receives from $2$; $4$ sends to $1$ and receives from $2,3$.

Check: There are still six arcs, one for each of the $4\cdot3/2=6$ pairs. The out-degree total is $1+2+2+1=6$, and the in-degree total is $2+1+1+2=6$. Each vertex’s two degrees add to $3=4-1$.

Common Pitfall: Counting Ordered Pairs

A common mistake is to count $n(n-1)$ possible ordered pairs and use that as the number of arcs. That counts both possible directions for every pair, even though a tournament includes only one. For the five-vertex example, the incorrect calculation gives $5(5-1)=20$ arcs. The correction is to count the ten unordered pairs, or divide the ordered-pair count by two: $5(4)/2=10$. The same care is needed when checking directions: listing both $u\to v$ and $v\to u$ violates the tournament definition, even though it represents only one unordered pair.

These basic counts are useful when checking data about pairwise comparisons, checking a proposed arc list, or confirming degree calculations. The tests are simple but effective: every pair must appear once, the total number of arcs must be $n(n-1)/2$, and each vertex’s in-degree plus out-degree must be $n-1$. Passing these numerical checks is necessary, though the pair-by-pair definition is what verifies that a particular arc list is a tournament.

Check Your Understanding

For each question, use the tournament definition and show the relevant pair or degree count.

How many arcs does a tournament on seven vertices have?
In a tournament on six vertices, if a vertex has out-degree $4$, what is its in-degree?
For the arc set $\{(a,b),(b,c),(c,a)\}$ on $\{a,b,c\}$, check that every pair has exactly one direction and find all in-degrees and out-degrees.
Explain why a digraph on four vertices with seven arcs cannot be a tournament.
If the direction of one arc in a tournament is reversed, which vertices’ in-degrees and out-degrees change, and by how much?