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
- simple_graph_laplacian_matrix_isHermitianThe Laplacian matrix of any finite simple graph is Hermitian.
- is_tree_card_coloring_threeFor every finite tree T, the number of proper 3-colorings of T is 3 * 2^(|V| - 1).
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}ᶜ⟩