AFTD Auto-Formalizing Theoretical Domains

path_graph_degree_le_two

theoremverified

Every vertex of the path graph P_k has degree at most 2.

Statement

theorem path_graph_degree_le_two (k : ℕ) [DecidableRel (SimpleGraph.pathGraph k).Adj]
    (i : Fin k) : (SimpleGraph.pathGraph k).degree i ≤ 2
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

The degree of a vertex i in the path graph P_k is the number of its neighbors. By definition of adjacency in P_k, any neighbor j must satisfy j = i - 1 or j = i + 1 as natural numbers. We embed the neighbor set of i injectively into the two-element set of natural numbers {i - 1, i + 1}, bounding the degree by |{i - 1, i + 1}|. Since every two-element set has cardinality at most 2, the degree is at most 2.

  1. The degree of vertex i equals the cardinality of its neighbor finset, so it suffices to show that |N(i)| ≤ 2.

    After enabling classical reasoning for decidability, SimpleGraph.card_neighborFinset_eq_degree rewrites the degree of i as the cardinality of its neighbor finset.

    lines 3–4

    uses SimpleGraph.card_neighborFinset_eq_degree

      classical
      rw [← SimpleGraph.card_neighborFinset_eq_degree]
  2. The number of neighbors of i is at most the cardinality of {i - 1, i + 1} in ℕ.

    By Finset.card_le_card_of_injOn, an injective map from a finite set into another bounds its cardinality. We embed the neighbor finset into ℕ by sending each vertex to its underlying natural number. First, any neighbor j satisfies i + 1 = j or j + 1 = i by SimpleGraph.pathGraph_adj, which implies j = i - 1 or j = i + 1, so the map lands in {i - 1, i + 1}. Second, the map is injective because vertices in Fin k with identical natural values are equal by Fin.ext.

    lines 5–14

    uses Finset.card_le_card_of_injOn, Finset.mem_coe, SimpleGraph.mem_neighborFinset, SimpleGraph.pathGraph_adj, Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff, Set.mem_singleton_iff, Fin.ext

      calc ((SimpleGraph.pathGraph k).neighborFinset i).card
          ≤ ({(i : ℕ) - 1, (i : ℕ) + 1} : Finset ℕ).card := by
            apply Finset.card_le_card_of_injOn (fun j : Fin k => (j : ℕ))
            · intro j hj
              rw [Finset.mem_coe, SimpleGraph.mem_neighborFinset, SimpleGraph.pathGraph_adj] at hj
              simp only [Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff,
                Set.mem_singleton_iff]
              omega
            · intro j _ j' _ h
              exact Fin.ext h
  3. The degree of vertex i is at most 2.

    By Finset.card_le_two, any pair set {a, b} has at most two elements. Chaining this with the inequality |N(i)| ≤ |{i - 1, i + 1}| completes the proof.

    line 15

    uses Finset.card_le_two

        _ ≤ 2 := Finset.card_le_two
SimpleGraph.card_neighborFinset_eq_degree
The degree of a vertex in a simple graph equals the cardinality of its neighbor finset.
Finset.card_le_card_of_injOn
If a function maps a finite set s into a finite set t and is injective on s, then the cardinality of s is at most that of t.
Finset.mem_coe
An element belongs to the coercion of a finset to a set if and only if it belongs to the finset.
SimpleGraph.mem_neighborFinset
A vertex w belongs to the neighbor finset of v if and only if v and w are adjacent.
SimpleGraph.pathGraph_adj
In the path graph on n vertices, two vertices u and v are adjacent if and only if u + 1 = v or v + 1 = u.
Finset.coe_insert
Coercing the insertion of an element into a finset to a set equals inserting the element into the coerced set.
Finset.coe_singleton
Coercing a singleton finset to a set yields the singleton set.
Set.mem_insert_iff
An element belongs to insert a s if and only if it equals a or belongs to s.
Set.mem_singleton_iff
An element belongs to the singleton set {b} if and only if it equals b.
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
Finset.card_le_two
Any finite set of the form {a, b} has cardinality at most 2.

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 path_graph_degree_le_two (k : ℕ) [DecidableRel (SimpleGraph.pathGraph k).Adj]    (i : Fin k) : (SimpleGraph.pathGraph k).degree i ≤ 2 := by  classical  rw [← SimpleGraph.card_neighborFinset_eq_degree]  calc ((SimpleGraph.pathGraph k).neighborFinset i).card      ≤ ({(i : ℕ) - 1, (i : ℕ) + 1} : Finset ℕ).card := by        apply Finset.card_le_card_of_injOn (fun j : Fin k => (j : ℕ))        · intro j hj          rw [Finset.mem_coe, SimpleGraph.mem_neighborFinset, SimpleGraph.pathGraph_adj] at hj          simp only [Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff,            Set.mem_singleton_iff]          omega        · intro j _ j' _ h          exact Fin.ext h    _ ≤ 2 := Finset.card_le_two
See it in the graphDiscuss this resultChallenge it