AFTD Auto-Formalizing Theoretical Domains

simple_graph_connected_degree_pos

theoremverified

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

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.

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

    lines 4–5

    uses Fintype.exists_ne_of_one_lt_card

      obtain ⟨w, hw⟩ := Fintype.exists_ne_of_one_lt_card (by omega) v
      obtain ⟨p⟩ := hconn.preconnected v w
  2. 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.

    lines 6–7

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

    lines 8–10

    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

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