AFTD Auto-Formalizing Theoretical Domains

tree_card_four_iso_of_exists_degree_three

theoremverified

Any two trees on 4 vertices each possessing a vertex of degree 3 are isomorphic.

Statement

theorem tree_card_four_iso_of_exists_degree_three {V₁ V₂ : Type*} [Fintype V₁] [DecidableEq V₁] [Fintype V₂] [DecidableEq V₂]
    (T₁ : SimpleGraph V₁) (T₂ : SimpleGraph V₂) [DecidableRel T₁.Adj] [DecidableRel T₂.Adj]
    (hT₁ : T₁.IsTree) (hT₂ : T₂.IsTree) (hcard₁ : Fintype.card V₁ = 4) (hcard₂ : Fintype.card V₂ = 4)
    (hv₁ : ∃ v : V₁, T₁.degree v = 3) (hv₂ : ∃ v : V₂, T₂.degree v = 3) :
    Nonempty (T₁ ≃g T₂)
Source
step towards caterpillar_third_t_chromatic_specialization_fiber_le_two
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

To prove that any two trees on 4 vertices each possessing a vertex of degree 3 are isomorphic, we first show that in a 4-vertex graph, a degree-3 vertex is adjacent to all other vertices. Next, we show that trees have no triangles (which would create two paths of different lengths between the same endpoints), so neither tree can have edges between any other vertices; that is, both trees are star graphs K_{1,3} centered at their respective degree-3 vertices. Finally, because the vertex sets both have cardinality 4, we take a bijection between them, adjust it by a transposition to send the center of the first tree to the center of the second, and verify that this adjusted bijection preserves the adjacency relation, yielding a graph isomorphism.

  1. In a 4-vertex graph, the neighborhood of a degree-3 vertex v is the entire set of other vertices V \ {v}.

    The neighbor finset of v is a subset of V \ {v} because simple graphs have no self-loops. Since |V| = 4, the complement V \ {v} has cardinality 4 - 1 = 3. Because v has degree 3, its neighbor finset also has cardinality 3. A subset with the same cardinality as the ambient finite set must equal the entire set.

    lines 5–17

    uses Finset.mem_erase, Finset.mem_univ, and_true, SimpleGraph.mem_neighborFinset, Finset.card_erase_of_mem, Finset.card_univ, SimpleGraph.card_neighborFinset_eq_degree, Finset.eq_of_subset_of_card_le

      intro w hw
      have hsub : G.neighborFinset v ⊆ Finset.univ.erase v := by
        intro u hu
        simp only [Finset.mem_erase, Finset.mem_univ, and_true]
        rw [SimpleGraph.mem_neighborFinset] at hu
        exact hu.ne'
      have hcard1 : (Finset.univ.erase v).card = 3 := by
        rw [Finset.card_erase_of_mem (Finset.mem_univ v)]
        rw [Finset.card_univ, hcard]
      have hcard2 : (G.neighborFinset v).card = 3 := by
        rw [SimpleGraph.card_neighborFinset_eq_degree, hdeg]
      have heq : G.neighborFinset v = Finset.univ.erase v :=
        Finset.eq_of_subset_of_card_le hsub (by rw [hcard1, hcard2])
  2. Any vertex w ≠ v is adjacent to v.

    Since w ≠ v, w belongs to V \ {v}. Because the neighborhood of v equals V \ {v}, w belongs to the neighborhood of v, which means v and w are adjacent.

    lines 18–22

    uses Finset.mem_erase, Finset.mem_univ, and_true, SimpleGraph.mem_neighborFinset

      have hw_mem : w ∈ Finset.univ.erase v := by
        simp only [Finset.mem_erase, Finset.mem_univ, and_true]
        exact hw
      rw [← heq] at hw_mem
      rwa [SimpleGraph.mem_neighborFinset] at hw_mem
  3. If v, x, and y form a triangle in a tree, there are two paths from v to x with lengths 1 and 2.

    In a tree, there is a unique path between any two vertices. If v, x, y are mutually adjacent, the single edge (v, x) forms a path of length 1, while the walk (v, y, x) forms a path of length 2 because v, y, x are pairwise distinct.

    lines 26–33

    uses SimpleGraph.Walk.cons_isPath_iff

      have hyx := hxy.symm
      obtain ⟨p, hp, huniq⟩ := hG.existsUnique_path v x
      have hp1 : (SimpleGraph.Walk.cons hvx SimpleGraph.Walk.nil).IsPath := by
        simp [hvx.ne]
      have hp2 : (SimpleGraph.Walk.cons hvy (SimpleGraph.Walk.cons hyx SimpleGraph.Walk.nil)).IsPath := by
        rw [SimpleGraph.Walk.cons_isPath_iff]
        refine ⟨by simp [hyx.ne], ?_⟩
        simp [hvy.ne, hvx.ne]
  4. A tree contains no triangle.

    By the uniqueness of paths in a tree, both the path of length 1 and the path of length 2 between v and x must equal the unique path p. Therefore their lengths are equal, giving 1 = 2, which simplifies to a contradiction.

    lines 34–39

      have e1 := huniq _ hp1
      have e2 := huniq _ hp2
      have hlen : (SimpleGraph.Walk.cons hvx SimpleGraph.Walk.nil).length =
                  (SimpleGraph.Walk.cons hvy (SimpleGraph.Walk.cons hyx SimpleGraph.Walk.nil)).length := by
        rw [e1, e2]
      simp at hlen
  5. In a tree where v is adjacent to all other vertices, if x and y are adjacent, then x ≠ y and at least one of x or y is v.

    Adjacent vertices in a simple graph must be distinct. If neither x nor y were v, then v would be adjacent to both x and y, forming a triangle with vertices v, x, y, which contradicts the lemma that trees have no triangles.

    lines 44–50

    uses Or.inl, Or.inr, tree_card_four_iso_of_exists_degree_three_no_triangle

      constructor
      · intro h
        refine ⟨h.ne, ?_⟩
        by_contra hc
        have h1 : x ≠ v := fun hx => hc (Or.inl hx)
        have h2 : y ≠ v := fun hy => hc (Or.inr hy)
        exact tree_card_four_iso_of_exists_degree_three_no_triangle hG (hv x h1) (hv y h2) h
  6. In such a tree, two vertices are adjacent if and only if they are distinct and at least one of them is v.

    For the converse direction, if x ≠ y and either x = v or y = v, the two vertices are adjacent directly by the hypothesis that v is adjacent to all other vertices (using symmetry of adjacency if y = v).

    lines 51–53

      · rintro ⟨hne, rfl | rfl⟩
        · exact hv y hne.symm
        · exact (hv x hne).symm
  7. In both trees T₁ and T₂, adjacency is completely characterized by being distinct and incident to the degree-3 center vertex.

    Let v₁ and v₂ be the assumed degree-3 vertices in T₁ and T₂, respectively. By the auxiliary lemma, each is adjacent to all other vertices in its 4-vertex tree. Applying the adjacency characterization lemma, two vertices in T₁ (respectively T₂) are adjacent if and only if they are distinct and at least one is v₁ (respectively v₂).

    lines 61–66

    uses tree_card_four_iso_of_exists_degree_three_aux, tree_card_four_iso_of_exists_degree_three_aux_adj

      obtain ⟨v₁, hv₁⟩ := hv₁
      obtain ⟨v₂, hv₂⟩ := hv₂
      have hadj₁ := tree_card_four_iso_of_exists_degree_three_aux T₁ hcard₁ hv₁
      have hadj₂ := tree_card_four_iso_of_exists_degree_three_aux T₂ hcard₂ hv₂
      have key₁ := tree_card_four_iso_of_exists_degree_three_aux_adj T₁ hT₁ hadj₁
      have key₂ := tree_card_four_iso_of_exists_degree_three_aux_adj T₂ hT₂ hadj₂
  8. There exists a bijection E between the vertex sets V₁ and V₂.

    Because both V₁ and V₂ have cardinality 4, they have equal finite cardinality, which is equivalent to the existence of a bijection E : V₁ ≃ V₂.

    lines 67–69

    uses Fintype.card_eq

      obtain ⟨E⟩ : Nonempty (V₁ ≃ V₂) := by
        rw [← Fintype.card_eq]
        rw [hcard₁, hcard₂]
  9. The modified bijection f = swap(E(v₁), v₂) ∘ E maps v₁ to v₂, reflects v₂, and is injective.

    Composing E with the transposition swapping E(v₁) and v₂ gives a bijection f : V₁ ≃ V₂ that maps v₁ to v₂. By properties of transpositions and injectivity of E, f(x) = v₂ holds if and only if x = v₁. Moreover, because f is an equivalence, it reflects equality: f(x) = f(y) if and only if x = y.

    lines 70–77

    uses Equiv.swap_apply_eq_iff, Equiv.swap_apply_right, Equiv.injective

      have hex : ∀ x : V₁, E.trans (Equiv.swap (E v₁) v₂) x = v₂ ↔ x = v₁ := by
        intro x
        show Equiv.swap (E v₁) v₂ (E x) = v₂ ↔ x = v₁
        rw [Equiv.swap_apply_eq_iff, Equiv.swap_apply_right, E.injective.eq_iff]
      have hne : ∀ x y : V₁, (E.trans (Equiv.swap (E v₁) v₂) x
          = E.trans (Equiv.swap (E v₁) v₂) y ↔ x = y) := by
        intro x y
        exact (Equiv.injective _).eq_iff
  10. The trees T₁ and T₂ are isomorphic.

    We package f into a graph isomorphism RelIso. Adjacency in T₂ between f(x) and f(y) is equivalent to f(x) ≠ f(y) and (f(x) = v₂ ∨ f(y) = v₂). Substituting f(x) ≠ f(y) ↔ x ≠ y and f(z) = v₂ ↔ z = v₁ converts this into x ≠ y and (x = v₁ ∨ y = v₁), which is the exact condition for adjacency in T₁.

    lines 78–80

    uses RelIso.mk, ne_eq

      refine ⟨RelIso.mk (E.trans (Equiv.swap (E v₁) v₂)) ?_⟩
      intro x y
      rw [key₂, key₁, hex x, hex y, ne_eq, ne_eq, hne x y]
