digraph_arborescence_count_at_sanity
Sanity check: on two vertices, the digraph with no arcs has no arborescence towards 0, and the complete digraph (with loops) has exactly one.
Statement
theorem digraph_arborescence_count_at_sanity : digraph_arborescence_count_at (⊥ : Digraph (Fin 2)) 0 = 0 ∧ @digraph_arborescence_count_at 2 ⊤ (fun _ _ => isTrue trivial) 0 = 1
- Source
- sanity check for digraph_arborescence_count_at (OP-404)
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- digraph_arborescence_count_ata_r(D): the number of spanning arborescences of D directed towards the root r. Each is recorded by its successor map p: p r = r, every…
The proof, explained
The theorem is a conjunction of two numerical evaluations for digraphs on two vertices. Both conjuncts are proved by finite evaluation (`decide`), exhaustively checking all parent maps on `Fin 2`.
The empty digraph on two vertices has 0 arborescences towards 0, and the complete digraph on two vertices has exactly 1 arborescence towards 0. automation
Both conjuncts are closed by computational evaluation (`decide`): because the vertex set is finite (`Fin 2`), all possible parent maps can be enumerated and checked exhaustively. For the empty digraph, no parent map satisfies the edge condition; for the complete digraph, exactly the map sending both 0 and 1 to 0 satisfies all conditions.
@digraph_arborescence_count_at 2 ⊤ (fun _ _ => isTrue trivial) 0 = 1 := ⟨by decide, by 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.
theorem digraph_arborescence_count_at_sanity : digraph_arborescence_count_at (⊥ : Digraph (Fin 2)) 0 = 0 ∧ @digraph_arborescence_count_at 2 ⊤ (fun _ _ => isTrue trivial) 0 = 1 := ⟨by decide, by decide⟩