AFTD Auto-Formalizing Theoretical Domains

is_algorithm1_output

def

A graph F on a finite type V is an output of Algorithm 1 on ordinal profile π : V → LinearOrder V if F is a tree (F.IsTree) and there exists a sequence of simple graphs of length k + 1 starting at the empty graph ⊥ and ending at F such that each step from seq(i) to seq(i+1) is a Borůvka round under π.

Statement

def is_algorithm1_output {V : Type*} [Fintype V] (π : V → LinearOrder V) (F : SimpleGraph V) : Prop
Defined in
arXiv:2610.23032 Algorithm 1
Verified
20 Oct 2026
Axioms
none listed
Built on 1
  • boruvka_roundA Borůvka round transitions forest F to acyclic graph F' containing F under ordinal profile π : V → LinearOrder V if there exist for each…

Read back from the Lean

Given a finite type $V$, a family of linear orders $\pi : V \to \text{LinearOrder}(V)$ (giving a linear order on $V$ for each vertex in $V$), and a simple graph $F$ on $V$, is_algorithm1_output π F asserts that there exist a natural number $k$ and a sequence of simple graphs $\mathrm{seq} : \mathrm{Fin}(k + 1) \to \mathrm{SimpleGraph}(V)$ such that: 1. The initial graph $\mathrm{seq}(0)$ is the empty graph $\bot$ on $V$ (having no edges). 2. The final graph $\mathrm{seq}(\mathrm{last}(k))$ is $F$. 3. For each index $i \in \mathrm{Fin}(k)$, the transition from $\mathrm{seq}(i)$ to $\mathrm{seq}(i + 1)$ is a Borůvka round with respect to $\pi$ (boruvka_round π (seq i.castSucc) (seq i.succ)). 4. $F$ is a tree (F.IsTree, meaning $F$ is connected and acyclic).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A tree F is an output of Algorithm 1 if it is reached from the empty forest by a sequence of Borůvka rounds. -/
def is_algorithm1_output {V : Type*} [Fintype V] (π : V → LinearOrder V) (F : SimpleGraph V) : Prop :=
  ∃ (k : ℕ) (seq : Fin (k + 1) → SimpleGraph V),
    seq 0 = ⊥ ∧
    seq (Fin.last k) = F ∧
    (∀ i : Fin k, boruvka_round π (seq i.castSucc) (seq i.succ)) ∧
    F.IsTree
See it in the graphDiscuss this resultChallenge it