mst_certificate_monotone
If a partial realization β is an MST identification certificate for G (is_mst_certificate G β), and β is extended by γ (partial_assignment_le β γ), then γ is also an MST identification certificate for G (is_mst_certificate G γ).
Statement
open scoped Classical in theorem mst_certificate_monotone {V : Type*} [Fintype V] (G : SimpleGraph V) (β γ : G.edgeSet → Option Bool) (hcert : is_mst_certificate G β) (hle : partial_assignment_le β γ) : is_mst_certificate G γ
- Source
- scout/2610-40844-stochastic-minimum-spanning-tree-identification-with-binary.md:262
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- partial_assignment_leA partial assignment β is extended by γ (written β ≼ γ) if for every element e and boolean value b, β(e) = some b implies γ(e) = some b.
- is_mst_certificateA partial realization β : G.edgeSet → Option Bool is an MST identification certificate for G if there exists a spanning tree T of G (T ≤ G…
- is_mst_forA simple graph T on a finite vertex type V is a minimum spanning tree of G under edge realization α : G.edgeSet → Bool if T is a subgraph…
Read back from the Lean
For any finite type V, any simple graph G on V, and any partial assignments β, γ : G.edgeSet → Option Bool to the edges of G: if β is an MST certificate for G (meaning there exists a subgraph T ≤ G which is a tree such that for every total Boolean assignment α : G.edgeSet → Bool compatible with β, T is a minimum spanning tree of G with respect to edge weights α), and γ extends β (meaning β e = some b → γ e = some b for all edges e and Booleans b), then γ is also an MST certificate for G.
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
An MST identification certificate $\beta$ specifies a spanning tree $T$ that is guaranteed to be a minimum spanning tree for every total edge-weight assignment compatible with $\beta$. When $\gamma$ extends $\beta$, every total assignment compatible with $\gamma$ is also compatible with $\beta$. Therefore, the same tree $T$ certifies that $\gamma$ is an MST identification certificate.
Obtain the tree $T$ and the certificate properties guaranteed by $\beta$.
By definition, the hypothesis that $\beta$ is an MST certificate (`hcert`) provides a subgraph $T \le G$ such that $T$ is a tree (`hT_tree`) and $T$ is a minimum spanning tree for every total weight assignment $\alpha$ that agrees with $\beta$ (`hT_mst`).
rcases hcert with ⟨T, hTG, hT_tree, hT_mst⟩
Show that the same tree $T$ witnesses that $\gamma$ is an MST certificate.
We witness the existential requirement for `is_mst_certificate G γ` using the same tree $T$. The conditions that $T \le G$ and that $T$ is a tree are already established. For the optimality condition, let $\alpha$ be any total weight assignment compatible with $\gamma$ (`hα`). Since $\gamma$ extends $\beta$ (`hle`), any edge assignment specified by $\beta$ is also assigned by $\gamma$, and hence matches $\alpha$. Applying the certificate property `hT_mst` to this $\alpha$ proves that $T$ is indeed an MST under $\alpha$.
refine ⟨T, hTG, hT_tree, fun α hα => hT_mst α fun e b hb => hα e b (hle e b hb)⟩
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.
open scoped Classical in/-- Extending an MST identification certificate yields another certificate. -/theorem mst_certificate_monotone {V : Type*} [Fintype V] (G : SimpleGraph V) (β γ : G.edgeSet → Option Bool) (hcert : is_mst_certificate G β) (hle : partial_assignment_le β γ) : is_mst_certificate G γ := by rcases hcert with ⟨T, hTG, hT_tree, hT_mst⟩ refine ⟨T, hTG, hT_tree, fun α hα => hT_mst α fun e b hb => hα e b (hle e b hb)⟩