tree_card_four_degree_two_count
In a tree on 4 vertices with all degrees at most 2, exactly two vertices have degree 2 and two vertices have degree 1.
Statement
theorem tree_card_four_degree_two_count {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) [DecidableRel T.Adj] (hT : T.IsTree) (hcard : Fintype.card V = 4) (hdeg : ∀ v : V, T.degree v ≤ 2) : (Finset.univ.filter (fun v => T.degree v = 2)).card = 2 ∧ (Finset.univ.filter (fun v => T.degree v = 1)).card = 2
- Source
- step towards tree_card_four_iso_of_degree_le_two
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- tree_card_four_path_edgesAny tree on 4 vertices with all degrees at most 2 has an ordering (a, b, c, d) of its 4 vertices such that edges are precisely (a,b),…
The proof, explained
The proof partitions the vertices of the tree into the set S₁ of degree-1 vertices and the set S₂ of degree-2 vertices. Because the graph is a connected tree on 4 vertices, no vertex can be isolated, so every vertex has degree 1 or 2, which gives |S₁| + |S₂| = 4. Since a tree on 4 vertices has 3 edges, the handshake lemma implies that the sum of all degrees is |S₁| + 2|S₂| = 2 * 3 = 6. Solving this system of two linear equations in two unknowns uniquely yields |S₂| = 2 and |S₁| = 2.
No vertex has degree 0.
Because the vertex set V has cardinality 4, it has strictly more than 1 element, making V nontrivial via Fintype.one_lt_card_iff_nontrivial.mp. In any connected graph on a nontrivial vertex set, no vertex can be isolated. Since having degree 0 is equivalent to being isolated by SimpleGraph.degree_eq_zero, every vertex must have non-zero degree.
uses
Fintype.one_lt_card_iff_nontrivial.mp,SimpleGraph.degree_eq_zerohave h_nontriv : Nontrivial V := Fintype.one_lt_card_iff_nontrivial.mp (by omega) have h_ne_zero : ∀ v : V, T.degree v ≠ 0 := by intro v h0 have h_iso : ¬ T.IsIsolated v := hT.connected.preconnected.not_isIsolated v rw [SimpleGraph.degree_eq_zero] at h0 exact h_iso h0
Every vertex has degree either 1 or 2.
By assumption, every vertex has degree at most 2, and by the previous step, no vertex has degree 0. The only natural numbers satisfying these conditions are 1 and 2.
have h_deg_cases : ∀ v : V, T.degree v = 1 ∨ T.degree v = 2 := by intro v have h1 := hdeg v have h2 := h_ne_zero v omega
The sets S₁ (vertices of degree 1) and S₂ (vertices of degree 2) partition the vertex set.
Let S₁ = {v ∈ V | deg(v) = 1} and S₂ = {v ∈ V | deg(v) = 2}. By Finset.disjoint_filter, S₁ and S₂ are disjoint because no vertex can have degree both 1 and 2. Furthermore, their union is the entire vertex set V because every vertex has degree 1 or 2.
uses
Finset.disjoint_filter,Finset.mem_union,Finset.mem_filter,Finset.mem_univ,true_and,iff_true_introlet S1 := Finset.univ.filter (fun v => T.degree v = 1) let S2 := Finset.univ.filter (fun v => T.degree v = 2) have hd : Disjoint S1 S2 := by rw [Finset.disjoint_filter] intro x _ hx1 hx2 omega have hu : S1 ∪ S2 = Finset.univ := by ext x simp only [Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and, S1, S2] exact iff_true_intro (h_deg_cases x)
The sizes of S₁ and S₂ sum to 4 (|S₁| + |S₂| = 4).
Since S₁ and S₂ are disjoint and their union is Finset.univ, Finset.card_union_of_disjoint shows that |S₁ ∪ S₂| = |S₁| + |S₂|. Using Finset.card_univ and the assumption that |V| = 4, this gives |S₁| + |S₂| = 4.
uses
Finset.card_union_of_disjoint,Finset.card_univhave h_card_sum : S1.card + S2.card = 4 := by have := Finset.card_union_of_disjoint hd rw [hu, Finset.card_univ, hcard] at this exact this.symm
The sum of all vertex degrees is |S₁| + 2|S₂|.
Summing the vertex degrees over all of V is equivalent to summing over S₁ ∪ S₂. By Finset.sum_union, this splits into the sum over S₁ plus the sum over S₂. On S₁, the degree is constantly 1, so Finset.sum_const_nat and mul_one evaluate that sum to |S₁|. On S₂, the degree is constantly 2, so Finset.sum_const_nat and mul_comm evaluate that sum to 2|S₂|.
uses
Finset.sum_const_nat,mul_one,mul_comm,Finset.mem_filter,Finset.sum_unionhave hs : ∑ v : V, T.degree v = ∑ v ∈ S1 ∪ S2, T.degree v := by rw [hu] have s1 : ∑ v ∈ S1, T.degree v = S1.card := by rw [Finset.sum_const_nat (m := 1), mul_one] intro x hx simp only [S1, Finset.mem_filter] at hx exact hx.2 have s2 : ∑ v ∈ S2, T.degree v = 2 * S2.card := by rw [Finset.sum_const_nat (m := 2), mul_comm] intro x hx simp only [S2, Finset.mem_filter] at hx exact hx.2 have h_deg_sum : ∑ v : V, T.degree v = S1.card + 2 * S2.card := by rw [hs, Finset.sum_union hd, s1, s2]
The sum of all vertex degrees in the tree is 6.
In a tree on n vertices, the number of edges is n - 1 (hT.card_edgeFinset), which gives 4 - 1 = 3 edges here. By Euler's handshake lemma (T.sum_degrees_eq_twice_card_edges), the sum of all vertex degrees is twice the number of edges, 2 * 3 = 6.
have h_edge := hT.card_edgeFinset have h_handshake := T.sum_degrees_eq_twice_card_edges have h_total : ∑ v : V, T.degree v = 6 := by omega
The system of equations uniquely determines that |S₂| = 2 and |S₁| = 2.
We have the two linear equations |S₁| + |S₂| = 4 and |S₁| + 2|S₂| = 6. Subtracting the first from the second gives |S₂| = 2, and substituting back gives |S₁| = 2. Combining these two values establishes the theorem.
have h_s2 : S2.card = 2 := by omega have h_s1 : S1.card = 2 := by omega exact ⟨h_s2, h_s1⟩
Fintype.one_lt_card_iff_nontrivial.mp- A finite type with cardinality strictly greater than 1 is nontrivial (contains at least two distinct elements).
SimpleGraph.degree_eq_zero- A vertex in a simple graph has degree 0 if and only if it is isolated (has no incident edges).
Finset.disjoint_filter- Filtering a finite set by two predicates yields disjoint subsets if and only if no element satisfies both predicates.
Finset.mem_union- An element belongs to the union of two finite sets if and only if it belongs to at least one of them.
Finset.mem_filter- An element belongs to a filtered finite set if and only if it belongs to the set and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal set Finset.univ.
true_and- The conjunction of True with any proposition p is logically equivalent to p.
iff_true_intro- If a proposition is true, it is logically equivalent to True.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_univ- The cardinality of Finset.univ is equal to the cardinality of the underlying finite type.
Finset.sum_const_nat- The sum over a finite set of a function that is constantly equal to m is equal to the set's cardinality times m.
mul_one- Multiplying an element by 1 on the right leaves it unchanged.
mul_comm- Multiplication is commutative (a * b = b * a).
Finset.sum_union- The sum of a function over the union of two disjoint finite sets is the sum of the sums over each set.
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.
/-- In a tree on 4 vertices with all degrees at most 2, exactly two vertices have degree 2 and two vertices have degree 1. -/theorem tree_card_four_degree_two_count {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) [DecidableRel T.Adj] (hT : T.IsTree) (hcard : Fintype.card V = 4) (hdeg : ∀ v : V, T.degree v ≤ 2) : (Finset.univ.filter (fun v => T.degree v = 2)).card = 2 ∧ (Finset.univ.filter (fun v => T.degree v = 1)).card = 2 := by have h_nontriv : Nontrivial V := Fintype.one_lt_card_iff_nontrivial.mp (by omega) have h_ne_zero : ∀ v : V, T.degree v ≠ 0 := by intro v h0 have h_iso : ¬ T.IsIsolated v := hT.connected.preconnected.not_isIsolated v rw [SimpleGraph.degree_eq_zero] at h0 exact h_iso h0 have h_deg_cases : ∀ v : V, T.degree v = 1 ∨ T.degree v = 2 := by intro v have h1 := hdeg v have h2 := h_ne_zero v omega let S1 := Finset.univ.filter (fun v => T.degree v = 1) let S2 := Finset.univ.filter (fun v => T.degree v = 2) have hd : Disjoint S1 S2 := by rw [Finset.disjoint_filter] intro x _ hx1 hx2 omega have hu : S1 ∪ S2 = Finset.univ := by ext x simp only [Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and, S1, S2] exact iff_true_intro (h_deg_cases x) have h_card_sum : S1.card + S2.card = 4 := by have := Finset.card_union_of_disjoint hd rw [hu, Finset.card_univ, hcard] at this exact this.symm have hs : ∑ v : V, T.degree v = ∑ v ∈ S1 ∪ S2, T.degree v := by rw [hu] have s1 : ∑ v ∈ S1, T.degree v = S1.card := by rw [Finset.sum_const_nat (m := 1), mul_one] intro x hx simp only [S1, Finset.mem_filter] at hx exact hx.2 have s2 : ∑ v ∈ S2, T.degree v = 2 * S2.card := by rw [Finset.sum_const_nat (m := 2), mul_comm] intro x hx simp only [S2, Finset.mem_filter] at hx exact hx.2 have h_deg_sum : ∑ v : V, T.degree v = S1.card + 2 * S2.card := by rw [hs, Finset.sum_union hd, s1, s2] have h_edge := hT.card_edgeFinset have h_handshake := T.sum_degrees_eq_twice_card_edges have h_total : ∑ v : V, T.degree v = 6 := by omega have h_s2 : S2.card = 2 := by omega have h_s1 : S1.card = 2 := by omega exact ⟨h_s2, h_s1⟩