Two Conditions for a Kernel
In an undirected graph, an independent set has no edges between its members. In a digraph, that condition still concerns the pairs of selected vertices, but a second condition must respect the direction of arcs: every vertex left outside the set must have an arc going from itself into the set. Together these requirements define a kernel. The outgoing direction is essential; an arc from a selected vertex to an outside vertex does not absorb that outside vertex.
Throughout, a digraph is finite and has no loops or repeated arcs, but it may contain both arcs \(u\to v\) and \(v\to u\). Write \(V(D)\) for its vertex set and \(A(D)\) for its arc set. For a vertex \(v\), its out-neighborhood is \(N^+(v)=\{w:(v,w)\in A(D)\}\). A sink is a vertex with no outgoing arcs, so \(N^+(v)=\varnothing\).
- Independence: there is no arc between any two distinct vertices of \(K\), in either direction.
- Absorption: for every vertex \(v\in V(D)\setminus K\), there is a vertex \(k\in K\) such that \(v\to k\) is an arc.
Independence concerns arcs whose two endpoints are both selected. Absorption concerns arcs that start at an unselected vertex and end at a selected one. In particular, it is not enough that each outside vertex is adjacent to the set in some direction: the arc must point out of that vertex and into \(K\).
The empty set is a kernel of the digraph with no vertices: both conditions hold because there are no vertices or pairs to check. If the digraph has at least one vertex, the empty set is not a kernel, since no outside vertex has an arc into it. For a nonempty edgeless digraph, the whole vertex set is a kernel: it is independent, and there are no outside vertices for which absorption must be checked.
A Reliable Way to Check a Proposed Set
For a particular set \(K\), check the two conditions separately. First inspect every pair of vertices in \(K\): if even one arc runs between a pair, \(K\) fails independence. If it passes, inspect every vertex outside \(K\): it must have at least one outgoing arc whose endpoint lies in \(K\). One successful arc is enough for that outside vertex; arcs to other outside vertices do not count toward its absorption.
Confirm that no arc has both its tail and its head in \(K\).
For each \(v\notin K\), find at least one arc \(v\to k\) with \(k\in K\).
If either condition fails, the set is not a kernel, regardless of whether it passes the other.
Worked Example: A Kernel in a Transitive Orientation
Let \(D\) have vertex set \(V(D)=\{1,2,3\}\) and arc set \(A(D)=\{(1,2),(1,3),(2,3)\}\). Test \(K=\{3\}\).
For independence, \(K\) has only one vertex, so there is no pair of distinct selected vertices and no arc within \(K\). The vertices outside \(K\) are \(1\) and \(2\). Vertex \(1\) has the arc \(1\to3\), and vertex \(2\) has the arc \(2\to3\). Thus each outside vertex has an outgoing arc into \(K\), so \(K=\{3\}\) is a kernel.
Check: the only arcs are \(1\to2\), \(1\to3\), and \(2\to3\). None has both endpoints in \(\{3\}\); the arcs \(1\to3\) and \(2\to3\) provide absorption for the two outside vertices.
Why Direction Changes the Answer
Worked Example: A Directed 3-Cycle Has No Kernel
Let \(D\) have vertex set \(V(D)=\{1,2,3\}\) and arc set \(A(D)=\{(1,2),(2,3),(3,1)\}\). We check every possible size of \(K\).
If \(K\) contains at least two vertices, it is not independent: every pair of distinct vertices in this digraph has an arc between them. If \(K=\varnothing\), it fails absorption because each of the three vertices is outside \(K\) and there is no vertex in \(K\) to receive an arc. It remains to test the three singleton sets.
For \(K=\{1\}\), vertex \(3\) has the arc \(3\to1\), but vertex \(2\) has only the outgoing arc \(2\to3\), which ends outside \(K\). So \(\{1\}\) fails absorption. For \(K=\{2\}\), vertex \(1\) is absorbed by \(1\to2\), but vertex \(3\) has only \(3\to1\), so \(\{2\}\) fails. For \(K=\{3\}\), vertex \(2\) is absorbed by \(2\to3\), but vertex \(1\) has only \(1\to2\), so \(\{3\}\) fails.
These cases cover all subsets: the empty set, three singleton sets, and sets of size at least two. None is a kernel, so this digraph has no kernel.
Check: each singleton is independent, but for each choice there is an outside vertex whose only outgoing arc points to another outside vertex. The failure is absorption, not independence.
Two Consequences of the Definition
Proof. Let \(K\) be a kernel, and form the underlying undirected graph by joining two distinct vertices whenever at least one of the two possible arcs between them is present. Independence of \(K\) in the digraph says there are no arcs between its members in either direction, so \(K\) is independent in this underlying graph. To prove maximality, take any \(v\in V(D)\setminus K\). Since \(K\) is a kernel, absorption gives some \(k\in K\) with \(v\to k\). Therefore \(v\) and \(k\) are adjacent in the underlying graph. Adding \(v\) to \(K\) would create an edge within the set, so it would not preserve independence. This applies to every vertex outside \(K\); hence no vertex can be added while keeping the set independent, and \(K\) is maximal independent. \(\square\)
The converse does not hold in general. Maximal independence only guarantees that an outside vertex is adjacent to the set; it does not guarantee that the connecting arc points from that vertex into the set. For a kernel, the direction of every required absorbing arc matters.
Worked Example: Maximal Independent Does Not Mean Kernel
Let \(D\) have \(V(D)=\{a,b\}\) and \(A(D)=\{(a,b)\}\). In the underlying undirected graph, \(\{a\}\) is independent. It is maximal independent because the only larger set is \(\{a,b\}\), and that set contains the edge corresponding to the arc \(a\to b\).
Nevertheless, \(\{a\}\) is not a kernel. Its outside vertex \(b\) has no outgoing arc to \(a\); the only arc points the other way, from \(a\) to \(b\). By contrast, \(\{b\}\) is a kernel: it is independent, and the outside vertex \(a\) has the arc \(a\to b\).
Check: both singleton sets are maximal independent in the underlying graph. Only \(\{b\}\) satisfies absorption, because only the arc directed from the outside vertex into the chosen set can provide it.
Proof. Let \(s\) be a sink, and suppose \(K\) is a kernel. If \(s\notin K\), absorption would require an arc \(s\to k\) for some \(k\in K\). But \(s\) has no outgoing arcs, by the definition of a sink. This contradiction shows that \(s\in K\). If the digraph has no kernel, the statement that every kernel contains \(s\) is vacuously true, since there is no kernel that could violate it. \(\square\)
This condition can help reject a proposed set immediately: if it omits a sink, it cannot be a kernel. It does not, by itself, guarantee that a set containing all sinks is a kernel; independence and absorption still have to be checked. In particular, if a sink has an incoming arc from another vertex, that arc prevents the two endpoints from both belonging to a kernel. Independence forbids arcs between selected vertices in either direction; a reciprocal arc is not required for this conflict.
Worked Example: A Sink Constrains the Set
Let \(D\) have \(V(D)=\{x,y,s\}\) and \(A(D)=\{(x,y),(x,s),(y,s)\}\). Vertex \(s\) is a sink, since none of the listed arcs starts at \(s\). The proposition requires \(s\) to belong to every kernel.
Test \(K=\{s\}\). It is independent because it is a singleton. The outside vertices are \(x\) and \(y\). Both have arcs into \(s\): \(x\to s\) and \(y\to s\). Hence \(\{s\}\) is a kernel.
Now consider \(\{y,s\}\). It cannot be a kernel, because the arc \(y\to s\) has both endpoints in the proposed set, violating independence. This remains a conflict even though there is no arc \(s\to y\). The single arc \(y\to s\) is enough to forbid selecting both endpoints.
Check: the only vertices outside \(\{s\}\) are \(x\) and \(y\), and each has a listed outgoing arc to \(s\). For \(\{y,s\}\), the listed arc \(y\to s\) directly witnesses failure of independence.
Common Pitfall: Reversing Absorption
A frequent error is to treat an arc from the selected set to an outside vertex as if it absorbed that vertex. For the two-vertex digraph with \(V(D)=\{a,b\}\) and \(A(D)=\{(a,b)\}\), the incorrect calculation is: “For \(K=\{a\}\), the outside vertex \(b\) is joined to \(a\) by the arc \(a\to b\), so it is absorbed.” This uses the wrong direction. The required arc must have tail \(b\) and head in \(K\); there is no arc \(b\to a\), so \(\{a\}\) is not a kernel. The corrected check is that \(K=\{b\}\) is independent and the outside vertex \(a\) is absorbed by \(a\to b\).
Keep the two tests distinct. An arc between two selected vertices violates independence, regardless of its direction. For an outside vertex, an arc to a selected vertex helps with absorption, while an arc from a selected vertex to it does not. A set must pass both tests to be a kernel.
Why Kernels Matter
A kernel identifies a group of mutually nonadjacent vertices that can be reached in one directed step from every vertex outside the group. This makes the definition useful when directed arcs represent permitted moves, choices, or influence: selected vertices do not conflict directly with one another, and every unselected vertex has a direct move into the selected set.
The definition alone does not promise that every digraph has a kernel. The directed 3-cycle above is a small example with none. Nor does it promise uniqueness: if \(D\) has vertices \(\{u,v\}\) and arcs \((u,v)\) and \((v,u)\), then each singleton is a kernel. For \(K=\{u\}\), vertex \(v\) has \(v\to u\); for \(K=\{v\}\), vertex \(u\) has \(u\to v\). Each singleton is independent, and these are the only outside-vertex checks in their respective cases.
Check Your Understanding
For each question, keep independence and outgoing absorption as separate checks.
- Let \(V(D)=\{p,q,r\}\) and \(A(D)=\{(p,q),(r,q)\}\). Is \(\{q\}\) a kernel? Give the independence and absorption checks.
- In a digraph with \(V(D)=\{u,v\}\) and \(A(D)=\{(u,v)\}\), explain why \(\{u\}\) is maximal independent but is not a kernel.
- Prove directly from the definition that a nonempty edgeless digraph has exactly one kernel.
- Can two vertices joined by a single arc both belong to a kernel? Explain why or why not.
- What does the sink proposition tell you about a proposed set that omits a sink? Does including every sink suffice to establish that the set is a kernel?