AFTD Auto-Formalizing Theoretical Domains

tree_card_four_degree_two_count

theoremverified

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.

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

    lines 8–13

    uses Fintype.one_lt_card_iff_nontrivial.mp, SimpleGraph.degree_eq_zero

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

    lines 14–18

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

    lines 19–28

    uses Finset.disjoint_filter, Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and, iff_true_intro

      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)
  4. 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.

    lines 29–32

    uses Finset.card_union_of_disjoint, Finset.card_univ

      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
  5. 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₂|.

    lines 33–46

    uses Finset.sum_const_nat, mul_one, mul_comm, Finset.mem_filter, Finset.sum_union

      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]
  6. 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.

    lines 47–49

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

    lines 50–52

      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

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