graph_degree_pos_of_connected_of_ne
In a connected graph, a vertex x with some other vertex y has positive degree.
Statement
theorem graph_degree_pos_of_connected_of_ne {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (x y : V) (hxy : x ≠ y) : 0 < G.degree x
- Source
- Helper for graph_lly_curvature_le_two_div_dist (OP-164, arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature)).
- Verified
- 10 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 3
- graph_ollivier_curvature_div_le_two_div_distIn a finite connected graph, for x ≠ y and α ∈ [0, 1), κ_α(x, y)/(1 − α) ≤ 2/d(x, y).
- graph_lly_curvature_le_of_lipschitz_cut_potentialKantorovich-duality bound on the Lin–Lu–Yau curvature at a pair: for x ≠ y and any 1-Lipschitz potential f with f(x) − f(y) = d(x,y),…
- graph_ollivier_curvature_div_monotoneOnIn a finite connected graph, for x ≠ y, α ↦ κ_α(x, y)/(1 − α) is nondecreasing on (0, 1).
The proof, explained
Because the graph G is connected, there exists a walk from x to y. Since x ≠ y, this walk cannot be the trivial empty walk, so it must start with an edge incident to x. The existence of an adjacent vertex implies that x has strictly positive degree.
There exists a walk p connecting x to y in G.
Since the graph G is connected, it is preconnected, guaranteeing the existence of a walk between any pair of vertices. We choose such a walk p from x to y.
obtain ⟨p⟩ := hG.preconnected x yThe walk p cannot be the trivial empty walk.
We split into cases on the structure of the walk p. If p were the empty walk (nil), its endpoints would coincide, meaning x = y. But this contradicts the hypothesis that x ≠ y (hxy).
cases p with | nil => exact absurd rfl hxy
The degree of x is strictly positive (0 < G.degree x).
In the non-empty case (cons), the walk begins with an edge h connecting x to some adjacent vertex. By G.degree_pos_iff_exists_adj, having an adjacent vertex implies that the degree of x is strictly positive.
uses
G.degree_pos_iff_exists_adj| cons h _ => exact (G.degree_pos_iff_exists_adj x).mpr ⟨_, h⟩
G.degree_pos_iff_exists_adj- A vertex in a simple graph has strictly positive degree if and only if there exists a vertex adjacent to it.
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 graph_degree_pos_of_connected_of_ne {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (x y : V) (hxy : x ≠ y) : 0 < G.degree x := by obtain ⟨p⟩ := hG.preconnected x y cases p with | nil => exact absurd rfl hxy | cons h _ => exact (G.degree_pos_iff_exists_adj x).mpr ⟨_, h⟩