boruvka_round
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))