digraph_digon_minimum_inweight_half_cover_counterexample
The displayed loopless semicomplete four-vertex digraph has vertex 0 minimizing both weighted in-degree and in-degree; its singleton is a quasi-kernel but covers less than half the displayed total weight in its closed out-neighborhood.
Statement
theorem digraph_digon_minimum_inweight_half_cover_counterexample : (∀ v, v ∉ in541_digon_out v) ∧ (∀ u v, u ≠ v → v ∈ in541_digon_out u ∨ u ∈ in541_digon_out v) ∧ (∀ v : Fin 4, (∑ u ∈ Finset.univ.filter (fun u => (0 : Fin 4) ∈ in541_digon_out u), in541_digon_weight u) ≤ (∑ u ∈ Finset.univ.filter (fun u => v ∈ in541_digon_out u), in541_digon_weight u)) ∧ (∀ v : Fin 4, (Finset.univ.filter (fun u => (0 : Fin 4) ∈ in541_digon_out u)).card ≤ (Finset.univ.filter (fun u => v ∈ in541_digon_out u)).card) ∧ (∀ v, v = 0 ∨ v ∈ in541_digon_out 0 ∨ ∃ z, z ∈ in541_digon_out 0 ∧ v ∈ in541_digon_out z) ∧ 2 * (∑ v ∈ Finset.univ.filter (fun v => v = 0 ∨ v ∈ in541_digon_out 0), in541_digon_weight v) < ∑ v, in541_digon_weight v
- Source
- Explicit finite counterexample to extending the oriented-graph minimum-inweight construction directly to digons, experiment 14481. Other quasi-kernels may still half-cover the weights.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The theorem provides a counterexample in the form of an explicit 4-vertex semicomplete directed graph with vertex weights. Because all quantifiers and summations range over the finite domain `Fin 4` and all definitions are given by explicit if-then-else expressions, the entire conjunction of properties is a decidable proposition verified by computational evaluation (`decide`).
The graph satisfies all six stated properties: it is loopless, semicomplete, vertex 0 achieves both minimum weighted in-degree (7) and minimum in-degree (2), vertex 0 reaches every other vertex within two steps, and its closed out-neighborhood has weight 5, which is strictly less than half the total weight 12. automation
Because the vertex set `Fin 4` is finite and both the out-neighborhood function and weight function are given by explicit case analyses, each of the six conjuncts is decidable by exhaustive finite checking: 1. Irreflexivity: $v \notin N^+(v)$ holds for all four vertices. 2. Semicompleteness: between any two distinct vertices, at least one directed edge is present. 3. Minimum weighted in-degree: vertex weights are $w(0) = 1$, $w(1) = 4$, $w(2) = 3$, $w(3) = 4$ (summing to 12), and in-weights are $w^-(0) = 7$, $w^-(1) = 7$, $w^-(2) = 8$, $w^-(3) = 8$, so vertex 0 minimizes in-weight. 4. Minimum in-degree: in-degrees are $d^-(0) = 2$, $d^-(1) = 2$, $d^-(2) = 2$, $d^-(3) = 3$, so vertex 0 also minimizes in-degree. 5. Quasi-kernel: $N^+(0) = \{3\}$ and $N^+(3) = \{1, 2\}$, so every vertex $v \in \{0, 1, 2, 3\}$ is equal to 0, in $N^+(0)$, or reachable in two steps from 0 via 3. 6. Under-half weight: the closed out-neighborhood $N^+[0] = \{0, 3\}$ has total weight $1 + 4 = 5$, and $2 \times 5 = 10 < 12$. The `decide` tactic checks all these finite conditions by computational evaluation.
decide
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open scoped BigOperatorsdef in541_digon_out (v : Fin 4) : Finset (Fin 4) := if v = 0 then {3} else if v = 1 then {0,2,3} else if v = 2 then {0,1,3} else {1,2}def in541_digon_weight (v : Fin 4) : ℕ := if v = 0 then 1 else if v = 1 then 4 else if v = 2 then 3 else 4theorem digraph_digon_minimum_inweight_half_cover_counterexample : (∀ v, v ∉ in541_digon_out v) ∧ (∀ u v, u ≠ v → v ∈ in541_digon_out u ∨ u ∈ in541_digon_out v) ∧ (∀ v : Fin 4, (∑ u ∈ Finset.univ.filter (fun u => (0 : Fin 4) ∈ in541_digon_out u), in541_digon_weight u) ≤ (∑ u ∈ Finset.univ.filter (fun u => v ∈ in541_digon_out u), in541_digon_weight u)) ∧ (∀ v : Fin 4, (Finset.univ.filter (fun u => (0 : Fin 4) ∈ in541_digon_out u)).card ≤ (Finset.univ.filter (fun u => v ∈ in541_digon_out u)).card) ∧ (∀ v, v = 0 ∨ v ∈ in541_digon_out 0 ∨ ∃ z, z ∈ in541_digon_out 0 ∧ v ∈ in541_digon_out z) ∧ 2 * (∑ v ∈ Finset.univ.filter (fun v => v = 0 ∨ v ∈ in541_digon_out 0), in541_digon_weight v) < ∑ v, in541_digon_weight v := by decide