AFTD Auto-Formalizing Theoretical Domains

is_tree_induce_compl_singleton

theoremverified

Removing a vertex of degree one from a finite tree yields an induced subgraph that is also a tree.

Statement

lemma is_tree_induce_compl_singleton {V : Type*} [Fintype V] [DecidableEq V]
    (T : SimpleGraph V) [DecidableRel T.Adj] (hT : T.IsTree) {v : V} (hv : T.degree v = 1) :
    (T.induce {v}ᶜ).IsTree
Source
step towards is_tree_card_coloring_three
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 2

Lean source view module on GitHub

/-- Removing a vertex of degree one from a finite tree yields an induced subgraph that is also a tree. -/
lemma is_tree_induce_compl_singleton {V : Type*} [Fintype V] [DecidableEq V]
    (T : SimpleGraph V) [DecidableRel T.Adj] (hT : T.IsTree) {v : V} (hv : T.degree v = 1) :
    (T.induce {v}ᶜ).IsTree := ⟨hT.connected.induce_compl_singleton_of_degree_eq_one hv, hT.isAcyclic.induce {v}ᶜ⟩
See it in the graphDiscuss this resultChallenge it