and_true
Conjunction of any proposition p with True is equivalent to p.
Equiv.swap_apply_eq_iff
Under the transposition swapping x and y, the image of z is w if and only if z is the image of w.
Equiv.swap_apply_right
The transposition swapping a and b maps b to a.
Equiv.injective
Any equivalence between types is an injective function.
Fintype.card_eq
Two finite types have the same cardinality if and only if there exists a bijection between them.
Finset.card_erase_of_mem
Removing an element a from a finset s decreases its cardinality by 1.
Finset.card_univ
The cardinality of Finset.univ is the cardinality of the underlying finite type.
Finset.eq_of_subset_of_card_le
If a finset s is a subset of a finset t and |t| ≤ |s|, then s = t.
Finset.mem_erase
An element a belongs to s.erase b if and only if a ≠ b and a ∈ s.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
ne_eq
Inequality a ≠ b is defined as the negation of a = b.
Or.inl
If proposition a holds, then the disjunction a ∨ b holds.
Or.inr
If proposition b holds, then the disjunction a ∨ b holds.
RelIso.mk
Constructs an isomorphism of relations from a bijection that preserves and reflects the relation.
SimpleGraph.card_neighborFinset_eq_degree
The cardinality of the neighbor finset of a vertex v equals the degree of v.
SimpleGraph.mem_neighborFinset
A vertex w belongs to the neighbor finset of v if and only if v and w are adjacent.
SimpleGraph.Walk.cons_isPath_iff
Prepending an edge (u, v) to a walk p gives a path if and only if p is a path and u is not in the support of p.
tree_card_four_iso_of_exists_degree_three_aux
In a graph on 4 vertices, any vertex of degree 3 is adjacent to every other vertex.
tree_card_four_iso_of_exists_degree_three_aux_adj
In a tree, if a vertex v is adjacent to all other vertices, then two vertices are adjacent if and only if they are distinct and at least one of them is v.
tree_card_four_iso_of_exists_degree_three_no_triangle
A tree cannot contain a triangle (three pairwise adjacent vertices).

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

