A quasi-kernel of a directed graph is an independent vertex set from which every graph vertex is reachable by a directed graph path of length at most two. This convention directs paths away from the quasi-kernel. The reverse convention is obtained by reversing all directed edges (Ai et al. 2026).
The small quasi-kernel conjecture asserts that every source-free directed graph on 
vertices has a quasi-kernel of size at most 
. Source-free means that every graph
vertex has positive indegree. The large quasi-kernel
conjecture asserts that every directed graph has
a quasi-kernel whose closed out-neighborhood contains at least half its vertices.
This neighborhood consists of the quasi-kernel and all vertices
reached from it by one directed edge. Ai et al.
(2026) proved that these two universal conjectures are equivalent. Neither is
thereby proved. Their conventions allow opposite directed
edges but exclude graph loops and parallel directed
edges.
