AFTD Auto-Formalizing Theoretical Domains

isTree_induce_compl_singleton_of_degree_eq_one

theoremverified

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.

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

    line 4

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