simple_graph_connected_degree_pos
In a connected graph with at least two vertices every vertex has positive degree.
Statement
theorem simple_graph_connected_degree_pos {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hconn : G.Connected) (hk : 2 ≤ Fintype.card V) (v : V) : 0 < G.degree v
- Source
- Helper for arXiv:2610.12109 (Sharp linear Turán remainders for cycle and edge extremality), Lemma 2.5 (equality case of the lower bound: the extremal tree is a path).
- Verified
- 12 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- simple_graph_is_tree_sum_choose_degree_eq_iff_pathFor a tree T on k ≥ 2 vertices, σ₂(T) = k − 2 if and only if T is isomorphic to the path P_k.
The proof, explained
Since the graph has at least two vertices, we can choose a vertex w distinct from v. Because the graph is connected, there exists a walk from v to w. This walk cannot be empty because its endpoints are distinct, so it must begin with an edge connecting v to some neighbor x. The existence of this neighbor shows that the neighbor set of v is nonempty, so v has strictly positive degree.
There exists a vertex w distinct from v, and a walk p connecting v to w.
Since the vertex type has cardinality at least 2, its cardinality is strictly greater than 1 (by linear arithmetic via omega). By Fintype.exists_ne_of_one_lt_card, there exists a vertex w ≠ v. Because G is connected (hconn.preconnected), there exists a walk p from v to w.
uses
Fintype.exists_ne_of_one_lt_cardobtain ⟨w, hw⟩ := Fintype.exists_ne_of_one_lt_card (by omega) v obtain ⟨p⟩ := hconn.preconnected v w
The walk p cannot be empty.
We split into cases on the structure of the walk p. If p is the empty walk (nil), its endpoints coincide, giving v = w. This contradicts the fact that w ≠ v (hw), ruling out this case.
cases p with | nil => exact absurd rfl hw
The degree of v is strictly positive.
In the non-empty walk case (cons), p begins with an edge from v to some vertex x, establishing that v is adjacent to x. By SimpleGraph.card_neighborFinset_eq_degree, the degree of v equals the cardinality of its neighbor finset. Since x belongs to this neighbor finset by SimpleGraph.mem_neighborFinset, the finset is nonempty, and Finset.card_pos.2 implies its cardinality—and therefore the degree of v—is strictly positive.
uses
SimpleGraph.card_neighborFinset_eq_degree,Finset.card_pos.2,SimpleGraph.mem_neighborFinset| @cons _ x _ h _ => rw [← SimpleGraph.card_neighborFinset_eq_degree] exact Finset.card_pos.2 ⟨x, (SimpleGraph.mem_neighborFinset _ _ _).2 h⟩
Fintype.exists_ne_of_one_lt_card- In a finite type with cardinality strictly greater than 1, every element has a distinct counterpart.
SimpleGraph.card_neighborFinset_eq_degree- The degree of a vertex equals the cardinality of its neighbor finset.
Finset.card_pos.2- A finite set has strictly positive cardinality if it is nonempty.
SimpleGraph.mem_neighborFinset- A vertex is in the neighbor finset of v if and only if it is adjacent to v.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem simple_graph_connected_degree_pos {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hconn : G.Connected) (hk : 2 ≤ Fintype.card V) (v : V) : 0 < G.degree v := by obtain ⟨w, hw⟩ := Fintype.exists_ne_of_one_lt_card (by omega) v obtain ⟨p⟩ := hconn.preconnected v w cases p with | nil => exact absurd rfl hw | @cons _ x _ h _ => rw [← SimpleGraph.card_neighborFinset_eq_degree] exact Finset.card_pos.2 ⟨x, (SimpleGraph.mem_neighborFinset _ _ _).2 h⟩