AFTD Auto-Formalizing Theoretical Domains

Research Blogs

A 24-Vertex Oriented Graph Showing f(4) ≥ 5/4 in a Source-Neighborhood Problem for Quasi-Kernels

low tier2026-11-03reviewed by Claude Code中文版

Abstract

For a vertex $v$ of a sourceless digraph, let $S(v)$ be the set of sources of $D - N^+[v]$ and let $E(v) = N^+(v) \cup N^+(S(v))$. Problem 5.2 of arXiv:2601.11847 asks, for each $d \ge 2$, for the least constant $f(d)$ such that every sourceless oriented graph of maximum out-degree at most $d$ has a vertex $v$ with $f(d)|E(v)| \ge |S(v)| + 1$, and for the least $d$ with $f(d) > 1$. We give an explicit loopless sourceless oriented graph on 24 vertices with maximum out-degree four in which every vertex satisfies $5|E(v)| \le 4(|S(v)|+1)$: the eight non-sink vertices have $|S(v)| = |E(v)| = 4$ and the sixteen sinks have $S(v) = E(v) = \emptyset$. Hence $f(4) \ge 5/4$, and the least $d$ with $f(d) > 1$ is at most 4; if the paper's Conjecture 5.1 (the case $d = 3$ with constant 1) holds, it is exactly 4. The graph is an instance of the paper's construction for Proposition 2.3, sink leaves attached to a regular core, with a 2-diregular oriented core on eight vertices in place of the regular tournament, which that construction needs on at least seven vertices to beat ratio 1. The same graph has a quasi-kernel of six vertices. All properties are verified in Lean 4.

1. Introduction

A quasi-kernel of a digraph $D$ is an independent set $Q$ such that every vertex is reached from $Q$ by a directed path of length at most two. Every digraph has one, and the Small Quasi-Kernel Conjecture asserts that every sourceless digraph on $n$ vertices has one of size at most $n/2$.

The paper arXiv:2601.11847 approaches the conjecture through a smallest counterexample. For a vertex $v$, deleting the closed out-neighbourhood $N^+[v] = \{v\} \cup N^+(v)$ may create sources; write $S(v)$ for the set of sources of $D - N^+[v]$ and \[ E(v) = N^+(v) \cup N^+(S(v)). \] Its Algorithm 1 builds a quasi-kernel from a vertex $v$ and a quasi-kernel of a smaller sourceless digraph, and the resulting criterion is: if every sourceless digraph has a vertex with $t|E(v)| \ge |S(v)| + 1$, quasi-kernels of size at most $tn/(t+1)$ follow, so $t = 1$ would give the conjecture. The paper proves a $4n/7$ bound for maximum out-degree three this way, conjectures (Conjecture 5.1) that every sourceless oriented graph of maximum out-degree at most three has a vertex with $|E(v)| \ge |S(v)| + 1$, and shows (Proposition 2.3) that without a degree bound no constant works: for every $c > 0$ there is a sourceless digraph in which every non-sink vertex has $c|E(v)| < |S(v)| + 1$.

Problem 5.2 of the paper asks how far the method goes at bounded degree: for fixed $d \ge 2$, what is the least constant $f(d)$ such that every sourceless oriented graph of maximum out-degree at most $d$ has a vertex $v$ with \[ f(d)\,|E(v)| \ge |S(v)| + 1, \] and what is the least $d$ such that $f(d) > 1$? A lower bound $f(d) \ge c$ is a single sourceless oriented graph of maximum out-degree at most $d$ in which no vertex satisfies the inequality for any constant below $c$.

The construction behind Proposition 2.3 takes a regular tournament on $2n+1$ vertices in which no out-neighbourhood equals an in-neighbourhood and attaches $k$ private sinks to each vertex; every non-sink vertex then has $|S(v)| = nk$ and $|E(v)| = n + k$, so the ratio is $(nk+1)/(n+k)$ at out-degree $n + k$. The ratio exceeds 1 only when $n, k \ge 2$; for $n = 2$ the regular tournament on five vertices has a vertex whose out-neighbourhood is another vertex's in-neighbourhood, so the smallest case is the seven-vertex Paley tournament with two sinks per vertex, which gives $f(5) \ge 7/5$.