lemma tree_card_four_iso_of_exists_degree_three_aux {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (hcard : Fintype.card V = 4)    {v : V} (hdeg : G.degree v = 3) :    ∀ w : V, w ≠ v → G.Adj v w := by  intro w hw  have hsub : G.neighborFinset v ⊆ Finset.univ.erase v := by    intro u hu    simp only [Finset.mem_erase, Finset.mem_univ, and_true]    rw [SimpleGraph.mem_neighborFinset] at hu    exact hu.ne'  have hcard1 : (Finset.univ.erase v).card = 3 := by    rw [Finset.card_erase_of_mem (Finset.mem_univ v)]    rw [Finset.card_univ, hcard]  have hcard2 : (G.neighborFinset v).card = 3 := by    rw [SimpleGraph.card_neighborFinset_eq_degree, hdeg]  have heq : G.neighborFinset v = Finset.univ.erase v :=    Finset.eq_of_subset_of_card_le hsub (by rw [hcard1, hcard2])  have hw_mem : w ∈ Finset.univ.erase v := by    simp only [Finset.mem_erase, Finset.mem_univ, and_true]    exact hw  rw [← heq] at hw_mem  rwa [SimpleGraph.mem_neighborFinset] at hw_memlemma tree_card_four_iso_of_exists_degree_three_no_triangle {V : Type*} {G : SimpleGraph V} (hG : G.IsTree) {v x y : V}    (hvx : G.Adj v x) (hvy : G.Adj v y) (hxy : G.Adj x y) : False := by  have hyx := hxy.symm  obtain ⟨p, hp, huniq⟩ := hG.existsUnique_path v x  have hp1 : (SimpleGraph.Walk.cons hvx SimpleGraph.Walk.nil).IsPath := by    simp [hvx.ne]  have hp2 : (SimpleGraph.Walk.cons hvy (SimpleGraph.Walk.cons hyx SimpleGraph.Walk.nil)).IsPath := by    rw [SimpleGraph.Walk.cons_isPath_iff]    refine ⟨by simp [hyx.ne], ?_⟩    simp [hvy.ne, hvx.ne]  have e1 := huniq _ hp1  have e2 := huniq _ hp2  have hlen : (SimpleGraph.Walk.cons hvx SimpleGraph.Walk.nil).length =              (SimpleGraph.Walk.cons hvy (SimpleGraph.Walk.cons hyx SimpleGraph.Walk.nil)).length := by    rw [e1, e2]  simp at hlenlemma tree_card_four_iso_of_exists_degree_three_aux_adj {V : Type*} (G : SimpleGraph V)    (hG : G.IsTree) {v : V} (hv : ∀ w : V, w ≠ v → G.Adj v w) (x y : V) :    G.Adj x y ↔ x ≠ y ∧ (x = v ∨ y = v) := by  constructor  · intro h    refine ⟨h.ne, ?_⟩    by_contra hc    have h1 : x ≠ v := fun hx => hc (Or.inl hx)    have h2 : y ≠ v := fun hy => hc (Or.inr hy)    exact tree_card_four_iso_of_exists_degree_three_no_triangle hG (hv x h1) (hv y h2) h  · rintro ⟨hne, rfl | rfl⟩    · exact hv y hne.symm    · exact (hv x hne).symm/-- Any two trees on 4 vertices each possessing a vertex of degree 3 are isomorphic. -/theorem tree_card_four_iso_of_exists_degree_three {V₁ V₂ : Type*} [Fintype V₁] [DecidableEq V₁] [Fintype V₂] [DecidableEq V₂]    (T₁ : SimpleGraph V₁) (T₂ : SimpleGraph V₂) [DecidableRel T₁.Adj] [DecidableRel T₂.Adj]    (hT₁ : T₁.IsTree) (hT₂ : T₂.IsTree) (hcard₁ : Fintype.card V₁ = 4) (hcard₂ : Fintype.card V₂ = 4)    (hv₁ : ∃ v : V₁, T₁.degree v = 3) (hv₂ : ∃ v : V₂, T₂.degree v = 3) :    Nonempty (T₁ ≃g T₂) := by  obtain ⟨v₁, hv₁⟩ := hv₁  obtain ⟨v₂, hv₂⟩ := hv₂  have hadj₁ := tree_card_four_iso_of_exists_degree_three_aux T₁ hcard₁ hv₁  have hadj₂ := tree_card_four_iso_of_exists_degree_three_aux T₂ hcard₂ hv₂  have key₁ := tree_card_four_iso_of_exists_degree_three_aux_adj T₁ hT₁ hadj₁  have key₂ := tree_card_four_iso_of_exists_degree_three_aux_adj T₂ hT₂ hadj₂  obtain ⟨E⟩ : Nonempty (V₁ ≃ V₂) := by    rw [← Fintype.card_eq]    rw [hcard₁, hcard₂]  have hex : ∀ x : V₁, E.trans (Equiv.swap (E v₁) v₂) x = v₂ ↔ x = v₁ := by    intro x    show Equiv.swap (E v₁) v₂ (E x) = v₂ ↔ x = v₁    rw [Equiv.swap_apply_eq_iff, Equiv.swap_apply_right, E.injective.eq_iff]  have hne : ∀ x y : V₁, (E.trans (Equiv.swap (E v₁) v₂) x      = E.trans (Equiv.swap (E v₁) v₂) y ↔ x = y) := by    intro x y    exact (Equiv.injective _).eq_iff  refine ⟨RelIso.mk (E.trans (Equiv.swap (E v₁) v₂)) ?_⟩  intro x y  rw [key₂, key₁, hex x, hex y, ne_eq, ne_eq, hne x y]
See it in the graphDiscuss this resultChallenge it