Weighted Half-Coverage by Quasi-Kernels in Oriented Graphs Whose Non-Neighborhoods Have Kernels
medium tier2026-11-05OP-337reviewed by Claude Code中文版
Abstract
The Small Quasi-kernel Conjecture asks whether every finite source-free digraph has a quasi-kernel of at most half its vertices. arXiv:2610.23487 proves that a source-free digraph satisfies this bound as soon as every nonnegative integer weighting of its vertices admits a quasi-kernel whose closed out-neighborhood carries at least half the total weight, and applies this to break digraphs, for which such a weighted theorem was known. We prove this weighted half-coverage property for every finite loopless oriented graph in which the non-neighborhood of every vertex induces a digraph with a kernel. The class contains all tournaments and all oriented complete multipartite graphs, and it contains oriented graphs that are not break digraphs. The proof chooses a vertex of minimum in-weight, ties broken by in-degree: this vertex together with a kernel of its non-neighborhood is a quasi-kernel, since otherwise one of its in-neighbors would have a smaller score, and in an oriented graph the minimum in-weight is at most half the total weight. Combined with the transfer theorem of arXiv:2610.23487, which is not formalized here, this gives the half-order bound for every source-free digraph of the class. The theorem and its lemmas are checked in Lean 4.
1. Introduction
In directed graph theory, an independent set in a digraph $D = (V, E)$ is a subset of vertices with no directed arcs between any two of its elements. An out-kernel (or simply kernel) is an independent set $K \subseteq V$ that out-dominates $V \setminus K$, meaning that for every $v \in V \setminus K$ there exists $u \in K$ with $(u, v) \in E$. While kernels do not exist in all digraphs due to the obstruction of odd directed cycles, a classical theorem guarantees that every finite digraph contains a quasi-kernel: an independent set $Q \subseteq V$ such that every vertex in $V$ is reachable from $Q$ by a directed path of length at most 2.
In arXiv:2610.23487, Conjecture 1.1 formulates the Small Quasi-kernel Conjecture: every finite loopless directed graph $D = (V, E)$ without sources (that is, in which every vertex has in-degree at least 1) contains a quasi-kernel $Q$ such that $|Q| \le |V|/2$. The source-free condition is indispensable, because every source vertex of $D$ must belong to every quasi-kernel, so that a graph with more than $|V|/2$ sources cannot have a quasi-kernel of size at most $|V|/2$.
arXiv:2610.23487 relates the conjecture to a weighted coverage property. Given a nonnegative integer weighting $w : V \to \mathbb{N}$, call a quasi-kernel $Q$ half-covering for $w$ if its closed out-neighborhood $N^+[Q] = \{v \in V \mid \exists q \in Q, q = v \vee (q, v) \in E\}$ carries at least half of the total weight: $$\sum_{v \in N^+[Q]} w(v) \ge \frac{1}{2} \sum_{v \in V} w(v).$$ Its Theorem 1.3 states that a source-free digraph in which every weighting has a half-covering quasi-kernel has a quasi-kernel of size at most $\lfloor |V|/2 \rfloor$; the proof is a neighborhood-preserving selection argument combined with an alternating-path argument for matchings. The paper applies this to break digraphs, the oriented graphs whose vertex set splits into a part inducing an acyclic digraph and a part inducing a tournament, using a weighted neighborhood theorem for that class from the earlier literature, and so proves the conjecture for source-free break digraphs.
In this work we prove the weighted half-coverage property for another class: the finite loopless oriented graphs in which, for every vertex $v$, the vertices that are neither in- nor out-neighbors of $v$ induce a digraph with a kernel (theorem digraph_nonneighborhood_kernels_weighted_half_cover). The class contains every tournament, where all these non-neighborhoods are empty, and every oriented complete multipartite graph, where the non-neighborhood of $v$ is the rest of its part, an independent set and hence its own kernel. It is not contained in the class of break digraphs: in the digraph obtained from a directed triangle by replacing each vertex by two non-adjacent copies, a tournament part contains at most one copy of each original vertex, so the other part contains one copy of each and hence a directed triangle. Nor does it contain the break digraphs: the directed triangle together with one further vertex adjacent to none of its vertices is a break digraph, but the non-neighborhood of that vertex is the directed triangle, which has no kernel.
2. Preliminaries
We formalize finite directed graphs and their weighted properties following the setting in Lean.
Definition 1 (Finite loopless digraph). Let $\alpha$ be a finite type with decidable equality. A directed graph $D$ on vertex set $\alpha$ is specified by an adjacency relation $D.Adj : \alpha \to \alpha \to \text{Prop}$ with decidable relation. The graph is loopless if $\forall v \in \alpha, \neg D.Adj\ v\ v$.
Definition 2 (Oriented graph). A loopless digraph $D$ is oriented if it contains no directed 2-cycles: $$\forall u, v \in \alpha, \quad D.Adj\ u\ v \implies \neg D.Adj\ v\ u.$$
Definition 3 (Neighborhoods and in-degree). For a vertex $v \in \alpha$, its open in-neighborhood is $N^-(v) = \{u \in \alpha \mid D.Adj\ u\ v\}$. Its open out-neighborhood is $N^+(v) = \{u \in \alpha \mid D.Adj\ v\ u\}$. For any subset $Q \subseteq \alpha$, its closed out-neighborhood is: $$N^+[Q] = \{v \in \alpha \mid \exists q \in Q, q = v \vee D.Adj\ q\ v\}.$$
Definition 4 (Non-neighborhood and non-neighborhood out-kernel). For any vertex $v \in \alpha$, its non-neighborhood consists of all vertices $x \in \alpha \setminus \{v\}$ that are neither in-neighbors nor out-neighbors of $v$: $$x \ne v \wedge \neg D.Adj\ x\ v \wedge \neg D.Adj\ v\ x.$$ An out-kernel of this non-neighborhood is a subset $K \subseteq \alpha$ satisfying three conditions:
- Every element $x \in K$ belongs to the non-neighborhood of $v$: $x \ne v \wedge \neg D.Adj\ x\ v \wedge \neg D.Adj\ v\ x$.
- $K$ is independent in $D$: $\forall x, y \in K, x \ne y \implies \neg D.Adj\ x\ y$.
- $K$ out-dominates the non-neighborhood: for every $x \ne v$ with $\neg D.Adj\ x\ v$ and $\neg D.Adj\ v\ x$, there exists $k \in K$ such that $k = x$ or $D.Adj\ k\ x$.
The local hypothesis asserts that for every $v \in \alpha$, there exists such a non-neighborhood out-kernel $K$.
Definition 5 (Quasi-kernel). A subset $Q \subseteq \alpha$ is a quasi-kernel of $D$ if $Q$ is independent in $D$ and every vertex of $\alpha$ is reachable from $Q$ by a directed path of length at most 2: $$\forall v \in \alpha, \quad \exists q \in Q, \quad q = v \vee D.Adj\ q\ v \vee (\exists z \in \alpha, D.Adj\ q\ z \wedge D.Adj\ z\ v).$$
Definition 6 (Weights and in-weight). A weight function is a map $w : \alpha \to \mathbb{N}$. The total weight of $\alpha$ is $W = \sum_{v \in \alpha} w(v)$. For any vertex $v \in \alpha$, its in-weight is: $$w^-(v) = \sum_{u \in N^-(v)} w(u).$$ For any subset $S \subseteq \alpha$, its weight is $w(S) = \sum_{v \in S} w(v)$.
Definition 7 (Total preorder). A total preorder on a type $A$ (TotalPreorder) is a preorder whose relation $\le$ satisfies totality: $\forall a, b \in A, a \le b \vee b \le a$. The instance LinearOrder.toTotalPreorder registers that every linear order is a total preorder.
Remarks on formalization choices: The weight function $w$ is defined with values in the natural numbers $\mathbb{N}$. To avoid rational fractions and rounding, the half-weight condition is expressed as an integer inequality: $$\sum_{v \in \alpha} w(v) \le 2 \sum_{v \in N^+[Q]} w(v).$$ If $\alpha$ is empty, both sums evaluate to 0 and the inequality holds trivially with $Q = \emptyset$. The local hypothesis only requires the existence of at least one out-kernel for each non-neighborhood, without requiring uniqueness.
3. Main result
The primary theorem formalized in this work is digraph_nonneighborhood_kernels_weighted_half_cover.
Theorem (digraph_nonneighborhood_kernels_weighted_half_cover). Let $D$ be a finite loopless oriented graph on vertex set $\alpha$. Suppose that for every vertex $v \in \alpha$, the induced non-neighborhood of $v$ contains an out-kernel. Then for every nonnegative integer weighting $w : \alpha \to \mathbb{N}$, there exists a quasi-kernel $Q \subseteq \alpha$ such that the closed out-neighborhood of $Q$ contains at least half the total weight: $$\sum_{v \in \alpha} w(v) \le 2 \sum_{v \in N^+[Q]} w(v).$$
In Lean, the theorem digraph_nonneighborhood_kernels_weighted_half_cover takes as arguments a finite type $\alpha$, a digraph $D$ with decidable adjacency, the hypotheses stating that $D$ is loopless and oriented and that every vertex has an out-kernel in its non-neighborhood, and a weighting $w$, and asserts the existence of a finite subset of $\alpha$ that is independent, forms a quasi-kernel, and satisfies the doubled summation inequality over all vertices.
The theorem is supported by several auxiliary results:
- Lemma
digraph_nonneighbor_kernel_or_dominating_vertexestablishes a key structural dichotomy: for any vertex $s$ and any out-kernel $K$ of its non-neighborhood, either $\{s\} \cup K$ is a quasi-kernel of $D$, or there exists a distinct vertex $t$ pointing to $s$ whose in-neighborhood is entirely contained within that of $s$. - A pair of score encoding lemmas establishes that the composite score function $w^-(v) \cdot M + |N^-(v)|$ faithfully implements a lexicographic comparison, so that minimizing the score over vertices minimizes first the in-weight and then the in-degree.
- A coverage weight lemma shows that whenever an independent set $\{s\} \cup K$ covers all vertices not pointing to $s$, the closed out-neighborhood of $\{s\} \cup K$ misses at most the in-weight $w^-(s)$.
- A double-sum inequality for oriented graphs establishes that the double sum of arc weights is at most half the squared total weight, which implies that any vertex of minimal in-weight has in-weight at most $W / 2$.
The main theorem uses no other formalized result beyond digraph_nonneighbor_kernel_or_dominating_vertex and these auxiliary lemmas.
theorem digraph_nonneighborhood_kernels_weighted_half_cover {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v) (horient : ∀ u v, D.Adj u v → ¬ D.Adj v u) (hlocal : ∀ v, ∃ K : Finset α, (∀ x ∈ K, x ≠ v ∧ ¬ D.Adj x v ∧ ¬ D.Adj v x) ∧ (∀ x ∈ K, ∀ y ∈ K, x ≠ y → ¬ D.Adj x y) ∧ (∀ x, x ≠ v → ¬ D.Adj x v → ¬ D.Adj v x → ∃ k ∈ K, k = x ∨ D.Adj k x)) (w : α → ℕ) : ∃ Q : Finset α, (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v) ∧ (∀ v, ∃ u ∈ Q, u = v ∨ D.Adj u v ∨ ∃ z, D.Adj u z ∧ D.Adj z v) ∧ (∑ v ∈ Finset.univ, w v) ≤ 2 * (∑ v ∈ Finset.univ.filter (fun v => ∃ q ∈ Q, q = v ∨ D.Adj q v), w v)
4. Proof
We now present the proof of digraph_nonneighborhood_kernels_weighted_half_cover.
The overall idea is an extremal selection. In an oriented graph, the average in-weight is at most half the total weight. If we pick a vertex $s$ that minimizes the in-weight $w^-(s)$ and, secondarily, minimizes the in-degree $|N^-(s)|$, then its in-weight cannot exceed half the total weight. We then take the out-kernel $K$ of the non-neighborhood of $s$ provided by the local kernel hypothesis. By the structural dichotomy of digraph_nonneighbor_kernel_or_dominating_vertex, if $\{s\} \cup K$ failed to be a quasi-kernel, there would exist an in-neighbor $t \to s$ whose in-neighborhood is strictly contained in that of $s$. But such a vertex $t$ would have $w^-(t) \le w^-(s)$ and $|N^-(t)| < |N^-(s)|$, strictly decreasing the minimal score and yielding an immediate contradiction. Hence $\{s\} \cup K$ must be a quasi-kernel, and its closed out-neighborhood covers every vertex except possibly some in-neighbors of $s$, guaranteeing that it contains at least half the total weight.
We state each lemma and explain how Lean settles it.
Lemma 1 (Lexicographic score encoding). Let $\alpha$ be a finite type, and let $M$ be a constant strictly exceeding the cardinality of every in-neighborhood, so that $|N^-(x)| < M$ for all $x \in \alpha$. If $w_1 \cdot M + c_1 \le w_2 \cdot M + c_2$ with $c_1 < M$, then $w_1 \le w_2$. Furthermore, if $w_1 \le w_2$ and $c_1 < c_2$ with $c_1 < M$, then $w_1 \cdot M + c_1 < w_2 \cdot M + c_2$. Both statements follow from integer division and properties of remainder arithmetic on $\mathbb{N}$.
Lemma 2 (digraph_nonneighbor_kernel_or_dominating_vertex). Let $D$ be a finite loopless digraph, $s \in \alpha$, and let $K \subseteq \alpha$ be an out-kernel of the non-neighborhood of $s$. Then either $\{s\} \cup K$ is an independent quasi-kernel of $D$, or there exists a vertex $t \in \alpha \setminus \{s\}$ such that $D.Adj\ t\ s$ and $N^-(t) \subseteq N^-(s)$.
Proof in Lean: By definition of a non-neighborhood out-kernel, every $k \in K$ satisfies $\neg D.Adj\ s\ k$ and $\neg D.Adj\ k\ s$, and $K$ is independent. Therefore $\{s\} \cup K$ is independent. Suppose $\{s\} \cup K$ is not a quasi-kernel. Then there exists a vertex $x \in \alpha$ that cannot be reached from $\{s\} \cup K$ in at most 2 steps. In particular, $x \notin \{s\} \cup K$, so $x \ne s$. Also, $\neg D.Adj\ s\ x$, since otherwise $s \in \{s\} \cup K$ would reach $x$ in 1 step. If $x$ were also not an in-neighbor of $s$ (that is, $\neg D.Adj\ x\ s$), then $x$ would belong to the non-neighborhood of $s$. But $K$ is an out-kernel of this non-neighborhood, so there would exist $k \in K$ such that $k = x$ or $D.Adj\ k\ x$. In either case, $x$ would be reachable from $K \subseteq \{s\} \cup K$ in at most 1 step, contradicting our assumption. Therefore, we must have $D.Adj\ x\ s$, so $x \in N^-(s)$. Now, consider any in-neighbor $z$ of $x$ with $D.Adj\ z\ x$. If $z$ were not an in-neighbor of $s$ ($\neg D.Adj\ z\ s$), then either $z = s$, or $D.Adj\ s\ z$, or $z$ is in the non-neighborhood of $s$. If $z = s$, then $D.Adj\ s\ x$, which was already ruled out. If $D.Adj\ s\ z$, then $s \to z \to x$ is a path of length 2 from $\{s\} \cup K$ to $x$, a contradiction. If $z$ is in the non-neighborhood of $s$, then some $k \in K$ satisfies $k = z$ or $D.Adj\ k\ z$, giving a path from $k \in K$ to $x$ of length at most 2 ($k = z \to x$ or $k \to z \to x$), again a contradiction. Thus, every in-neighbor $z$ of $x$ must satisfy $D.Adj\ z\ s$. This proves $N^-(x) \subseteq N^-(s)$. Setting $t = x$ provides the second alternative with $t \ne s$ and $D.Adj\ t\ s$.
Lemma 3 (In-weight and in-degree monotonicity). Let $D$ be a loopless digraph, $w : \alpha \to \mathbb{N}$, and let $s, t \in \alpha$ such that $t \ne s$, $D.Adj\ t\ s$, and $N^-(t) \subseteq N^-(s)$. Then $w^-(t) \le w^-(s)$ and $|N^-(t)| < |N^-(s)|$.
Proof in Lean: Since $D$ is loopless, $\neg D.Adj\ t\ t$, which means $t \notin N^-(t)$. However, $D.Adj\ t\ s$, so $t \in N^-(s)$. Since $N^-(t) \subseteq N^-(s)$ and $t \notin N^-(t)$, we have $N^-(t) \subseteq N^-(s) \setminus \{t\}$. Because $t \in N^-(s)$, the set $N^-(s) \setminus \{t\}$ has cardinality strictly smaller than $|N^-(s)|$. Thus $|N^-(t)| \le |N^-(s) \setminus \{t\}| = |N^-(s)| - 1 < |N^-(s)|$. For the weights, since $w$ takes values in $\mathbb{N}$, we have $w^-(t) = \sum_{u \in N^-(t)} w(u) \le \sum_{u \in N^-(s) \setminus \{t\}} w(u) \le \sum_{u \in N^-(s)} w(u) = w^-(s)$.
Lemma 4 (Out-neighborhood coverage weight). Let $s \in \alpha$, $K \subseteq \alpha$, and let $Q = \{s\} \cup K$. If every vertex $x \in \alpha$ satisfying $\neg D.Adj\ x\ s$ belongs to $N^+[Q]$, then: $$\sum_{v \in N^+[Q]} w(v) \ge \sum_{v \in \alpha} w(v) - w^-(s).$$
Proof in Lean: If a vertex $x \in \alpha$ is not in $N^+[Q]$, then by the hypothesis it must satisfy $D.Adj\ x\ s$, meaning $x \in N^-(s)$. Therefore, the set of uncovered vertices is contained in $N^-(s)$: $\alpha \setminus N^+[Q] \subseteq N^-(s)$. Summing the nonnegative weights yields $\sum_{v \notin N^+[Q]} w(v) \le \sum_{v \in N^-(s)} w(v) = w^-(s)$. Since $\sum_{v \in \alpha} w(v) = \sum_{v \in N^+[Q]} w(v) + \sum_{v \notin N^+[Q]} w(v)$, rearranging gives the claimed bound.
Lemma 5 (Double sum bound for oriented graphs). Let $D$ be an oriented digraph and $w : \alpha \to \mathbb{N}$. Then: $$\sum_{v \in \alpha} w(v) w^-(v) \le \frac{1}{2} \left( \sum_{v \in \alpha} w(v) \right)^2.$$
Proof in Lean: Expanding $w^-(v)$ yields $\sum_{v \in \alpha} w(v) w^-(v) = \sum_{v \in \alpha} \sum_{u \in N^-(v)} w(u) w(v) = \sum_{(u, v) \in E} w(u) w(v)$. Because $D$ is oriented, for any pair of distinct vertices $\{u, v\}$, at most one of $(u, v)$ or $(v, u)$ is a directed arc. Because $D$ has no loops, no pair $(u, u)$ is an arc. Therefore $2 \sum_{(u, v) \in E} w(u) w(v) = \sum_{(u, v) \in E} w(u) w(v) + \sum_{(v, u) \in E} w(v) w(u) \le \sum_{u \ne v} w(u) w(v)$. Since $\sum_{u \ne v} w(u) w(v) = (\sum_{v} w(v))^2 - \sum_{v} w(v)^2 \le (\sum_{v} w(v))^2$, dividing by 2 establishes the inequality.
Lemma 6 (Minimum in-weight bound). Let $s \in \alpha$ such that $w^-(s) \le w^-(v)$ for all $v \in \alpha$. If $W = \sum_{v \in \alpha} w(v) > 0$ and $\sum_{v \in \alpha} w(v) w^-(v) \le \frac{1}{2} W^2$, then $2 w^-(s) \le W$.
Proof in Lean: Multiplying the inequality $w^-(s) \le w^-(v)$ by $w(v) \ge 0$ and summing over all $v \in \alpha$ gives $w^-(s) W = \sum_{v \in \alpha} w(v) w^-(s) \le \sum_{v \in \alpha} w(v) w^-(v) \le \frac{1}{2} W^2$. Multiplying through by 2 gives $2 w^-(s) W \le W^2$. Since $W > 0$, dividing by $W$ yields $2 w^-(s) \le W$.
Now we combine these lemmas to establish the main theorem:
1. Base case: If $\alpha$ is empty, we choose $Q = \emptyset$. The independence and quasi-kernel reachability conditions hold vacuously, and both sides of the summation inequality equal 0, so $0 \le 2 \cdot 0$. 2. Minimizer selection: If $\alpha$ is non-empty, we define the encoding modulus $M = \text{card}(\alpha) + 1$ and the score function: $$\text{score}(v) = w^-(v) \cdot M + |N^-(v)|.$$ By the existence of a minimum on a finite non-empty set, there exists a vertex $s \in \alpha$ minimizing $\text{score}(v)$ over all $v \in \alpha$. By Lemma 1, $s$ also minimizes $w^-(v)$: $\forall v \in \alpha, w^-(s) \le w^-(v)$. 3. Applying the structural dichotomy: By the local hypothesis on $s$, there exists an out-kernel $K$ of the non-neighborhood of $s$. We apply Lemma 2 (digraph_nonneighbor_kernel_or_dominating_vertex) to $s$ and $K$. If there exists $t \ne s$ such that $D.Adj\ t\ s$ and $N^-(t) \subseteq N^-(s)$, then by Lemma 3, we have $w^-(t) \le w^-(s)$ and $|N^-(t)| < |N^-(s)|$. Applying Lemma 1 shows that $\text{score}(t) < \text{score}(s)$, which directly contradicts the minimality of $\text{score}(s)$. Thus this alternative is eliminated, and the first alternative must hold: $Q = \{s\} \cup K$ is an independent quasi-kernel of $D$. 4. Neighborhood coverage: Let $x \in \alpha$ be any vertex such that $\neg D.Adj\ x\ s$. If $x = s$, then $x \in Q \subseteq N^+[Q]$. If $x \ne s$ and $D.Adj\ s\ x$, then $s \in Q$ out-dominates $x$, so $x \in N^+[Q]$. If $x \ne s$ and $\neg D.Adj\ s\ x$, then $x$ is in the non-neighborhood of $s$; since $K$ out-dominates this non-neighborhood, there exists $k \in K \subseteq Q$ such that $k = x$ or $D.Adj\ k\ x$, so $x \in N^+[Q]$. 5. Weight calculation: Since every vertex not in $N^-(s)$ is covered by $N^+[Q]$, Lemma 4 gives $\sum_{v \in N^+[Q]} w(v) \ge W - w^-(s)$. If $W = 0$, the inequality $W \le 2 w(N^+[Q])$ holds trivially ($0 \le 0$). If $W > 0$, Lemma 5 and Lemma 6 give $2 w^-(s) \le W$, which is equivalent to $2 (W - w^-(s)) \ge W$. Combining this with the coverage bound yields $2 \sum_{v \in N^+[Q]} w(v) \ge 2 (W - w^-(s)) \ge W = \sum_{v \in \alpha} w(v)$, completing the proof.
5. Discussion
The theorem digraph_nonneighborhood_kernels_weighted_half_cover establishes weighted half-coverage by quasi-kernels for a class of oriented graphs defined by a local condition. We note where each hypothesis enters, what follows for the conjecture, and what remains open.
- Orientation: $D$ has no directed 2-cycles. It is used only in Lemma 5, to bound the minimum in-weight by half the total weight. The selection rule itself fails without it: a formalized example gives a 4-vertex semicomplete digraph with 2-cycles and a weighting in which one vertex minimizes both in-weight and in-degree and is by itself a quasi-kernel, yet its closed out-neighborhood carries less than half of the total weight.
- Non-neighborhood kernels: the non-neighborhood of every vertex must induce a digraph with a kernel. This holds in tournaments, in oriented complete multipartite graphs, and whenever every non-neighborhood induces an acyclic or, more generally, kernel-perfect digraph. It fails as soon as some non-neighborhood induces, for instance, a directed odd cycle.
By Theorem 1.3 of arXiv:2610.23487, every source-free digraph with the weighted half-coverage property has a quasi-kernel of size at most $\lfloor |V|/2 \rfloor$. Hence every source-free oriented graph of the class satisfies the Small Quasi-kernel Conjecture; this deduction rests on the paper's theorem and is not part of the Lean development. For oriented complete multipartite graphs the half-order bound itself was already known (arXiv:2610.23487 recalls that semicomplete multipartite digraphs have two disjoint quasi-kernels); there the theorem adds the weighted statement. The class is incomparable with that of break digraphs, so the result extends the reach of the weighted method beyond the classes treated in the paper without containing them.
Two small formalized examples mark the limits of simpler strategies: in digraph_seven_tournament_two_neighborhood_cover_counterexample, a source-free tournament on 7 vertices has every singleton as a quasi-kernel and only singletons, yet no two of their closed out-neighborhoods cover all vertices; in digraph_small_quasikernel_max_independent_cover_counterexample, a source-free oriented graph on 7 vertices has a maximum independent set of size 4 that lies in the closed out-neighborhood of no quasi-kernel of size at most $7/2$.
Questions that remain:
- Does every oriented graph have the weighted half-coverage property? By the transfer theorem this would prove the Small Quasi-kernel Conjecture for all source-free oriented graphs.
- Can the non-neighborhood kernel hypothesis be weakened to non-neighborhood quasi-kernels? If $K$ is only a quasi-kernel of the non-neighborhood of $s$, does an analogue of the dichotomy in
digraph_nonneighbor_kernel_or_dominating_vertexstill hold? - Can a different selection rule keep the uncovered weight at most half the total in digraphs with 2-cycles, where minimizing in-weight fails?
Why it is research-level
- Weighted half-coverage by quasi-kernels for every oriented graph whose non-neighborhoods have kernels; with the transfer theorem of arXiv:2610.23487 this gives the half-order bound for a class incomparable with the break digraphs treated there
Lean declarations
- digraph_nonneighborhood_kernels_weighted_half_coverIn a finite loopless oriented graph in which the induced non-neighborhood of every vertex has an out-kernel, every nonnegative integer…
- digraph_nonneighbor_kernel_or_dominating_vertexGiven an out-kernel K of the non-neighbors of a vertex v, either {v}∪K is a quasi-kernel or there is a distinct vertex w pointing to v…
- digraph_seven_tournament_two_neighborhood_cover_counterexampleThe displayed source-free seven-vertex tournament has all singleton quasi-kernels, every quasi-kernel is a singleton, no pair of their…
- digraph_small_quasikernel_max_independent_cover_counterexampleIn the displayed source-free oriented seven-vertex graph, the displayed four-vertex independent set is maximum, the graph has a…
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
References
- arXiv:2610.23487 — Small and large quasi-kernels: a weighted transfer theorem
Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.