AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_tree_sum_choose_degree_eq_iff_path

theoremverifiedformalization

For a tree T on k ≥ 2 vertices, σ₂(T) = k − 2 if and only if T is isomorphic to the path P_k.

Statement

theorem simple_graph_is_tree_sum_choose_degree_eq_iff_path {V : Type*} [Fintype V]
    [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hT : G.IsTree)
    (hk : 2 ≤ Fintype.card V) :
    ∑ v, (G.degree v).choose 2 = Fintype.card V - 2 ↔
      Nonempty (G ≃g SimpleGraph.pathGraph (Fintype.card V))
Formalizes
arXiv:2610.12109 (Sharp linear Turán remainders for cycle and edge extremality), Lemma 2.5, equality case of the lower bound.
Verified
12 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
Used by 1

The proof, explained

For any tree T on k ≥ 2 vertices, the handshaking lemma and the tree edge relation |E| = k - 1 give ∑_v (d(v) - 1) = k - 2. The pointwise inequality d - 1 ≤ (d choose 2) holds for all degrees, with equality holding precisely when d ∈ {1, 2}. If ∑_v (d(v) choose 2) = k - 2, the two sums match, forcing equality at every vertex and hence maximum degree at most 2, which characterizes the path graph P_k. Conversely, if T ≃ P_k, all degrees are 1 or 2, which gives ∑_v (d(v) choose 2) ≤ k - 2; combined with the general lower bound k - 2 ≤ ∑_v (d(v) choose 2) for trees, equality follows.

  1. The sum of the degrees of the vertices of G is 2(|V| - 1).

    Since G is a tree, its edge count satisfies |E| + 1 = |V|, so |E| = |V| - 1. By the handshaking lemma, the sum of all vertex degrees equals 2|E| = 2(|V| - 1).

    lines 6–14

      classical
      have hE : G.edgeFinset.card + 1 = Fintype.card V := hT.card_edgeFinset
      have hsumdeg : (∑ v, (G.degree v : ℤ)) = 2 * (Fintype.card V - 1) := by
        have := G.sum_degrees_eq_twice_card_edges
        have h' : (∑ v, (G.degree v : ℤ)) = 2 * G.edgeFinset.card := by exact_mod_cast this
        rw [h']
        have : (G.edgeFinset.card : ℤ) + 1 = Fintype.card V := by exact_mod_cast hE
        linarith
      -- ∑ (d − 1) = k − 2 in ℤ
  2. The sum of (d(v) - 1) over all vertices v is |V| - 2.

    Distributing the sum over d(v) - 1 yields the sum of all degrees minus |V| times 1. Substituting the degree sum 2(|V| - 1) and simplifying gives 2|V| - 2 - |V| = |V| - 2.

    lines 15–18

    uses Finset.sum_sub_distrib, Finset.sum_const, Finset.card_univ, nsmul_eq_mul, mul_one

      have hsub1 : (∑ v, ((G.degree v : ℤ) - 1)) = Fintype.card V - 2 := by
        rw [Finset.sum_sub_distrib, hsumdeg]
        simp only [Finset.sum_const, Finset.card_univ, nsmul_eq_mul, mul_one]
        ring
  3. For every vertex v, d(v) - 1 ≤ (d(v) choose 2).

    We check the inequality by cases on the degree d = d(v). If d = 0, we have -1 ≤ 0. If d = m + 1, Pascal's identity gives (m + 1 choose 2) = m + (m choose 2), which is at least m = (m + 1) - 1 because (m choose 2) ≥ 0.

    lines 19–26

    uses Nat.choose_succ_succ, Nat.choose_one_right

      have hle : ∀ v, ((G.degree v : ℤ) - 1) ≤ ((G.degree v).choose 2 : ℤ) := by
        intro v
        generalize G.degree v = d
        rcases d with _ | m
        · simp
        · rw [Nat.choose_succ_succ, Nat.choose_one_right]
          push_cast
          omega
  4. To show that ∑_v (d(v) choose 2) = |V| - 2 implies G is isomorphic to the path graph P_|V|, it suffices to show that every vertex has degree at most 2.

    We split the theorem into the two implications. For the forward direction, we assume ∑_v (d(v) choose 2) = |V| - 2. A tree whose vertices all have degree at most 2 is known to be isomorphic to the path graph on |V| vertices.

    lines 27–29

    uses simple_graph_is_tree_nonempty_iso_path_graph_of_degree_le_two

      constructor
      · intro hsum
        apply simple_graph_is_tree_nonempty_iso_path_graph_of_degree_le_two G hT
  5. Under the forward assumption, the sum of (d(v) choose 2) equals the sum of (d(v) - 1).

    Both ∑_v (d(v) choose 2) and ∑_v (d(v) - 1) equal |V| - 2, so the two integer sums are equal.

    lines 30–36

        have hz : (∑ v, ((G.degree v).choose 2 : ℤ)) = ∑ v, ((G.degree v : ℤ) - 1) := by
          rw [hsub1]
          have : ((∑ v, (G.degree v).choose 2 : ℕ) : ℤ) = ((Fintype.card V - 2 : ℕ) : ℤ) := by
            rw [hsum]
          push_cast at this
          rw [this]
          omega
  6. Every vertex v of G satisfies d(v) ≤ 2.

    Since d(v) - 1 ≤ (d(v) choose 2) holds for all v and their sums over all vertices are equal, equality must hold term-by-term: d(v) - 1 = (d(v) choose 2) for each v. If some vertex had degree d(v) ≥ 3, say d(v) = m + 3, then (m + 3 choose 2) = m + 2 + (m + 2 choose 2). Since m + 2 ≥ 2, the term (m + 2 choose 2) is strictly positive, forcing (d(v) choose 2) > m + 2 = d(v) - 1, which contradicts equality. Thus d(v) ≤ 2 for all v.

    lines 37–46

    uses Finset.sum_eq_sum_iff_of_le, Finset.mem_univ, Nat.choose_succ_succ, Nat.choose_one_right, Nat.choose_pos

        have heach := (Finset.sum_eq_sum_iff_of_le (fun v _ => hle v)).1 hz.symm
        intro v
        have hv := heach v (Finset.mem_univ v)
        by_contra hlt
        push Not at hlt
        obtain ⟨m, hm⟩ : ∃ m, G.degree v = m + 3 := ⟨G.degree v - 3, by omega⟩
        rw [hm, Nat.choose_succ_succ, Nat.choose_one_right] at hv
        have hpos : 0 < (m + 2).choose 2 := Nat.choose_pos (by omega)
        push_cast at hv
        omega
  7. Assuming G is isomorphic to the path graph P_|V|, every vertex v has degree at most 2.

    An isomorphism f from G to P_|V| restricts to an injection from the neighbor set of v to that of f(v), so d(v) ≤ d(f(v)). Since every vertex in a path graph has degree at most 2, we conclude d(v) ≤ 2.

    lines 47–59

    uses SimpleGraph.card_neighborFinset_eq_degree, Finset.card_le_card_of_injOn, Finset.mem_coe, SimpleGraph.mem_neighborFinset, path_graph_degree_le_two

      · rintro ⟨f⟩
        have hdeg2 : ∀ v, G.degree v ≤ 2 := by
          intro v
          calc G.degree v ≤ (SimpleGraph.pathGraph (Fintype.card V)).degree (f v) := by
                rw [← SimpleGraph.card_neighborFinset_eq_degree,
                  ← SimpleGraph.card_neighborFinset_eq_degree]
                apply Finset.card_le_card_of_injOn f
                · intro w hw
                  rw [Finset.mem_coe, SimpleGraph.mem_neighborFinset] at hw ⊢
                  exact f.map_adj_iff.2 hw
                · intro w _ w' _ h
                  exact f.injective h
            _ ≤ 2 := path_graph_degree_le_two _ _
  8. The sum of (d(v) choose 2) is at most the sum of (d(v) - 1).

    Because G is connected and has at least two vertices, every vertex has degree at least 1. Together with d(v) ≤ 2, each vertex degree is either 1 or 2. Direct computation shows that (1 choose 2) = 0 ≤ 1 - 1 and (2 choose 2) = 1 ≤ 2 - 1. Summing this pointwise inequality over all vertices gives the result.

    lines 60–67

    uses simple_graph_connected_degree_pos, Finset.sum_le_sum

        have hpos : ∀ v, 0 < G.degree v := simple_graph_connected_degree_pos G hT.1 hk
        have hz : (∑ v, ((G.degree v).choose 2 : ℤ)) ≤ ∑ v, ((G.degree v : ℤ) - 1) := by
          apply Finset.sum_le_sum
          intro v _
          have h1 := hdeg2 v
          have h2 := hpos v
          generalize G.degree v = d at h1 h2
          interval_cases d <;> simp
  9. The sum of (d(v) choose 2) equals |V| - 2.

    By a general property of trees on at least two vertices, |V| - 2 ≤ ∑_v (d(v) choose 2). Combined with the upper bound ∑_v (d(v) choose 2) ≤ ∑_v (d(v) - 1) = |V| - 2 from the previous step, the sum is sandwiched and must equal |V| - 2.

    lines 68–76

    uses simple_graph_is_tree_card_sub_two_le_sum_choose_degree_le_choose, Nat.cast_sub, Int.ofNat_le.1

        have hlow := (simple_graph_is_tree_card_sub_two_le_sum_choose_degree_le_choose G hT hk).1
        rw [hsub1] at hz
        have : ((∑ v, (G.degree v).choose 2 : ℕ) : ℤ) ≤ ((Fintype.card V - 2 : ℕ) : ℤ) := by
          push_cast
          rw [Nat.cast_sub hk]
          push_cast
          exact hz
        have := Int.ofNat_le.1 this
        omega
Finset.sum_sub_distrib
The sum of a difference of functions over a finite set equals the difference of the sums.
Finset.sum_const
Summing a constant b over a finite set s yields |s| • b.
Finset.card_univ
The cardinality of the universal finset of a finite type is the cardinality of the type.
nsmul_eq_mul
Scalar multiplication by a natural number n coincides with multiplication by n.
mul_one
Multiplying any element by 1 yields the element itself.
Nat.choose_succ_succ
Pascal's identity for binomial coefficients: (n + 1 choose k + 1) = (n choose k) + (n choose k + 1).
Nat.choose_one_right
For any natural number n, (n choose 1) = n.
simple_graph_is_tree_nonempty_iso_path_graph_of_degree_le_two
A tree on a finite vertex set whose vertex degrees are all at most 2 is isomorphic to the path graph on that many vertices.
Finset.sum_eq_sum_iff_of_le
If f(i) ≤ g(i) for all elements i in a finite set, then their sums are equal if and only if f(i) = g(i) for every element.
Finset.mem_univ
Every element of a finite type belongs to Finset.univ.
Nat.choose_pos
For k ≤ n, the binomial coefficient (n choose k) is strictly positive.
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 map from finset s to finset t is injective on s, then |s| ≤ |t|.
Finset.mem_coe
Coercion from finset to set preserves membership.
SimpleGraph.mem_neighborFinset
A vertex w is in the neighbor finset of v if and only if v and w are adjacent.
path_graph_degree_le_two
Every vertex in the path graph on k vertices has degree at most 2.
simple_graph_connected_degree_pos
In a connected simple graph with at least 2 vertices, every vertex has degree strictly greater than 0.
Finset.sum_le_sum
If f(i) ≤ g(i) for all i in a finite set, then the sum of f is at most the sum of g.
simple_graph_is_tree_card_sub_two_le_sum_choose_degree_le_choose
For any tree on k ≥ 2 vertices, k - 2 ≤ ∑_v (d(v) choose 2) ≤ (k - 1 choose 2).
Nat.cast_sub
For m ≤ n in ℕ, the integer cast of n - m equals the difference of the integer casts.
Int.ofNat_le.1
If the integer casts of two natural numbers satisfy (a : ℤ) ≤ (b : ℤ), then a ≤ b in ℕ.

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_is_tree_sum_choose_degree_eq_iff_path {V : Type*} [Fintype V]    [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hT : G.IsTree)    (hk : 2 ≤ Fintype.card V) :    ∑ v, (G.degree v).choose 2 = Fintype.card V - 2 ↔      Nonempty (G ≃g SimpleGraph.pathGraph (Fintype.card V)) := by  classical  have hE : G.edgeFinset.card + 1 = Fintype.card V := hT.card_edgeFinset  have hsumdeg : (∑ v, (G.degree v : ℤ)) = 2 * (Fintype.card V - 1) := by    have := G.sum_degrees_eq_twice_card_edges    have h' : (∑ v, (G.degree v : ℤ)) = 2 * G.edgeFinset.card := by exact_mod_cast this    rw [h']    have : (G.edgeFinset.card : ℤ) + 1 = Fintype.card V := by exact_mod_cast hE    linarith  -- ∑ (d − 1) = k − 2 in ℤ  have hsub1 : (∑ v, ((G.degree v : ℤ) - 1)) = Fintype.card V - 2 := by    rw [Finset.sum_sub_distrib, hsumdeg]    simp only [Finset.sum_const, Finset.card_univ, nsmul_eq_mul, mul_one]    ring  have hle : ∀ v, ((G.degree v : ℤ) - 1) ≤ ((G.degree v).choose 2 : ℤ) := by    intro v    generalize G.degree v = d    rcases d with _ | m    · simp    · rw [Nat.choose_succ_succ, Nat.choose_one_right]      push_cast      omega  constructor  · intro hsum    apply simple_graph_is_tree_nonempty_iso_path_graph_of_degree_le_two G hT    have hz : (∑ v, ((G.degree v).choose 2 : ℤ)) = ∑ v, ((G.degree v : ℤ) - 1) := by      rw [hsub1]      have : ((∑ v, (G.degree v).choose 2 : ℕ) : ℤ) = ((Fintype.card V - 2 : ℕ) : ℤ) := by        rw [hsum]      push_cast at this      rw [this]      omega    have heach := (Finset.sum_eq_sum_iff_of_le (fun v _ => hle v)).1 hz.symm    intro v    have hv := heach v (Finset.mem_univ v)    by_contra hlt    push Not at hlt    obtain ⟨m, hm⟩ : ∃ m, G.degree v = m + 3 := ⟨G.degree v - 3, by omega⟩    rw [hm, Nat.choose_succ_succ, Nat.choose_one_right] at hv    have hpos : 0 < (m + 2).choose 2 := Nat.choose_pos (by omega)    push_cast at hv    omega  · rintro ⟨f⟩    have hdeg2 : ∀ v, G.degree v ≤ 2 := by      intro v      calc G.degree v ≤ (SimpleGraph.pathGraph (Fintype.card V)).degree (f v) := by            rw [← SimpleGraph.card_neighborFinset_eq_degree,              ← SimpleGraph.card_neighborFinset_eq_degree]            apply Finset.card_le_card_of_injOn f            · intro w hw              rw [Finset.mem_coe, SimpleGraph.mem_neighborFinset] at hw ⊢              exact f.map_adj_iff.2 hw            · intro w _ w' _ h              exact f.injective h        _ ≤ 2 := path_graph_degree_le_two _ _    have hpos : ∀ v, 0 < G.degree v := simple_graph_connected_degree_pos G hT.1 hk    have hz : (∑ v, ((G.degree v).choose 2 : ℤ)) ≤ ∑ v, ((G.degree v : ℤ) - 1) := by      apply Finset.sum_le_sum      intro v _      have h1 := hdeg2 v      have h2 := hpos v      generalize G.degree v = d at h1 h2      interval_cases d <;> simp    have hlow := (simple_graph_is_tree_card_sub_two_le_sum_choose_degree_le_choose G hT hk).1    rw [hsub1] at hz    have : ((∑ v, (G.degree v).choose 2 : ℕ) : ℤ) ≤ ((Fintype.card V - 2 : ℕ) : ℤ) := by      push_cast      rw [Nat.cast_sub hk]      push_cast      exact hz    have := Int.ofNat_le.1 this    omega
See it in the graphDiscuss this resultChallenge it