We go one degree lower. Replacing the tournament by an eight-vertex oriented graph in which every vertex has in- and out-degree two, and attaching two private sinks to each core vertex, gives a 24-vertex sourceless oriented graph of maximum out-degree four in which every core vertex has $|S(v)| = |E(v)| = 4$ and every sink has $S(v) = E(v) = \emptyset$. The Lean theorem digraph_four_outdegree_five_four_counterexample states that every vertex satisfies $5|E(v)| \le 4(|S(v)|+1)$. Hence $f(4) \ge 5/4$ and the least $d$ with $f(d) > 1$ is at most four. Since a graph of maximum out-degree at most two also has maximum out-degree at most three, Conjecture 5.1 would give $f(2), f(3) \le 1$, and then the least such $d$ is exactly four. The theorem also exhibits a quasi-kernel of six vertices in the same graph, so the failure of the local criterion here says nothing against the conjecture itself.

2. Preliminaries

We work in finite directed graph theory. All vertices are elements of the standard finite type Fin 24, representing the integers $0, 1, \dots, 23$. A directed graph is specified by an out-neighborhood function $\text{out} : V \to \text{Finset } V$.

\begin{definition}[Loopless Digraph] A directed graph specified by $\text{out} : V \to \text{Finset } V$ is loopless if no vertex belongs to its own out-neighborhood: \[ \forall v \in V,\ v \notin \text{out}(v). \] \end{definition}

\begin{definition}[Source-Free Digraph] A directed graph is source-free (or has minimum in-degree at least 1) if every vertex has at least one in-neighbor: \[ \forall v \in V,\ \exists u \in V,\ v \in \text{out}(u). \] \end{definition}

\begin{definition}[Oriented Digraph] A directed graph is oriented (or asymmetric) if it contains no directed 2-cycles: \[ \forall u, v \in V,\ v \in \text{out}(u) \implies u \notin \text{out}(v). \] \end{definition}

\begin{definition}[Maximum Outdegree] The maximum outdegree of the digraph is at most $d$ if for every vertex $v \in V$, the cardinality of its out-neighborhood satisfies $|\text{out}(v)| \le d$. \end{definition}

\begin{definition}[Local Source Set digraph_local_source_set] For a finite type $\alpha$ with decidable equality and an out-neighborhood map $\text{out} : \alpha \to \text{Finset } \alpha$, the local source set $S(v)$ associated with a vertex $v \in \alpha$ is the set of all vertices $u \in \alpha$ outside the closed out-neighborhood $N^+[v] = \{v\} \cup \text{out}(v)$ that have no in-neighbors outside $N^+[v]$. In Lean: ``lean def digraph_local_source_set {α : Type} [Fintype α] [DecidableEq α] (out : α → Finset α) (v : α) : Finset α := Finset.univ.filter fun u => u ≠ v ∧ u ∉ out v ∧ ∀ p, p ≠ v → p ∉ out v → u ∉ out p `` In standard graph-theoretic notation, $u \in S(v)$ if and only if $u \notin N^+[v]$ and in the induced subgraph $G - N^+[v]$, the in-degree of $u$ is zero. \end{definition}

\begin{definition}[Local Source Expansion digraph_local_source_expansion] The local source expansion set $E(v)$ associated with a vertex $v$ is the union of the out-neighborhood $\text{out}(v)$ and the out-neighborhoods of all vertices in $S(v)$: ``lean def digraph_local_source_expansion {α : Type} [Fintype α] [DecidableEq α] (out : α → Finset α) (v : α) : Finset α := out v ∪ Finset.univ.filter (fun w => ∃ u ∈ digraph_local_source_set out v, w ∈ out u) `` In formula notation, $E(v) = N^+(v) \cup \bigcup_{u \in S(v)} N^+(u)$. \end{definition}

\begin{definition}[Quasi-Kernel] A subset $Q \subseteq V$ is a quasi-kernel of the directed graph if it satisfies two conditions:
• Independent set: for all $u, v \in Q$ with $u \neq v$, $v \notin \text{out}(u)$.
• Two-step out-dominating set: for every vertex $v \in V$, either $v \in Q$, or $v \in \text{out}(u)$ for some $u \in Q$, or there exists $w \in \text{out}(u)$ such that $v \in \text{out}(w)$ for some $u \in Q$. \end{definition}

