AFTD Auto-Formalizing Theoretical Domains

graph_degree_pos_of_connected_of_ne

theoremverified

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

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.

  1. 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.

    line 4

      obtain ⟨p⟩ := hG.preconnected x y
  2. The 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).

    lines 5–6

      cases p with
      | nil => exact absurd rfl hxy
  3. 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.

    line 7

    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

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⟩
See it in the graphDiscuss this resultChallenge it