Lemma 10 — a connected graph of minimum degree has an edge with connected
ProvedOneTwoThree.Weighting.lemma_101-2-3-conjectureconnectivitygraph-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite connected graph with minimum degree at least . Then there exist two vertices such that and the induced subgraph
is connected.
In the proof of Theorem 1 this non-separating edge is the starting point of the case analysis for graphs without vertices of degree one.
Formalization Note Mathlib's Connected requires a nonempty vertex set. Minimum degree at least forces , so is nonempty and the conclusion asks for genuine connectivity.
Preamble
import Mathlib
Formal statement
namespace OneTwoThree.Weighting
open Finset SimpleGraph
theorem lemma_10 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
[DecidableRel G.Adj] (hG : G.Connected) (hdeg : ∀ v, 2 ≤ G.degree v) :
∃ x y : V, G.Adj x y ∧ (G.induce ({x, y}ᶜ : Set V)).Connected := by sorry
end OneTwoThree.Weighting
Source
Keusch, A Solution to the 1-2-3 Conjecture, arXiv:2303.02611v4, p. 11, Lemma 10
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.