\begin{definition}[The 24-Vertex Witness digraph_local_four_witness] The function digraph_local_four_witness : Fin 24 → Finset (Fin 24) defines the out-neighborhoods of the 24 vertices as follows:
• Core vertices $\{0, 1, \dots, 7\}$: \begin{align*} \text{out}(0) &= {4, 5, 8, 9}, & \text{out}(1) &= {3, 7, 10, 11}, \\ \text{out}(2) &= {0, 6, 12, 13}, & \text{out}(3) &= {2, 4, 14, 15}, \\ \text{out}(4) &= {2, 7, 16, 17}, & \text{out}(5) &= {1, 6, 18, 19}, \\ \text{out}(6) &= {0, 1, 20, 21}, & \text{out}(7) &= {3, 5, 22, 23}. \end{align*}
• Leaf vertices $\{8, 9, \dots, 23\}$: $\text{out}(v) = \emptyset$ for all $v \ge 8$. \end{definition}

A remark on conventions: the local source set $S(v)$ only considers vertices strictly outside the closed out-neighborhood $N^+[v]$; vertices in $N^+(v)$ are deleted along with $v$. If $v$ is a leaf, $N^+[v] = \{v\}$, and since no vertex had $v$ as an in-neighbor, $S(v) = \emptyset$ and $E(v) = \emptyset$. For empty sets, $|E(v)| = |S(v)| = 0$, and the inequality $5(0) \le 4(0 + 1)$ trivially holds as $0 \le 4$.

3. Main result

The main theorem established and verified in Lean 4 is the existence of the 24-vertex witness:

\begin{theorem}[digraph_four_outdegree_five_four_counterexample] There exists an out-neighborhood function $\text{out} : \text{Fin } 24 \to \text{Finset } (\text{Fin } 24)$ defining a directed graph such that:
• $\text{out}$ is loopless: $\forall v,\ v \notin \text{out}(v)$.
• $\text{out}$ is source-free: $\forall v,\ \exists u,\ v \in \text{out}(u)$.
• $\text{out}$ is oriented: $\forall u, v,\ v \in \text{out}(u) \implies u \notin \text{out}(v)$.
• The maximum outdegree is at most 4: $\forall v,\ |\text{out}(v)| \le 4$.
• For every vertex $v$, the local source set $S(v)$ and the local source expansion set $E(v)$ satisfy: \[ |E(v)| = |S(v)| \quad \text{and} \quad 5 |E(v)| \le 4 (|S(v)| + 1). \]
• There exists an independent two-step out-dominating set $Q \subseteq \text{Fin } 24$ of cardinality exactly 6: \[ |Q| = 6 \quad \text{and} \quad (\forall u, v \in Q,\ u \neq v \implies v \notin \text{out}(u)) \] \[ \text{and} \quad (\forall v,\ \exists u \in Q,\ u = v \lor v \in \text{out}(u) \lor \exists w \in \text{out}(u),\ v \in \text{out}(w)). \] \end{theorem}

In Lean 4, the theorem is stated as: ``lean theorem digraph_four_outdegree_five_four_counterexample : ∃ out : Fin 24 → Finset (Fin 24), (∀ v, v ∉ out v) ∧ (∀ v, ∃ u, v ∈ out u) ∧ (∀ u v, v ∈ out u → u ∉ out v) ∧ (∀ v, (out v).card ≤ 4) ∧ (∀ v, (digraph_local_source_expansion out v).card = (digraph_local_source_set out v).card ∧ 5 * (digraph_local_source_expansion out v).card ≤ 4 * ((digraph_local_source_set out v).card + 1)) ∧ (∃ Q : Finset (Fin 24), Q.card = 6 ∧ (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → v ∉ out u) ∧ (∀ v, ∃ u ∈ Q, u = v ∨ v ∈ out u ∨ ∃ w, w ∈ out u ∧ v ∈ out w)) ` The Lean formulation asserts the existence of an out-neighborhood map on the 24-element type Fin 24`, conjunctively verifying the five structural conditions alongside the existence of the 6-element quasi-kernel $Q$.

