isTree_induce_compl_singleton_of_degree_eq_one
If G is a tree and v is a vertex of degree one, then the induced subgraph G[{v}ᶜ] obtained by deleting v is also a tree.
Statement
theorem isTree_induce_compl_singleton_of_degree_eq_one {V : Type*} (G : SimpleGraph V) (v : V) [Fintype ↑(G.neighborSet v)] (hG : G.IsTree) (hdeg : G.degree v = 1) : (G.induce ({v}ᶜ : Set V)).IsTree
- Source
- arXiv:2611.04674 Lemma 2.1 (Pair preparation)
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For any type V, any simple graph G on V, and any vertex v : V whose neighbor set in G is finite: if G is a tree (G.IsTree) and the degree of v in G is 1 (G.degree v = 1), then the subgraph of G induced by the complement of {v} (i.e., deleting the vertex v) is also a tree.
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
By definition, a tree is a connected acyclic graph. Removing a vertex of degree one preserves connectedness, and taking an induced subgraph preserves acyclicity. Combining these two properties shows that removing a degree-one vertex from a tree yields another tree.
The induced subgraph G[{v}ᶜ] is a tree.
By definition, a graph is a tree if and only if it is connected and acyclic. The proof provides witnesses for both components: connectivity of G[{v}ᶜ] follows from the fact that G is connected and v has degree 1 (by `induce_compl_singleton_of_degree_eq_one`), while acyclicity of G[{v}ᶜ] holds because any induced subgraph of the acyclic graph G is acyclic (by `induce`). Combining both properties establishes that G[{v}ᶜ] is a tree.
uses
induce_compl_singleton_of_degree_eq_one,induce(G.induce ({v}ᶜ : Set V)).IsTree := ⟨hG.connected.induce_compl_singleton_of_degree_eq_one hdeg, hG.isAcyclic.induce _⟩
induce_compl_singleton_of_degree_eq_one- Removing a vertex of degree 1 from a connected graph leaves a connected induced subgraph.
induce- Every induced subgraph of an acyclic graph is acyclic.
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
/-- The induced subgraph obtained by removing a leaf (a vertex of degree 1) from a tree is a tree. -/theorem isTree_induce_compl_singleton_of_degree_eq_one {V : Type*} (G : SimpleGraph V) (v : V) [Fintype ↑(G.neighborSet v)] (hG : G.IsTree) (hdeg : G.degree v = 1) : (G.induce ({v}ᶜ : Set V)).IsTree := ⟨hG.connected.induce_compl_singleton_of_degree_eq_one hdeg, hG.isAcyclic.induce _⟩