op1370_connected_nonleaf_core_card
theoremverified
In a connected finite simple graph with at least three vertices, every set containing all vertices of degree at least two induces a connected graph.
Statement
theorem op1370_connected_nonleaf_core_card {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (hV : 3 ≤ Fintype.card V) (S : Finset V) (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- Built on 1
- op1370_connected_nonleaf_coreIn a finite preconnected graph, any nonempty vertex set containing every vertex of degree at least two induces a connected subgraph.
Lean source view module on GitHub
open scoped BigOperators theorem op1370_connected_nonleaf_core_card {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (hV : 3 ≤ Fintype.card V) (S : Finset V) (hS : ∀ v, 2 ≤ G.degree v → v ∈ S) : (G.induce (S : Set V)).Connected := by classical apply op1370_connected_nonleaf_core G hG.preconnected S · by_contra hne have hd : ∀ v, G.degree v ≤ 1 := by intro v by_contra hv have hlarge : 2 ≤ G.degree v := by omega exact hne ⟨v, hS v hlarge⟩ have hsum : (∑ v : V, G.degree v) ≤ Fintype.card V := by calc (∑ v : V, G.degree v) ≤ ∑ _v : V, 1 := by apply Finset.sum_le_sum intro v hv exact hd v _ = Fintype.card V := by simp have hedge : Fintype.card V ≤ G.edgeFinset.card + 1 := by rw [G.edgeFinset_card] simpa only [Nat.card_eq_fintype_card] using hG.card_vert_le_card_edgeSet_add_one have hdegree := G.sum_degrees_eq_twice_card_edges omega · exact hS