Problem 5.2 asks for a vertex with $f|E(v)| \ge |S(v)| + 1$. In this graph no vertex has one when $f < 5/4$: at a sink, $|E(v)| = 0 < 1 = |S(v)| + 1$; at a core vertex, $f|E(v)| < \tfrac54|E(v)| \le |S(v)| + 1$ by the theorem, since $|E(v)| = 4 > 0$. Thus $f(4) \ge 5/4$; at the core vertices $5|E(v)| = 20 = 4(|S(v)|+1)$, so the constant $5/4$ itself is attained by this graph and the bound cannot be improved using it. In particular $f(4) > 1$, so the least $d$ with $f(d) > 1$ in Problem 5.2 is at most four. The quasi-kernel $Q$ has $6 = 24/4$ vertices, well within the conjectured $n/2$.

Theorem digraph_four_outdegree_five_four_counterexample (Lean 4, verified)
theorem digraph_four_outdegree_five_four_counterexample :
    ∃ out : Fin 24 → Finset (Fin 24),
      (∀ v, v ∉ out v) ∧
      (∀ v, ∃ u, v ∈ out u) ∧
      (∀ u v, v ∈ out u → u ∉ out v) ∧
      (∀ v, (out v).card ≤ 4) ∧
      (∀ v, (digraph_local_source_expansion out v).card = (digraph_local_source_set out v).card ∧
        5 * (digraph_local_source_expansion out v).card ≤ 4 * ((digraph_local_source_set out v).card + 1)) ∧
      (∃ Q : Finset (Fin 24), Q.card = 6 ∧
        (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → v ∉ out u) ∧
        (∀ v, ∃ u ∈ Q, u = v ∨ v ∈ out u ∨ ∃ w, w ∈ out u ∧ v ∈ out w))

4. Proof

The proof of the main theorem proceeds by providing the explicit witness function digraph_local_four_witness on the domain Fin 24 and verifying each required property.

### Structure of the Witness Graph

The 24 vertices are partitioned into two sets:

  1. An 8-vertex core $C = \{0, 1, 2, 3, 4, 5, 6, 7\}$.
  2. A 16-vertex set of sink leaves $L = \{8, 9, \dots, 23\}$.

The core subgraph induced on $C$ is a 2-outregular and 2-inregular oriented graph: - Out-arcs between core vertices: $0 \to 4, 5$; $1 \to 3, 7$; $2 \to 0, 6$; $3 \to 2, 4$; $4 \to 2, 7$; $5 \to 1, 6$; $6 \to 0, 1$; $7 \to 3, 5$. - In-arcs to core vertices: Vertex 0 receives arcs from 2, 6. Vertex 1 receives arcs from 5, 6. Vertex 2 receives arcs from 3, 4. Vertex 3 receives arcs from 1, 7. Vertex 4 receives arcs from 0, 3. Vertex 5 receives arcs from 0, 7. Vertex 6 receives arcs from 2, 5. Vertex 7 receives arcs from 1, 4.

Each core vertex $i \in \{0, \dots, 7\}$ has two private sink leaves: $0 \to \{8, 9\}$, $1 \to \{10, 11\}$, $2 \to \{12, 13\}$, $3 \to \{14, 15\}$, $4 \to \{16, 17\}$, $5 \to \{18, 19\}$, $6 \to \{20, 21\}$, $7 \to \{22, 23\}$. All leaves $l \in L$ have outdegree 0 and indegree 1.

### Verification of Basic Digraph Axioms

We establish the structural axioms via the following lemmas:

\begin{lemma}[Loopless] For every $v \in \text{Fin } 24$, $v \notin \text{out}(v)$. \end{lemma} \begin{proof} For each core vertex $i \in \{0, \dots, 7\}$, the explicit set $\text{out}(i)$ does not contain $i$. For each leaf $l \in \{8, \dots, 23\}$, $\text{out}(l) = \emptyset$, so $l \notin \emptyset$. In Lean, this is verified exhaustively by intro v; fin_cases v <;> decide. \end{proof}

