op1370_connected_nonleaf_core
theoremverified
In a finite preconnected graph, any nonempty vertex set containing every vertex of degree at least two induces a connected subgraph.
Statement
theorem op1370_connected_nonleaf_core {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Preconnected) (S : Finset V) (hne : S.Nonempty) (hS : ∀ v, 2 ≤ G.degree v → v ∈ S) : (G.induce (S : Set V)).Connected
- Source
- Filed by the prover as a step towards another result
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- op1370_connected_nonleaf_core_cardIn a connected finite simple graph with at least three vertices, every set containing all vertices of degree at least two induces a…
Lean source view module on GitHub
theorem op1370_connected_nonleaf_core {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Preconnected) (S : Finset V) (hne : S.Nonempty) (hS : ∀ v, 2 ≤ G.degree v → v ∈ S) : (G.induce (S : Set V)).Connected := by classical have hs : ∀ v ∉ (S : Set V), (G.neighborSet v).Subsingleton := by intro v hv have hn : ¬ 2 ≤ G.degree v := fun h => hv (hS v h) have hd : G.degree v ≤ 1 := Nat.lt_succ_iff.mp (Nat.lt_of_not_ge hn) have hc : (G.neighborFinset v).card ≤ 1 := hd simpa only [SimpleGraph.coe_neighborFinset] using (Finset.card_le_one_iff_subsingleton.mp hc) obtain ⟨v, hv⟩ := hne letI : Nonempty (S : Set V) := ⟨⟨v, hv⟩⟩ exact ⟨hG.induce_of_degree_eq_one hs⟩