Corollary 10, p. 98 — after the removal step, A(v) never holds vertices of two distinct non-singleton clusters of OPT′
ProvedCorrClustBBC.Cautious.corollary_10Let and let be a complete -labelled graph on a finite vertex set . Let be a clustering of whose clusters with at least two vertices are -clean in (for instance of Lemma 6). Consider any run of Algorithm Cautious on , with any choice of pivots and any removal order, producing clusters , and let be the set left after the removal step 1(b) in the iteration that produced . Then for every and all whose clusters in have at least two vertices,
Corollary 10 is the key step of Theorem 7's proof: each set produced by the removal step meets at most one non-singleton cluster of .
Formalization Note The statement covers every iteration that produced a nonempty cluster. An iteration in the final phase, which produces , has an empty removal result, for which the claim is vacuous.
Differences from the source:
- generalization: OPT′ → every clustering D whose clusters with at least two vertices are δ-clean in G; reason: the proof uses only this property of OPT′, which OPT′ has by Lemma 6.
- reading: "repeat until no vertices are left or until all the produced sets A(v) are empty" → the run may stop exactly when every remaining vertex, tried as the pivot, has some execution of steps 1(a)–(c) producing ∅; reason: the phrase is ambiguous; this is the reading under which "all the produced sets are empty" refers to every remaining vertex.
- reading: N⁺(v), δ-goodness and the "y ∈ V" of step 1(c) in every iteration after the first → taken in the graph induced on the vertices not yet clustered (the current set R of the run); reason: step 2 deletes A(v) "from the set of vertices" before repeating, and the proof of Theorem 7 (p. 99) argues in "the remaining graph G \ (⋃_{ℓ<i} A_ℓ)".
- encoding: "after every application of the removal step 1b" → for the removal result A′ᵢ recorded with every produced cluster of a run of the run relation, over all pivot choices and removal orders; reason: the algorithm is nondeterministic; iterations producing ∅ have A′ = ∅, where the claim is vacuous.
import Mathlib import Definitions.Def_CorrClustBBC_Cautious_Setting
namespace CorrClustBBC.Cautious
theorem corollary_10 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
(D : Setoid V) (hD : NonsingletonClean G δ44 D)
(L : List (Finset V × Finset V × Finset V)) (Z : Finset V) (hrun : Run G Finset.univ L Z) :
∀ p ∈ L, ∀ u ∈ p.1, ∀ v ∈ p.1, 2 ≤ (classOf D u).card → 2 ≤ (classOf D v).card →
D.r u v := by sorry
end CorrClustBBC.Cautious
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.