\begin{lemma}[Source-Free] For every $v \in \text{Fin } 24$, there exists $u \in \text{Fin } 24$ such that $v \in \text{out}(u)$. \end{lemma} \begin{proof} For every core vertex $i \in \{0, \dots, 7\}$, we exhibited above two distinct core in-neighbors (e.g., $0 \in \text{out}(2)$ and $0 \in \text{out}(6)$). For each leaf $l \in \{8, \dots, 23\}$, $l$ has a unique parent core vertex $\lfloor (l - 8) / 2 \rfloor$ whose out-neighborhood contains $l$. Thus every vertex has an in-neighbor, and the digraph is source-free. In Lean, this is verified by intro v; fin_cases v <;> decide. \end{proof}

\begin{lemma}[Oriented] For all $u, v \in \text{Fin } 24$, if $v \in \text{out}(u)$, then $u \notin \text{out}(v)$. \end{lemma} \begin{proof} If $v$ is a leaf, $\text{out}(v) = \emptyset$, so $u \notin \text{out}(v)$ holds vacuously. If both $u$ and $v$ are core vertices, we inspect all 16 directed edges between core vertices: $(0,4), (0,5), (1,3), (1,7), (2,0), (2,6), (3,2), (3,4), (4,2), (4,7), (5,1), (5,6), (6,0), (6,1), (7,3), (7,5)$. None of the reverse pairs are present. For instance, $4 \in \text{out}(0)$ but $\text{out}(4) = \{2, 7, 16, 17\}$, which does not contain 0. In Lean, the finite check on all $24 \times 24 = 576$ pairs is dispatched by intro u v; fin_cases u <;> fin_cases v <;> decide. \end{proof}

\begin{lemma}[Maximum Outdegree Four] For every $v \in \text{Fin } 24$, $|\text{out}(v)| \le 4$. \end{lemma} \begin{proof} For $v \in \{0, \dots, 7\}$, $|\text{out}(v)| = 4$. For $v \in \{8, \dots, 23\}$, $|\text{out}(v)| = 0 \le 4$. In Lean, intro v; fin_cases v <;> decide. \end{proof}

### Verification of the Source-Neighborhood Inequality

\begin{lemma}[Local Source and Expansion Sets] For each $v \in \text{Fin } 24$, $|E(v)| = |S(v)|$ and $5|E(v)| \le 4(|S(v)| + 1)$. \end{lemma} \begin{proof} We distinguish two cases depending on whether $v$ is a leaf or a core vertex:

1. Case $v \in L$ (leaf): The closed out-neighborhood is $N^+[v] = \{v\} \cup \emptyset = \{v\}$. Since $v$ has outdegree 0, deleting $v$ removes no outgoing edges. In the remaining graph $G - \{v\}$, every other vertex retains all of its original in-neighbors. Because $G$ is source-free, no remaining vertex becomes a source. Thus $S(v) = \emptyset$, giving $|S(v)| = 0$. The expansion set is $E(v) = \text{out}(v) \cup \bigcup_{u \in \emptyset} \text{out}(u) = \emptyset \cup \emptyset = \emptyset$, so $|E(v)| = 0$. We evaluate: \[ |E(v)| = 0 = |S(v)|, \quad \text{and} \quad 5|E(v)| = 0 \le 4(0 + 1) = 4. \] The equality and inequality hold for all 16 leaves.

