AFTD Auto-Formalizing Theoretical Domains

digraph_digon_minimum_inweight_half_cover_counterexample

theoremverified

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`).

  1. 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.

    line 23

      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

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
See it in the graphDiscuss this resultChallenge it