two_le_simple_graph_tree_estimate
theoremverified
The tree estimate is at least 2.
Statement
theorem two_le_simple_graph_tree_estimate {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) [DecidableRel T.Adj] : 2 ≤ simple_graph_tree_estimate T
- Source
- Sanity lemma for simple_graph_tree_estimate (arXiv:2610.09650 (The Almost Stacked Hypothesis: A Conjectural Analogue of Sjöstrand's Cover Pebbling Theorem), Definition 5.1).
- Verified
- 12 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- simple_graph_tree_estimateThe tree estimate estim(T) = max{2, 1 + max_r (ρ_T(r) + leaf_T(r))}, where leaf_T(r) is the number of leaves of T other than r and ρ_T(r)…
- Used by 2
- simple_graph_cut_weight_emptyIn any simple graph G on a finite type V with decidable equality and decidable adjacency, with edge weighting w : G.edgeSet → ℝ, the cut…
- dephased_tree_local_noise_criterion_zeroFor any finite simple graph T on vertex type V, the identically zero noise profile q = fun _ => 0 satisfies…
The proof, explained
The quantity simple_graph_tree_estimate T is defined as max 2 (...). The claim that 2 is at most this estimate follows immediately from the general inequality a ≤ max a b.
2 ≤ simple_graph_tree_estimate T
By definition, simple_graph_tree_estimate T is given as the maximum of 2 and an expression involving vertex degrees and distances. Applying the general property that a ≤ max a b with a = 2 proves the inequality directly.
uses
le_max_leftle_max_left _ _
le_max_left- In any linear order, a is less than or equal to max(a, b).
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
theorem two_le_simple_graph_tree_estimate {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) [DecidableRel T.Adj] : 2 ≤ simple_graph_tree_estimate T := le_max_left _ _