2. Case $v \in C$ (core vertex): We trace $v = 0$ in detail; the other seven core vertices are checked the same way. The out-neighborhood is $\text{out}(0) = \{4, 5, 8, 9\}$, so the closed out-neighborhood is $N^+[0] = \{0, 4, 5, 8, 9\}$. We determine which vertices in $V \setminus N^+[0]$ have all their in-neighbors inside $N^+[0]$: - Core vertices in $V \setminus N^+[0]$ are $\{1, 2, 3, 6, 7\}$. Their in-neighbors in $G$ are: - Vertex 1: in-neighbors $\{5, 6\}$. Here $5 \in N^+[0]$, but $6 \notin N^+[0]$. Thus 1 retains in-neighbor 6 in $G - N^+[0]$, so $1 \notin S(0)$. - Vertex 2: in-neighbors $\{3, 4\}$. Here $4 \in N^+[0]$, but $3 \notin N^+[0]$. Thus 2 retains in-neighbor 3, so $2 \notin S(0)$. - Vertex 3: in-neighbors $\{1, 7\}$. Neither belongs to $N^+[0]$, so $3 \notin S(0)$. - Vertex 6: in-neighbors $\{2, 5\}$. Here $5 \in N^+[0]$, but $2 \notin N^+[0]$, so $6 \notin S(0)$. - Vertex 7: in-neighbors $\{1, 4\}$. Here $4 \in N^+[0]$, but $1 \notin N^+[0]$, so $7 \notin S(0)$. Hence, no core vertex becomes a source in $G - N^+[0]$. - Leaves in $V \setminus N^+[0]$: Each leaf $l$ has a unique in-neighbor, namely its parent core vertex. Therefore, a leaf $l$ becomes a source in $G - N^+[0]$ if and only if its parent core vertex belongs to $N^+[0]$. The core vertices in $N^+[0]$ are 0, 4, and 5. The leaves of 0 are 8 and 9, which belong to $N^+[0]$ and are deleted. The leaves of 4 are 16 and 17, which lie outside $N^+[0]$. Their only in-neighbor is 4, which is in $N^+[0]$. Therefore, 16 and 17 lose all in-neighbors and belong to $S(0)$. The leaves of 5 are 18 and 19, which lie outside $N^+[0]$. Their only in-neighbor is 5, which is in $N^+[0]$. Therefore, 18 and 19 lose all in-neighbors and belong to $S(0)$. All other leaves have parents in $\{1, 2, 3, 6, 7\} \cap (V \setminus N^+[0])$, so they retain their in-neighbor and do not become sources.

Thus the local source set for $v = 0$ is exactly: \[ S(0) = \{16, 17, 18, 19\}, \quad \text{with } |S(0)| = 4. \] Next, since every $u \in S(0)$ is a leaf, $\text{out}(u) = \emptyset$ for all $u \in S(0)$. The local source expansion set is therefore: \[ E(0) = \text{out}(0) \cup \bigcup_{u \in S(0)} \text{out}(u) = \{4, 5, 8, 9\} \cup \emptyset = \{4, 5, 8, 9\}, \quad \text{with } |E(0)| = 4. \] We now evaluate the required relations: \[ |E(0)| = 4 = |S(0)|, \] and \[ 5 |E(0)| = 5 \times 4 = 20, \quad 4 (|S(0)| + 1) = 4 \times (4 + 1) = 20. \] Thus $5|E(0)| \le 4(|S(0)| + 1)$ holds with exact equality. For every core vertex $v$ the same check shows that no core vertex outside $N^+[v]$ has all its in-neighbours in $N^+[v]$, so $S(v)$ consists of the four private sinks of the two core out-neighbours of $v$; for example $S(1) = \{14, 15, 22, 23\}$ and $S(6) = \{8, 9, 10, 11\}$. Since these are sinks, $E(v) = N^+(v)$, and $|S(v)| = |E(v)| = 4$.

In Lean, both the equality and the inequality for each $v \in \text{Fin } 24$ are verified by: intro v; fin_cases v <;> constructor <;> decide. \end{proof}

### Verification of the Quasi-Kernel of Size Six

