boruvka_round_contraction_le
In any Borůvka round from F to F' under profile π : V → LinearOrder V on finite type V, the number of connected components Fintype.card F'.ConnectedComponent is at most Fintype.card F.ConnectedComponent / 2.
Statement
theorem boruvka_round_contraction_le {V : Type*} [Fintype V] [DecidableEq V] (π : V → LinearOrder V) (F F' : SimpleGraph V) (h_round : boruvka_round π F F') : Fintype.card F'.ConnectedComponent ≤ Fintype.card F.ConnectedComponent / 2
- Source
- arXiv:2610.23032 Lemma 6.1
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- 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…
Read back from the Lean
Let $V$ be a finite type with decidable equality. Let $\pi$ be a family of linear orders on $V$ indexed by $V$ (i.e., $\pi(v)$ is a linear order on $V$ for each $v \in V$). Let $F$ and $F'$ be simple graphs on $V$. If $F'$ is obtained from $F$ by a Boruvka round with respect to $\pi$ (boruvka_round π F F'), then the number of connected components of $F'$ is at most half the number of connected components of $F$ (specifically, $\le \lfloor |F.\text{ConnectedComponent}| / 2 \rfloor$ using natural number division).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
A Borůvka round adds an edge out of every connected component of F to connect it to some outside component, resulting in a supergraph F'. The inclusion F ≤ F' induces a canonical map f from the connected components of F to those of F'. For each component b of F' represented by a vertex v, the fiber f⁻¹(b) contains both the F-component of v and the distinct F-component of the target vertex chosen by the Borůvka step. Because every fiber has size at least 2, double counting shows 2 * |F'.ConnectedComponent| ≤ |F.ConnectedComponent|, so the number of connected components is at least halved.
We unpack the Borůvka round hypotheses and define the canonical projection map f : F.ConnectedComponent → F'.ConnectedComponent induced by the subgraph inclusion F ≤ F'.
We rewrite the cardinalities to Nat.card and unpack the definition of a Borůvka round, obtaining acyclicity of F and F', the inclusion F ≤ F', root representatives r(c), and target vertices g(c) outside each component c connected to r(c) in F'. The inclusion F ≤ F' induces a canonical map f on connected components sending each component of F to the component of F' containing it.
uses
Nat.card_eq_fintype_card,SimpleGraph.ConnectedComponent.map,SimpleGraph.Hom.ofLErw [← Nat.card_eq_fintype_card, ← Nat.card_eq_fintype_card] classical rcases h_round with ⟨hF_acyc, h_le, hF'_acyc, r, g, hr, hg, hadj, heq⟩ let f : F.ConnectedComponent → F'.ConnectedComponent := SimpleGraph.ConnectedComponent.map (SimpleGraph.Hom.ofLE h_le)
For an arbitrary component b of F', represented by a vertex v, we define two components c₁ and c₂ of F and observe that f(c₁) = b.
To show that every fiber of f has size at least 2, we consider an arbitrary component b of F', which by component induction can be written as the component of some vertex v. We define c₁ = [v]_F to be the F-component of v, and c₂ = [g(c₁)]_F to be the F-component of the target vertex chosen by the Borůvka step for c₁. Since f sends [v]_F to [v]_{F'}, we have f(c₁) = b. By definition, the representative root r(c₁) also belongs to c₁.
uses
SimpleGraph.ConnectedComponent.ind,SimpleGraph.ConnectedComponent.map_mk,SimpleGraph.Hom.ofLEhave h_fibers : ∀ b ∈ (Finset.univ : Finset F'.ConnectedComponent), 2 ≤ (Finset.filter (fun a => f a = b) (Finset.univ : Finset F.ConnectedComponent)).card := by intro b hb induction b using SimpleGraph.ConnectedComponent.ind with | _ v => let c1 := F.connectedComponentMk v let c2 := F.connectedComponentMk (g c1) have hc1_map : f c1 = F'.connectedComponentMk v := SimpleGraph.ConnectedComponent.map_mk (SimpleGraph.Hom.ofLE h_le) v have hr_c1 : F.connectedComponentMk (r c1) = c1 := hr c1
The components c₁ and c₂ are distinct.
Assume for contradiction that c₁ = c₂. The Borůvka property for c₁ guarantees that the chosen target vertex g(c₁) does not belong to the component of the root r(c₁). Since r(c₁) ∈ c₁, this means [g(c₁)]_F ≠ c₁, contradicting c₁ = c₂.
have hc1_ne_c2 : c1 ≠ c2 := by intro he have hdiff := (hg c1).1 rw [hr_c1] at hdiff exact hdiff he.symm
The component c₂ also maps to b under f.
Under f, the component c₂ = [g(c₁)]_F maps to [g(c₁)]_{F'}. The Borůvka round contracts an edge between r(c₁) and g(c₁), meaning [g(c₁)]_{F'} = [r(c₁)]_{F'}. In turn, [r(c₁)]_{F'} = f([r(c₁)]_F) = f(c₁) = b. Chaining these equalities yields f(c₂) = b.
uses
SimpleGraph.ConnectedComponent.map_mk,SimpleGraph.Hom.ofLEhave hc2_map : f c2 = F'.connectedComponentMk v := by have h1 : f c2 = F'.connectedComponentMk (g c1) := SimpleGraph.ConnectedComponent.map_mk (SimpleGraph.Hom.ofLE h_le) (g c1) have h2 : F'.connectedComponentMk (g c1) = F'.connectedComponentMk (r c1) := (heq c1).symm have h3 : F'.connectedComponentMk (r c1) = f (F.connectedComponentMk (r c1)) := (SimpleGraph.ConnectedComponent.map_mk (SimpleGraph.Hom.ofLE h_le) (r c1)).symm have h4 : f (F.connectedComponentMk (r c1)) = f c1 := by rw [hr_c1] exact h1.trans (h2.trans (h3.trans (h4.trans hc1_map)))
The fiber of f over b contains at least two distinct components of F.
Since f(c₁) = b and f(c₂) = b, both c₁ and c₂ belong to the fiber {a | f(a) = b}. Because c₁ ≠ c₂, the pair set {c₁, c₂} has cardinality 2. Since this pair is a subset of the fiber, the fiber has cardinality at least 2.
uses
Finset.mem_insert,Finset.mem_singleton,Finset.card_pair,Finset.card_le_cardhave h1 : c1 ∈ Finset.filter (fun a => f a = F'.connectedComponentMk v) Finset.univ := by simp [hc1_map] have h2 : c2 ∈ Finset.filter (fun a => f a = F'.connectedComponentMk v) Finset.univ := by simp [hc2_map] have hsub : {c1, c2} ⊆ Finset.filter (fun a => f a = F'.connectedComponentMk v) Finset.univ := by intro z hz simp only [Finset.mem_insert, Finset.mem_singleton] at hz rcases hz with rfl | rfl <;> assumption have hcard_pair : ({c1, c2} : Finset F.ConnectedComponent).card = 2 := Finset.card_pair hc1_ne_c2 rw [← hcard_pair] exact Finset.card_le_card hsub
The number of connected components in F' is at most half that in F.
Applying Finset.mul_card_image_le_card_of_maps_to with fiber lower bound 2 yields 2 * |F'.ConnectedComponent| ≤ |F.ConnectedComponent|. Rewriting finset cardinalities of the universe back to type cardinalities, linear integer arithmetic (omega) concludes |F'.ConnectedComponent| ≤ |F.ConnectedComponent| / 2.
uses
Finset.mul_card_image_le_card_of_maps_to,Finset.mem_univ,Finset.card_univ,Nat.card_eq_fintype_cardhave h_mul := Finset.mul_card_image_le_card_of_maps_to (f := f) (s := (Finset.univ : Finset F.ConnectedComponent)) (t := (Finset.univ : Finset F'.ConnectedComponent)) (fun a _ => Finset.mem_univ (f a)) 2 h_fibers rw [Finset.card_univ, Finset.card_univ] at h_mul rw [← Nat.card_eq_fintype_card, ← Nat.card_eq_fintype_card] at h_mul omega
Nat.card_eq_fintype_card- For any finite type α, its Nat.card equals its Fintype.card.
SimpleGraph.ConnectedComponent.map- A graph homomorphism from G to G' induces a well-defined map between their connected components.
SimpleGraph.Hom.ofLE- A subgraph inclusion G₁ ≤ G₂ induces a graph homomorphism from G₁ to G₂.
SimpleGraph.ConnectedComponent.ind- Induction principle for connected components: a property holds for every component if it holds for the component of every vertex.
SimpleGraph.ConnectedComponent.map_mk- The component map induced by a homomorphism φ sends the component containing v to the component containing φ(v).
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to {a} if and only if it equals a.
Finset.card_pair- A pair set {a, b} has cardinality 2 if a ≠ b.
Finset.card_le_card- If s ⊆ t for finite sets s and t, then the cardinality of s is at most that of t.
Finset.mul_card_image_le_card_of_maps_to- If a map f sends elements of s into t and every fiber over t has at least n elements in s, then n * |t| ≤ |s|.
Finset.mem_univ- Every element of a finite type belongs to its universal finset Finset.univ.
Finset.card_univ- The cardinality of the universal finset Finset.univ of type α equals Fintype.card α.
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.
/-- A Borůvka round reduces the number of connected components by at least a factor of 2 (Lemma 6.1). -/theorem boruvka_round_contraction_le {V : Type*} [Fintype V] [DecidableEq V] (π : V → LinearOrder V) (F F' : SimpleGraph V) (h_round : boruvka_round π F F') : Fintype.card F'.ConnectedComponent ≤ Fintype.card F.ConnectedComponent / 2 := by rw [← Nat.card_eq_fintype_card, ← Nat.card_eq_fintype_card] classical rcases h_round with ⟨hF_acyc, h_le, hF'_acyc, r, g, hr, hg, hadj, heq⟩ let f : F.ConnectedComponent → F'.ConnectedComponent := SimpleGraph.ConnectedComponent.map (SimpleGraph.Hom.ofLE h_le) have h_fibers : ∀ b ∈ (Finset.univ : Finset F'.ConnectedComponent), 2 ≤ (Finset.filter (fun a => f a = b) (Finset.univ : Finset F.ConnectedComponent)).card := by intro b hb induction b using SimpleGraph.ConnectedComponent.ind with | _ v => let c1 := F.connectedComponentMk v let c2 := F.connectedComponentMk (g c1) have hc1_map : f c1 = F'.connectedComponentMk v := SimpleGraph.ConnectedComponent.map_mk (SimpleGraph.Hom.ofLE h_le) v have hr_c1 : F.connectedComponentMk (r c1) = c1 := hr c1 have hc1_ne_c2 : c1 ≠ c2 := by intro he have hdiff := (hg c1).1 rw [hr_c1] at hdiff exact hdiff he.symm have hc2_map : f c2 = F'.connectedComponentMk v := by have h1 : f c2 = F'.connectedComponentMk (g c1) := SimpleGraph.ConnectedComponent.map_mk (SimpleGraph.Hom.ofLE h_le) (g c1) have h2 : F'.connectedComponentMk (g c1) = F'.connectedComponentMk (r c1) := (heq c1).symm have h3 : F'.connectedComponentMk (r c1) = f (F.connectedComponentMk (r c1)) := (SimpleGraph.ConnectedComponent.map_mk (SimpleGraph.Hom.ofLE h_le) (r c1)).symm have h4 : f (F.connectedComponentMk (r c1)) = f c1 := by rw [hr_c1] exact h1.trans (h2.trans (h3.trans (h4.trans hc1_map))) have h1 : c1 ∈ Finset.filter (fun a => f a = F'.connectedComponentMk v) Finset.univ := by simp [hc1_map] have h2 : c2 ∈ Finset.filter (fun a => f a = F'.connectedComponentMk v) Finset.univ := by simp [hc2_map] have hsub : {c1, c2} ⊆ Finset.filter (fun a => f a = F'.connectedComponentMk v) Finset.univ := by intro z hz simp only [Finset.mem_insert, Finset.mem_singleton] at hz rcases hz with rfl | rfl <;> assumption have hcard_pair : ({c1, c2} : Finset F.ConnectedComponent).card = 2 := Finset.card_pair hc1_ne_c2 rw [← hcard_pair] exact Finset.card_le_card hsub have h_mul := Finset.mul_card_image_le_card_of_maps_to (f := f) (s := (Finset.univ : Finset F.ConnectedComponent)) (t := (Finset.univ : Finset F'.ConnectedComponent)) (fun a _ => Finset.mem_univ (f a)) 2 h_fibers rw [Finset.card_univ, Finset.card_univ] at h_mul rw [← Nat.card_eq_fintype_card, ← Nat.card_eq_fintype_card] at h_mul omega