Kernels in Tournaments

Kernels and Sinks in a Tournament

In a tournament, every pair of distinct vertices is joined by exactly one directed edge. This leaves little room for an independent set: two distinct vertices cannot both belong to it. As a result, deciding whether a tournament has a kernel comes down to a single question about edge directions: is there a vertex to which every other vertex points?

Throughout, a directed graph has no loops or multiple arcs. A tournament \(T=(V,E)\) is a directed graph in which, for every two distinct vertices \(u,v\in V\), exactly one of \(u\to v\) and \(v\to u\) is an arc. We write \(u\to v\) for the arc \((u,v)\in E\). The tournament may have no vertices unless otherwise specified.

In the absorption condition, the direction matters: a vertex outside the kernel must point to a kernel vertex. Thus a sink, not a source, is the natural candidate for a one-vertex kernel. If a tournament has no vertices, the empty set is a kernel: it is independent, and there are no outside vertices for which absorption must be checked. We will state the main characterization for nonempty tournaments and return to this exception below.

Why a Tournament Kernel Has at Most One Vertex

Proof. Suppose an independent set contained two distinct vertices \(u\) and \(v\). By the definition of a tournament, exactly one of \(u\to v\) and \(v\to u\) is an arc. Either arc is an arc between two vertices of the set, contradicting independence. Therefore an independent set has at most one vertex. \(\square\)

So a kernel in a nonempty tournament cannot use two or more vertices. It also cannot be empty: if \(V\ne\varnothing\) and \(K=\varnothing\), choose \(v\in V\). There is no \(k\in K\) with \(v\to k\), so the absorption condition fails. A kernel in a nonempty tournament, if one exists, must therefore be a singleton.

The Characterization

Proof. First suppose the nonempty tournament \(T=(V,E)\) has a kernel \(K\). By the lemma, \(K\) has at most one vertex. It is not empty, because the absorption condition would fail for any vertex of the nonempty set \(V\). Hence \(K=\{s\}\) for some \(s\in V\). For each \(v\in V\setminus\{s\}\), absorption requires \(v\to s\). The tournament has exactly one direction on the pair \(v,s\), so \(s\to v\) is not an arc. This holds for every other vertex \(v\), which means \(s\) has no outgoing arcs and is a sink.

Conversely, suppose \(s\in V\) is a sink. The singleton \(K=\{s\}\) is independent. For each \(v\in V\setminus\{s\}\), the tournament has exactly one arc between \(v\) and \(s\); since \(s\) has no outgoing arc, that arc must be \(v\to s\). Thus \(K\) absorbs every vertex outside it and is a kernel.

Finally, there cannot be two sinks. If \(s\) and \(t\) were distinct sinks, exactly one of \(s\to t\) and \(t\to s\) would be an arc. Its tail would have an outgoing arc, contradicting that it is a sink. Hence the sink, and therefore the kernel, is unique. \(\square\)

The theorem gives a direct way to decide the question: inspect the outgoing arcs of the vertices. If one vertex has no outgoing arcs, the kernel is exactly its singleton. If every vertex has at least one outgoing arc, there is no kernel. This is a test for a sink, not a search over all subsets of vertices.

The Empty Tournament and the Scope of the Result

The nonempty hypothesis in the theorem is necessary if “sink” means a vertex with no outgoing arcs. In the empty tournament, \(V=\varnothing\), the only subset is \(K=\varnothing\). It is independent, and the absorption condition holds because there are no vertices outside \(K\). Thus the empty tournament has a kernel but has no sink, since it has no vertices at all.

For every nonempty tournament, the characterization applies without further assumptions, including a tournament with just one vertex. In that case the only vertex has no outgoing arcs, so it is a sink; its singleton is independent and there are no outside vertices to absorb. The one-vertex tournament therefore has a kernel.

Common Pitfall: Reversing the Direction

A frequent error is to select a source, a vertex with no incoming arcs, instead of a sink. For the transitive tournament in the first example, vertex \(a\) is a source: it has no incoming arcs. But \(\{a\}\) is not a kernel. The outgoing arcs \(a\to b,a\to c,a\to d\) show that none of \(b,c,d\) points to \(a\), so the absorption condition fails for all three outside vertices. The correct candidate is \(d\), with arcs directed toward it from every other vertex.

Another tempting but invalid step is to treat any independent set as a possible multi-vertex kernel. In a tournament, two distinct vertices always have an arc between them, so no independent set can have size two. The right test is therefore not to search through large subsets: rule out the empty set when the tournament is nonempty, then check whether a singleton is a sink.

This special behavior is useful precisely because the general kernel conditions collapse to a simple structural test. In an arbitrary directed graph, an independent set may contain several vertices, and each outside vertex must be checked for an arc to at least one of them. In a tournament, the orientation of every pair forces independence to restrict the candidate to one vertex; absorption then says exactly that this vertex is a sink.