AFTD Auto-Formalizing Theoretical Domains

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

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.

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

    line 3

    uses le_max_left

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