simple_graph_is_tree_sum_choose_degree_eq_iff_path
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
- simple_graph_is_tree_card_sub_two_le_sum_choose_degree_le_chooseFor a tree T on k ≥ 2 vertices, σ₂(T) = ∑_v C(d_T(v),2) satisfies k − 2 ≤ σ₂(T) ≤ C(k−1,2).
- path_graph_degree_le_twoEvery vertex of the path graph P_k has degree at most 2.
- simple_graph_connected_degree_posIn a connected graph with at least two vertices every vertex has positive degree.
- simple_graph_is_tree_nonempty_iso_path_graph_of_degree_le_twoA finite tree in which every vertex has degree at most 2 is isomorphic to the path P_k, k = |V|.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- op223_tree_fin_four_iso_path_or_starEvery tree on four vertices is isomorphic either to the path graph on four vertices or to the star K_{1,3}.
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.
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).
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 ℤ
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.
uses
Finset.sum_sub_distrib,Finset.sum_const,Finset.card_univ,nsmul_eq_mul,mul_onehave 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
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.
uses
Nat.choose_succ_succ,Nat.choose_one_righthave 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
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.
uses
simple_graph_is_tree_nonempty_iso_path_graph_of_degree_le_twoconstructor · intro hsum apply simple_graph_is_tree_nonempty_iso_path_graph_of_degree_le_two G hT
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.
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
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.
uses
Finset.sum_eq_sum_iff_of_le,Finset.mem_univ,Nat.choose_succ_succ,Nat.choose_one_right,Nat.choose_poshave 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
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.
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 _ _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.
uses
simple_graph_connected_degree_pos,Finset.sum_le_sumhave 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
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.
uses
simple_graph_is_tree_card_sub_two_le_sum_choose_degree_le_choose,Nat.cast_sub,Int.ofNat_le.1have 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 ℕ.
- Several steps switch between natural numbers and integers to perform subtraction, using `omega` and `linarith` to discharge the inequality arithmetic automatically.
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 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