AFTD Auto-Formalizing Theoretical Domains

digraph_arborescence_count_at_sanity

theoremverified

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

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

    line 3

          @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

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