AFTD Auto-Formalizing Theoretical Domains

boruvka_round

def

A Borůvka round transitions forest F to acyclic graph F' containing F under ordinal profile π : V → LinearOrder V if there exist for each connected component c of F a representative r(c) with component c and its globally best outside vertex g(c), every added edge of F' is of the form {r(c), g(c)}, and each pair r(c), g(c) belongs to the same connected component of F'.

Statement

def boruvka_round {V : Type*} (π : V → LinearOrder V) (F F' : SimpleGraph V) : Prop
Defined in
arXiv:2610.23032 Algorithm 1
Verified
20 Oct 2026
Axioms
none listed
Built on 1
  • is_globally_best_outsideGiven a simple graph G on V, an ordinal profile π : V → LinearOrder V, and vertices r, g : V, is_globally_best_outside G π r g holds if g…
Used by 2
  • is_algorithm1_outputA 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…
  • boruvka_round_contraction_leIn any Borůvka round from F to F' under profile π : V → LinearOrder V on finite type V, the number of connected components Fintype.card…

Read back from the Lean

For a type V, a family of linear orders π : V → LinearOrder V, and two simple graphs F and F' on V, boruvka_round π F F' asserts that all of the following hold: 1. F is acyclic (F.IsAcyclic); 2. F is a subgraph of F' (F ≤ F'); 3. F' is acyclic (F'.IsAcyclic); 4. There exist two functions r and g, each mapping from the connected components of F (F.ConnectedComponent) to V, such that: a. For every connected component c of F, r c belongs to c (i.e., F.connectedComponentMk (r c) = c); b. For every connected component c of F, (r c, g c) satisfies is_globally_best_outside F π (r c) (g c), meaning g c does not belong to the same component of F as r c, and for all vertices v : V outside the component of r c, g c ≤ v according to the linear order π (r c); c. For all vertices u, v : V, if u and v are adjacent in F', then either they are adjacent in F, or there exists a connected component c of F such that {u, v} = {r c, g c}; d. For every connected component c of F, r c and g c belong to the same connected component of F' (i.e., F'.connectedComponentMk (r c) = F'.connectedComponentMk (g c)).

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

/-- One round of Borůvka-style contraction: each component proposes its globally best outside edge and a maximal acyclic subset is added. -/
def boruvka_round {V : Type*} (π : V → LinearOrder V) (F F' : SimpleGraph V) : Prop :=
  F.IsAcyclic ∧ F ≤ F' ∧ F'.IsAcyclic ∧
  ∃ (r : F.ConnectedComponent → V) (g : F.ConnectedComponent → V),
    (∀ c, F.connectedComponentMk (r c) = c) ∧
    (∀ c, is_globally_best_outside F π (r c) (g c)) ∧
    (∀ u v, F'.Adj u v → F.Adj u v ∨ (∃ c, (u = r c ∧ v = g c) ∨ (u = g c ∧ v = r c))) ∧
    (∀ c, F'.connectedComponentMk (r c) = F'.connectedComponentMk (g c))
See it in the graphDiscuss this resultChallenge it