\begin{lemma}[Quasi-Kernel Existence] The set $Q = \{0, 1, 12, 13, 20, 21\} \subset \text{Fin } 24$ is an independent set of size 6 that is two-step out-dominating. \end{lemma} \begin{proof} We verify the three conditions: 1. Cardinality: The six elements $0, 1, 12, 13, 20, 21$ are pairwise distinct, so $|Q| = 6$. 2. Independence: We check that no edge exists between any two elements of $Q$: - For $u = 0$: $\text{out}(0) = \{4, 5, 8, 9\}$, which is disjoint from $Q$. - For $u = 1$: $\text{out}(1) = \{3, 7, 10, 11\}$, which is disjoint from $Q$. - For $u \in \{12, 13, 20, 21\}$: $\text{out}(u) = \emptyset$, so no edges leave these vertices. Thus, for all $u, v \in Q$ with $u \neq v$, $v \notin \text{out}(u)$. 3. Two-step out-domination: Every vertex $v \in \text{Fin } 24$ is reachable from $Q$ in at most 2 steps: - Vertices in $Q$ (distance 0): $0, 1, 12, 13, 20, 21$. - Core vertices reached in 1 step: From 0: vertices 4 and 5. From 1: vertices 3 and 7. - Core vertices reached in 2 steps: From $0 \to 4 \to 2$, vertex 2 is reached. From $0 \to 5 \to 6$, vertex 6 is reached. Therefore, all eight core vertices $\{0, 1, 2, 3, 4, 5, 6, 7\}$ are reached from $\{0, 1\} \subseteq Q$ in at most 2 steps. - Leaf vertices: - Leaves of 0: $\{8, 9\}$ are reached in 1 step from 0 ($0 \to 8, 9$). - Leaves of 1: $\{10, 11\}$ are reached in 1 step from 1 ($1 \to 10, 11$). - Leaves of 3: $\{14, 15\}$ are reached in 2 steps from 1 ($1 \to 3 \to 14, 15$). - Leaves of 4: $\{16, 17\}$ are reached in 2 steps from 0 ($0 \to 4 \to 16, 17$). - Leaves of 5: $\{18, 19\}$ are reached in 2 steps from 0 ($0 \to 5 \to 18, 19$). - Leaves of 7: $\{22, 23\}$ are reached in 2 steps from 1 ($1 \to 7 \to 22, 23$). - Leaves of 2: $\{12, 13\}$ are directly in $Q$ (distance 0). - Leaves of 6: $\{20, 21\}$ are directly in $Q$ (distance 0). Hence, every vertex of $\text{Fin } 24$ is at distance at most 2 from $Q$.

In Lean, this check is discharged by refine ⟨{0,1,12,13,20,21}, by decide, by decide, fun v => by fin_cases v <;> decide⟩. \end{proof}

Combining these lemmas completes the Lean proof of digraph_four_outdegree_five_four_counterexample.

5. Discussion

The graph shows $f(4) \ge 5/4$ in Problem 5.2 of arXiv:2601.11847, and so that the least $d$ with $f(d) > 1$ is at most four. It is the paper's own construction for Proposition 2.3 with a different core: the paper's regular tournaments reach a ratio above 1 first at out-degree five, while a 2-diregular oriented core on eight vertices, in which no core vertex outside $N^+[v]$ has all its in-neighbours in $N^+[v]$, already works at out-degree four. Every vertex fails the criterion with constant 1, although the graph has a quasi-kernel of size $n/4$.

Several questions remain.

1. The case $d = 3$. Conjecture 5.1 of the paper asserts $f(3) \le 1$. The construction used here cannot refute it: with core in- and out-degree $c$, $k$ private sinks per core vertex, and no core vertex becoming a source, the ratio at a core vertex is $(ck+1)/(c+k)$, which exceeds 1 only when $c, k \ge 2$, that is at out-degree at least four. Whether $d = 4$ is the threshold therefore rests on Conjecture 5.1.

2. The exact value of $f(4)$. The graph gives only a lower bound; whether some sourceless oriented graph of maximum out-degree four forces a constant above $5/4$, and whether any finite constant suffices at $d = 4$, is open.

3. Growth in $d$. The same family with $c = k = d/2$ gives $f(d) \ge (d^2/4 + 1)/d$ whenever a suitable $d/2$-diregular core exists, so $f(d)$ grows at least linearly; this is the quantitative content of Proposition 2.3. We have not formalized the general family.

Why it is research-level

  • An explicit source-free oriented graph of maximum outdegree four gives f(4) at least 5/4 for the uniform source-neighborhood inequality in arXiv:2601.11847, Problem 5.2, while itself having a small quasi-kernel

Lean declarations

  • digraph_four_outdegree_five_four_counterexampleThere exists a loopless source-free oriented digraph on 24 vertices with maximum outdegree at most four such that for every vertex v, if…
  • digraph_local_source_setGiven finite out-neighborhood sets and a vertex v, the vertices outside the closed out-neighborhood of v that have no in-neighbor outside…
  • digraph_local_source_expansionThe union of the out-neighborhood of v and the out-neighborhoods of the sources remaining after deletion of the closed out-neighborhood of…
  • digraph_local_four_witnessA 24-vertex oriented digraph specified by its out-neighborhoods: an eight-vertex two-outregular core with two private sink leaves at each…

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

References

  1. arXiv:2601.11847

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.