tree_submodular_goal_value_zero
For every finite simple graph G on a vertex type V that is a tree (G.IsTree), the submodular goal value stochastic_mst_submodular_goal_value G is 0.
Statement
open scoped Classical in theorem tree_submodular_goal_value_zero {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.IsTree) : stochastic_mst_submodular_goal_value G = 0
- Source
- scout/2610-40844-stochastic-minimum-spanning-tree-identification-with-binary.md:703
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- stochastic_mst_submodular_goal_valueThe submodular goal value Q_ID(G) of a finite graph G is the infimum in ℕ (sInf) of the set of natural numbers Q such that there exists a…
- 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…
- is_submodular_goal_functionA function g : (G.edgeSet → Option Bool) → ℕ is a submodular goal function with goal value Q for G if: g evaluates to 0 on the empty…
- Used by 1
- nonadaptive_mst_stopping_time_of_isTreeIf G is a tree, then under any binary edge realization α and any querying order π, the stopping time is 0 because the unique spanning tree…
Read back from the Lean
For any finite type V and any simple graph G on V, if G is a tree (G.IsTree), then the stochastic MST submodular goal value of G (stochastic_mst_submodular_goal_value G) equals 0.
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
Because G is already a tree on a finite vertex set V, any spanning sub-tree T' ≤ G has |V| - 1 edges and is therefore equal to G itself. Consequently, G is uniquely its own minimum spanning tree under any edge weights, which makes every partial observation an MST certificate. This allows the constant zero function to serve as a valid submodular goal function achieving goal value Q = 0. Since 0 is an achievable goal value, the infimum over all achievable goal values—the stochastic MST submodular goal value—is 0.
Any spanning sub-tree T' of G has the same number of edges as G.
In any finite graph on vertex set V, any tree has |V| - 1 edges (so |E(G)| + 1 = |V| and |E(T')| + 1 = |V|). Linear integer arithmetic (via omega) deduces that |E(T')| = |E(G)|.
have hcardG := hG.card_edgeFinset have hcardT' := hT'.card_edgeFinset have hcard_eq : T'.edgeFinset.card = G.edgeFinset.card := by omega
Any spanning sub-tree T' ≤ G is identical to G.
Because T' ≤ G, the edges of T' form a subset of the edges of G (by SimpleGraph.edgeFinset_subset_edgeFinset). A subset between finite sets of equal cardinality must be the entire set (Finset.eq_of_subset_of_card_le and ge_of_eq). Since their edge sets are equal, the graphs T' and G are equal (SimpleGraph.edgeFinset_inj).
uses
SimpleGraph.edgeFinset_subset_edgeFinset,Finset.eq_of_subset_of_card_le,ge_of_eq,SimpleGraph.edgeFinset_injhave hsub : T'.edgeFinset ⊆ G.edgeFinset := by rwa [SimpleGraph.edgeFinset_subset_edgeFinset] have heq : T'.edgeFinset = G.edgeFinset := Finset.eq_of_subset_of_card_le hsub (ge_of_eq hcard_eq) rwa [SimpleGraph.edgeFinset_inj] at heq
The tree G is a minimum spanning tree for itself under any edge weights α.
To show that G is an MST for α, we check that G ≤ G (by le_rfl), G is a tree, and any tree subgraph T' ≤ G has total edge weight at least that of G. But by tree_submodular_goal_value_zero_subgraph_eq, any such T' must equal G, so the inequality between their weights holds by reflexivity.
uses
le_rfl,tree_submodular_goal_value_zero_subgraph_eqrefine ⟨le_rfl, hG, fun T' hT'le hT'tree => ?_⟩ have heq : T' = G := tree_submodular_goal_value_zero_subgraph_eq hG hT'tree hT'le subst heq rfl
The constant zero function is a submodular goal function with goal value 0.
The conditions for a submodular goal function require g(∅) = 0, monotonicity, submodularity, and that g(β) = Q if and only if β is an MST certificate. With g identically zero and Q = 0, the first three conditions hold trivially by reflexivity (le_rfl). The goal equivalence 0 = 0 ↔ is_mst_certificate G β reduces to True ↔ True because tree_submodular_goal_value_zero_is_mst_certificate proves that every partial assignment is an MST certificate for G.
uses
le_rfl,tree_submodular_goal_value_zero_is_mst_certificaterefine ⟨rfl, fun _ _ _ => le_rfl, fun _ _ _ _ _ _ => le_rfl, fun β => ?_⟩ simp [tree_submodular_goal_value_zero_is_mst_certificate G hG β]
The stochastic MST submodular goal value of G is 0.
The submodular goal value is defined as the infimum over all goal values Q achievable by a submodular goal function. Since g ≡ 0 achieves Q = 0 (by tree_submodular_goal_value_zero_is_submodular_goal_function), 0 belongs to this set (via Or.inl). The infimum of any set of natural numbers containing 0 is 0 (by Nat.sInf_eq_zero.mpr).
uses
tree_submodular_goal_value_zero_is_submodular_goal_function,Or.inl,Nat.sInf_eq_zero.mprchange sInf {Q | ∃ g, is_submodular_goal_function G g Q} = 0 exact Nat.sInf_eq_zero.mpr (Or.inl ⟨fun _ => 0, tree_submodular_goal_value_zero_is_submodular_goal_function G hG⟩)
SimpleGraph.edgeFinset_subset_edgeFinset- A simple graph is a subgraph of another if and only if its edge set is a subset of the other's edge set.
Finset.eq_of_subset_of_card_le- If one finite set is a subset of another and has at least as many elements, the two sets are equal.
ge_of_eq- Equality implies the reverse inequality in a preorder (a = b implies b ≤ a).
SimpleGraph.edgeFinset_inj- Two simple graphs on the same vertices are equal if and only if their edge sets are equal.
le_rfl- The preorder relation ≤ is reflexive (a ≤ a).
tree_submodular_goal_value_zero_subgraph_eq- Any spanning sub-tree of a finite tree graph is equal to the ambient graph.
tree_submodular_goal_value_zero_is_mst_certificate- For every tree graph G, every partial edge assignment is an MST certificate for G.
Nat.sInf_eq_zero.mpr- A set of natural numbers has infimum 0 if it contains 0 (or if it is empty).
Or.inl- Proves a disjunction A ∨ B by proving the left disjunct A.
tree_submodular_goal_value_zero_is_submodular_goal_function- For every finite tree G, the constant zero function is a submodular goal function with goal value 0.
- The intermediate lemma tree_submodular_goal_value_zero_is_mst_certificate (lines 21–23) is established in term mode without tactic lines; it notes that G itself witnesses the MST certificate condition for any partial assignment β.
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 intheorem tree_submodular_goal_value_zero_subgraph_eq {V : Type*} [Fintype V] {G T' : SimpleGraph V} (hG : G.IsTree) (hT' : T'.IsTree) (hle : T' ≤ G) : T' = G := by have hcardG := hG.card_edgeFinset have hcardT' := hT'.card_edgeFinset have hcard_eq : T'.edgeFinset.card = G.edgeFinset.card := by omega have hsub : T'.edgeFinset ⊆ G.edgeFinset := by rwa [SimpleGraph.edgeFinset_subset_edgeFinset] have heq : T'.edgeFinset = G.edgeFinset := Finset.eq_of_subset_of_card_le hsub (ge_of_eq hcard_eq) rwa [SimpleGraph.edgeFinset_inj] at heqopen scoped Classical intheorem tree_submodular_goal_value_zero_is_mst_for {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.IsTree) (α : G.edgeSet → Bool) : is_mst_for G G α := by refine ⟨le_rfl, hG, fun T' hT'le hT'tree => ?_⟩ have heq : T' = G := tree_submodular_goal_value_zero_subgraph_eq hG hT'tree hT'le subst heq rflopen scoped Classical intheorem tree_submodular_goal_value_zero_is_mst_certificate {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.IsTree) (β : G.edgeSet → Option Bool) : is_mst_certificate G β := ⟨G, le_rfl, hG, fun α _ => tree_submodular_goal_value_zero_is_mst_for G hG α⟩open scoped Classical intheorem tree_submodular_goal_value_zero_is_submodular_goal_function {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.IsTree) : is_submodular_goal_function G (fun _ => 0) 0 := by refine ⟨rfl, fun _ _ _ => le_rfl, fun _ _ _ _ _ _ => le_rfl, fun β => ?_⟩ simp [tree_submodular_goal_value_zero_is_mst_certificate G hG β]open scoped Classical in/-- For a tree, the submodular goal value is 0. -/theorem tree_submodular_goal_value_zero {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.IsTree) : stochastic_mst_submodular_goal_value G = 0 := by change sInf {Q | ∃ g, is_submodular_goal_function G g Q} = 0 exact Nat.sInf_eq_zero.mpr (Or.inl ⟨fun _ => 0, tree_submodular_goal_value_zero_is_submodular_goal_function G hG⟩)