AFTD Auto-Formalizing Theoretical Domains

boruvka_round_contraction_le

theoremverified

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.

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

    lines 7–11

    uses Nat.card_eq_fintype_card, SimpleGraph.ConnectedComponent.map, SimpleGraph.Hom.ofLE

      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)
  2. 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₁.

    lines 12–21

    uses SimpleGraph.ConnectedComponent.ind, SimpleGraph.ConnectedComponent.map_mk, SimpleGraph.Hom.ofLE

      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
  3. 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₂.

    lines 22–26

          have hc1_ne_c2 : c1 ≠ c2 := by
            intro he
            have hdiff := (hg c1).1
            rw [hr_c1] at hdiff
            exact hdiff he.symm
  4. 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.

    lines 27–35

    uses SimpleGraph.ConnectedComponent.map_mk, SimpleGraph.Hom.ofLE

          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)))
  5. 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.

    lines 36–47

    uses Finset.mem_insert, Finset.mem_singleton, Finset.card_pair, Finset.card_le_card

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

    lines 48–53

    uses Finset.mul_card_image_le_card_of_maps_to, Finset.mem_univ, Finset.card_univ, Nat.card_eq_fintype_card

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

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