AFTD Auto-Formalizing Theoretical Domains

is_caterpillar_iso_of_card_le_three

theoremverified

Any two caterpillars on at most 3 vertices with equal vertex counts are isomorphic.

Statement

theorem is_caterpillar_iso_of_card_le_three
    {V₁ V₂ : Type*} [Fintype V₁] [DecidableEq V₁] [Fintype V₂] [DecidableEq V₂]
    (T₁ : SimpleGraph V₁) (T₂ : SimpleGraph V₂)
    (hT₁ : is_caterpillar T₁) (hT₂ : is_caterpillar T₂)
    (hcard : Fintype.card V₁ = Fintype.card V₂)
    (hle : Fintype.card 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
Built on 3

The proof, explained

To show that any two caterpillars T₁, T₂ on at most 3 vertices of equal order are isomorphic, the proof first observes that every caterpillar is a tree and establishes that any tree on at most 3 vertices possesses a dominating vertex adjacent to all other vertices. Furthermore, because trees contain no triangles, the edges in such a tree are precisely those incident to this dominating vertex, completely determining the graph structure up to the identity of the central vertex. Given a bijection between the vertex sets, post-composing it with a transposition aligns the two dominating vertices. This adjusted bijection preserves adjacency, producing the desired graph isomorphism.

  1. A walk between distinct non-adjacent vertices begins with an edge to a vertex different from both endpoints.

    Let p be a walk from x to y with x ≠ y and ¬ G.Adj x y. The walk cannot be empty because x ≠ y. Thus p begins with an edge x ~ z followed by a walk from z to y. If z = y, this initial edge would contradict ¬ G.Adj x y; hence z ≠ y, yielding the desired neighbor.

    lines 7–10

      obtain ⟨p⟩ := h
      cases p with
      | nil => exact absurd rfl hxy
      | cons hd tl => exact ⟨_, hd, fun he => hna (he ▸ hd)⟩
  2. In any graph, a triangle would yield two distinct paths between the same two endpoints: one of length 1 and one of length 2.

    Suppose v, x, y form a triangle with edges v ~ x, v ~ y, and x ~ y. The single edge v ~ x is a path from v to x of length 1 because v ≠ x. Symmetrizing x ~ y to y ~ x, the two-step walk v ~ y ~ x is also a path from v to x: the second step y ~ x is a path, and v does not appear among its vertices because v ≠ y and v ≠ x.

    lines 17–35

    uses Walk.cons_isPath_iff, Walk.IsPath.nil, Walk.support_nil, List.mem_singleton, Walk.support_cons, List.mem_cons

      have hyx : G.Adj y x := hxy.symm
      obtain ⟨p, -, huniq⟩ := hG.existsUnique_path v x
      have hpA : (Walk.cons hvx Walk.nil : G.Walk v x).IsPath := by
        rw [Walk.cons_isPath_iff]
        refine ⟨Walk.IsPath.nil, ?_⟩
        simp only [Walk.support_nil, List.mem_singleton]
        exact hvx.ne
      have hpB : (Walk.cons hvy (Walk.cons hyx Walk.nil) : G.Walk v x).IsPath := by
        rw [Walk.cons_isPath_iff]
        refine ⟨?_, ?_⟩
        · rw [Walk.cons_isPath_iff]
          refine ⟨Walk.IsPath.nil, ?_⟩
          simp only [Walk.support_nil, List.mem_singleton]
          exact hyx.ne
        · intro hmem
          rw [Walk.support_cons, Walk.support_nil, List.mem_cons, List.mem_singleton] at hmem
          rcases hmem with h | h
          · exact hvy.ne h
          · exact hvx.ne h
  3. A tree contains no triangle. automation

    In a tree, any two vertices are connected by a uniquely determined path. The paths of lengths 1 and 2 constructed from the assumed triangle must therefore be identical, implying 1 = 2. Linear integer arithmetic (the omega tactic) derives a contradiction from this equality.

    lines 36–42

      have hA : (Walk.cons hvx Walk.nil : G.Walk v x).length = 1 := by simp
      have hB : (Walk.cons hvy (Walk.cons hyx Walk.nil) : G.Walk v x).length = 2 := by simp
      have hlen : (Walk.cons hvx Walk.nil : G.Walk v x).length
          = (Walk.cons hvy (Walk.cons hyx Walk.nil) : G.Walk v x).length := by
        rw [huniq _ hpA, huniq _ hpB]
      rw [hA, hB] at hlen
      omega
  4. A tree on 1 vertex contains a dominating vertex.

    A tree is connected, so its vertex set V is nonempty. When |V| < 2, the cardinality must be 1, so V is a subsingleton. Any chosen vertex v vacuously satisfies the condition of being adjacent to all other vertices, since no distinct vertex exists.

    lines 49–55

    uses Fintype.card_pos, Nat.lt_or_ge, Fintype.card_le_one_iff_subsingleton.mp, Classical.arbitrary, Subsingleton.elim

      haveI : Nonempty V := hG.connected.nonempty
      have hpos : 0 < Fintype.card V := Fintype.card_pos
      have hconn : G.Preconnected := hG.connected.preconnected
      rcases Nat.lt_or_ge (Fintype.card V) 2 with hlt2 | hge2
      · have hcard1 : Fintype.card V = 1 := by omega
        haveI : Subsingleton V := Fintype.card_le_one_iff_subsingleton.mp (by omega)
        exact ⟨Classical.arbitrary V, fun w hw => absurd (Subsingleton.elim w _) hw⟩
  5. A tree on 2 vertices contains a dominating vertex.

    When |V| = 2, let V = {a, b} with a ≠ b. Because the tree is connected, there is a walk from a to b. The walk cannot be empty since a ≠ b, so it begins with an edge from a to some vertex v. Since V = {a, b} and simple graphs have no self-loops, v must be b. Thus a ~ b, making a adjacent to all other vertices.

    lines 56–75

    uses Nat.lt_or_ge, Finset.card_eq_two, Finset.card_univ, Finset.mem_univ

      · rcases Nat.lt_or_ge (Fintype.card V) 3 with hlt3 | hge3
        · have hc2 : Fintype.card V = 2 := by omega
          obtain ⟨a, b, hab, huniv⟩ :=
            (Finset.card_eq_two (s := (Finset.univ : Finset V))).mp
              (by rw [Finset.card_univ]; exact hc2)
          have hmem2 : ∀ x : V, x = a ∨ x = b := by
            intro x
            have h : x ∈ ({a, b} : Finset V) := huniv ▸ Finset.mem_univ x
            simpa using h
          refine ⟨a, fun w hw => ?_⟩
          rcases hmem2 w with h | h
          · exact absurd h hw
          · rw [h]
            obtain ⟨p⟩ := hconn a b
            cases p with
            | nil => exact absurd rfl hab
            | cons hd tl =>
                rcases hmem2 _ with h' | h'
                · exact absurd h' hd.ne'
                · exact h' ▸ hd
  6. In a connected graph on 3 vertices, any non-adjacent pair has an edge to the remaining third vertex.

    When |V| = 3, V consists of three distinct vertices {a, b, c}. Applying the earlier walk-neighbor lemma, if two distinct vertices x, y are not adjacent, there exists a neighbor z of x with z ≠ x and z ≠ y. In a 3-element set, this forces z to be the third vertex.

    lines 76–88

    uses Finset.card_eq_three, Finset.card_univ, Finset.mem_univ, Finset.mem_insert, Finset.mem_singleton, is_caterpillar_iso_of_card_le_three_aux_walk_nbr

        · have hc3 : Fintype.card V = 3 := by omega
          obtain ⟨a, b, c, hab, hac, hbc, huniv⟩ :=
            (Finset.card_eq_three (s := (Finset.univ : Finset V))).mp
              (by rw [Finset.card_univ]; exact hc3)
          have hmem : ∀ x : V, x = a ∨ x = b ∨ x = c := by
            intro x
            have h : x ∈ ({a, b, c} : Finset V) := huniv ▸ Finset.mem_univ x
            simpa [Finset.mem_insert, Finset.mem_singleton] using h
          have third : ∀ x y : V, x ≠ y → ¬ G.Adj x y → ∃ z, G.Adj x z ∧ z ≠ x ∧ z ≠ y :=
            fun x y hxy hna => by
              obtain ⟨z, hz1, hz2⟩ :=
                is_caterpillar_iso_of_card_le_three_aux_walk_nbr (hconn x y) hxy hna
              exact ⟨z, hz1, hz1.ne', hz2⟩
  7. A tree on 3 vertices has a dominating vertex when a ~ b.

    If a ~ c as well, then a is adjacent to both b and c, so a is dominating. If a is not adjacent to c, the third-vertex property applied to c and a implies c must be adjacent to the remaining vertex b. Thus b is adjacent to both a and c, making b dominating.

    lines 89–107

          by_cases h1 : G.Adj a b
          · by_cases h2 : G.Adj a c
            · refine ⟨a, fun w hw => ?_⟩
              rcases hmem w with h | h | h
              · exact absurd h hw
              · rw [h]; exact h1
              · rw [h]; exact h2
            · obtain ⟨z, hz1, hz2, hz3⟩ := third c a hac.symm (fun h => h2 h.symm)
              have hzb : z = b := by
                rcases hmem z with h | h | h
                · exact absurd h hz3
                · exact h
                · exact absurd h hz2
              have hbc' : G.Adj b c := (hzb ▸ hz1).symm
              refine ⟨b, fun w hw => ?_⟩
              rcases hmem w with h | h | h
              · rw [h]; exact h1.symm
              · exact absurd h hw
              · rw [h]; exact hbc'
  8. A tree on 3 vertices has a dominating vertex when a is not adjacent to b.

    If a is not adjacent to b, the third-vertex property forces the neighbor of a to be c, so a ~ c. Symmetrically, b must also be adjacent to c. Hence c is adjacent to both a and b, making c a dominating vertex.

    lines 108–125

          · obtain ⟨y, hy1, hy2, hy3⟩ := third a b hab h1
            have hyc : y = c := by
              rcases hmem y with h | h | h
              · exact absurd h hy2
              · exact absurd h hy3
              · exact h
            have hac' : G.Adj a c := hyc ▸ hy1
            obtain ⟨z, hz1, hz2, hz3⟩ := third b a hab.symm (fun h => h1 h.symm)
            have hzc : z = c := by
              rcases hmem z with h | h | h
              · exact absurd h hz3
              · exact absurd h hz2
              · exact h
            refine ⟨c, fun w hw => ?_⟩
            rcases hmem w with h | h | h
            · rw [h]; exact hac'.symm
            · rw [h]; exact (hzc ▸ hz1).symm
            · exact absurd h hw
  9. In a tree with a dominating vertex v, every edge is incident to v.

    Suppose x ~ y. Then x ≠ y. If neither x nor y were equal to v, then by dominance of v we would have v ~ x and v ~ y. Together with x ~ y, this would form a triangle on {v, x, y}, contradicting the fact that trees have no triangles. Hence x = v or y = v.

    lines 134–140

    uses not_or, is_caterpillar_iso_of_card_le_three_aux_no_triangle

      intro x y
      constructor
      · intro h
        refine ⟨h.ne, ?_⟩
        by_contra hc
        rw [not_or] at hc
        exact is_caterpillar_iso_of_card_le_three_aux_no_triangle hG (hv x hc.1) (hv y hc.2) h
  10. In a tree with a dominating vertex v, any distinct pair containing v is an edge.

    Conversely, if x ≠ y and either x = v or y = v, the pair consists of v and a distinct vertex. By the dominance hypothesis, v is adjacent to every distinct vertex, so x ~ y holds by symmetry.

    lines 141–145

      · rintro ⟨hxy, hxv | hyv⟩
        · rw [hxv] at hxy ⊢
          exact hv y hxy.symm
        · rw [hyv] at hxy ⊢
          exact (hv x hxy).symm
  11. Both caterpillars have dominating vertices, their edge relations are characterized by these vertices, and an equinumerous bijection exists.

    Because caterpillars are trees (is_caterpillar_isTree), each tree has order at most 3 and therefore admits a dominating vertex v₁ ∈ V₁ and v₂ ∈ V₂. By aux_adj, the edges in each tree are precisely the pairs consisting of the dominating vertex and another vertex. Since |V₁| = |V₂|, there exists a bijection E : V₁ ≃ V₂.

    lines 155–162

    uses is_caterpillar_isTree, is_caterpillar_iso_of_card_le_three_aux_dom, is_caterpillar_iso_of_card_le_three_aux_adj, Fintype.card_eq.mp

      have h1 : T₁.IsTree := is_caterpillar_isTree T₁ hT₁
      have h2 : T₂.IsTree := is_caterpillar_isTree T₂ hT₂
      have hle2 : Fintype.card V₂ ≤ 3 := hcard ▸ hle
      obtain ⟨v₁, hv₁⟩ := is_caterpillar_iso_of_card_le_three_aux_dom T₁ h1 hle
      obtain ⟨v₂, hv₂⟩ := is_caterpillar_iso_of_card_le_three_aux_dom T₂ h2 hle2
      have key₁ := is_caterpillar_iso_of_card_le_three_aux_adj T₁ h1 hv₁
      have key₂ := is_caterpillar_iso_of_card_le_three_aux_adj T₂ h2 hv₂
      obtain ⟨E⟩ := Fintype.card_eq.mp hcard
  12. Modifying the bijection with a transposition maps v₁ to v₂.

    Composing E with the transposition swapping E(v₁) and v₂ gives a bijection f : V₁ ≃ V₂ such that f(x) = v₂ ↔ x = v₁. Because f is a bijection, it is also injective: f(x) = f(y) ↔ x = y.

    lines 163–170

    uses Equiv.swap, 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
  13. The modified bijection is a graph isomorphism between T₁ and T₂.

    We define the graph isomorphism using f. By the edge characterizations in T₁ and T₂, f(x) ~ f(y) in T₂ if and only if f(x) ≠ f(y) and (f(x) = v₂ ∨ f(y) = v₂). Since f is injective and maps v₁ to v₂, this is equivalent to x ≠ y and (x = v₁ ∨ y = v₁), which is the exact condition for x ~ y in T₁.

    lines 171–173

    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]
Walk.cons_isPath_iff
extending a walk by an edge u ~ v yields a path if and only if the original walk is a path and u is not in its vertex support
Walk.IsPath.nil
the trivial walk with no edges at any vertex is a path
Walk.support_nil
the vertex support of the trivial walk at u is the singleton list [u]
Walk.support_cons
the vertex support of an extended walk is the start vertex consed onto the support of the remaining walk
List.mem_singleton
membership in a singleton list: a ∈ [b] ↔ a = b
List.mem_cons
membership in a cons list: a ∈ b :: l ↔ a = b ∨ a ∈ l
Fintype.card_pos
any nonempty finite type has strictly positive cardinality
Nat.lt_or_ge
for any natural numbers n and m, either n < m or n ≥ m
Fintype.card_le_one_iff_subsingleton.mp
if a finite type has cardinality at most 1, it has at most one element (it is a subsingleton)
Classical.arbitrary
chooses an arbitrary element from a nonempty type
Subsingleton.elim
any two elements of a subsingleton type are equal
Finset.card_eq_two
a finite set has cardinality 2 if and only if it consists of two distinct elements
Finset.card_univ
the cardinality of the universal finset is the cardinality of the underlying finite type
Finset.mem_univ
every element of a finite type belongs to the universal finset
Finset.card_eq_three
a finite set has cardinality 3 if and only if it consists of three pairwise distinct elements
Finset.mem_insert
membership in an inserted finset: a ∈ insert b s ↔ a = b ∨ a ∈ s
is_caterpillar_iso_of_card_le_three_aux_walk_nbr
a walk between distinct non-adjacent vertices starts with an edge to a third vertex
not_or
de Morgan's law: ¬(p ∨ q) ↔ ¬p ∧ ¬q
is_caterpillar_iso_of_card_le_three_aux_no_triangle
a tree contains no triangle (no three mutually adjacent vertices)
is_caterpillar_isTree
every caterpillar graph is a tree
is_caterpillar_iso_of_card_le_three_aux_dom
every tree on at most 3 vertices has a dominating vertex adjacent to all other vertices
is_caterpillar_iso_of_card_le_three_aux_adj
in a tree where v is adjacent to all other vertices, the edges are precisely those pairs containing v and a distinct vertex
Fintype.card_eq.mp
two finite types of equal cardinality have a bijection between them
Equiv.swap
the permutation swapping two given elements and fixing all others
Equiv.swap_apply_eq_iff
applying a swap to z equals w if and only if z equals the swap applied to w
Equiv.swap_apply_right
the swap of a and b maps b to a
Equiv.injective
every bijection (equivalence) is an injective function
RelIso.mk
constructs an isomorphism of relational structures from a bijection that preserves and reflects the relation
ne_eq
definition of inequality: a ≠ b ↔ ¬(a = b)

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

open SimpleGraph in/-- A walk from `x` to `y` with `x ≠ y` and `¬ G.Adj x y` starts with an edge from `x`to a vertex other than `y`. -/private lemma is_caterpillar_iso_of_card_le_three_aux_walk_nbr    {V : Type*} {G : SimpleGraph V} {x y : V} (h : G.Reachable x y)    (hxy : x ≠ y) (hna : ¬ G.Adj x y) : ∃ z, G.Adj x z ∧ z ≠ y := by  obtain ⟨p⟩ := h  cases p with  | nil => exact absurd rfl hxy  | cons hd tl => exact ⟨_, hd, fun he => hna (he ▸ hd)⟩open SimpleGraph in/-- A tree contains no triangle. -/private lemma is_caterpillar_iso_of_card_le_three_aux_no_triangle    {V : Type*} {G : SimpleGraph V} {v x y : V} (hG : G.IsTree)    (hvx : G.Adj v x) (hvy : G.Adj v y) (hxy : G.Adj x y) : False := by  have hyx : G.Adj y x := hxy.symm  obtain ⟨p, -, huniq⟩ := hG.existsUnique_path v x  have hpA : (Walk.cons hvx Walk.nil : G.Walk v x).IsPath := by    rw [Walk.cons_isPath_iff]    refine ⟨Walk.IsPath.nil, ?_⟩    simp only [Walk.support_nil, List.mem_singleton]    exact hvx.ne  have hpB : (Walk.cons hvy (Walk.cons hyx Walk.nil) : G.Walk v x).IsPath := by    rw [Walk.cons_isPath_iff]    refine ⟨?_, ?_⟩    · rw [Walk.cons_isPath_iff]      refine ⟨Walk.IsPath.nil, ?_⟩      simp only [Walk.support_nil, List.mem_singleton]      exact hyx.ne    · intro hmem      rw [Walk.support_cons, Walk.support_nil, List.mem_cons, List.mem_singleton] at hmem      rcases hmem with h | h      · exact hvy.ne h      · exact hvx.ne h  have hA : (Walk.cons hvx Walk.nil : G.Walk v x).length = 1 := by simp  have hB : (Walk.cons hvy (Walk.cons hyx Walk.nil) : G.Walk v x).length = 2 := by simp  have hlen : (Walk.cons hvx Walk.nil : G.Walk v x).length      = (Walk.cons hvy (Walk.cons hyx Walk.nil) : G.Walk v x).length := by    rw [huniq _ hpA, huniq _ hpB]  rw [hA, hB] at hlen  omegaopen SimpleGraph in/-- A tree on at most three vertices has a vertex adjacent to every other vertex. -/private theorem is_caterpillar_iso_of_card_le_three_aux_dom    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hG : G.IsTree)    (hle : Fintype.card V ≤ 3) : ∃ v : V, ∀ w : V, w ≠ v → G.Adj v w := by  haveI : Nonempty V := hG.connected.nonempty  have hpos : 0 < Fintype.card V := Fintype.card_pos  have hconn : G.Preconnected := hG.connected.preconnected  rcases Nat.lt_or_ge (Fintype.card V) 2 with hlt2 | hge2  · have hcard1 : Fintype.card V = 1 := by omega    haveI : Subsingleton V := Fintype.card_le_one_iff_subsingleton.mp (by omega)    exact ⟨Classical.arbitrary V, fun w hw => absurd (Subsingleton.elim w _) hw⟩  · rcases Nat.lt_or_ge (Fintype.card V) 3 with hlt3 | hge3    · have hc2 : Fintype.card V = 2 := by omega      obtain ⟨a, b, hab, huniv⟩ :=        (Finset.card_eq_two (s := (Finset.univ : Finset V))).mp          (by rw [Finset.card_univ]; exact hc2)      have hmem2 : ∀ x : V, x = a ∨ x = b := by        intro x        have h : x ∈ ({a, b} : Finset V) := huniv ▸ Finset.mem_univ x        simpa using h      refine ⟨a, fun w hw => ?_⟩      rcases hmem2 w with h | h      · exact absurd h hw      · rw [h]        obtain ⟨p⟩ := hconn a b        cases p with        | nil => exact absurd rfl hab        | cons hd tl =>            rcases hmem2 _ with h' | h'            · exact absurd h' hd.ne'            · exact h' ▸ hd    · have hc3 : Fintype.card V = 3 := by omega      obtain ⟨a, b, c, hab, hac, hbc, huniv⟩ :=        (Finset.card_eq_three (s := (Finset.univ : Finset V))).mp          (by rw [Finset.card_univ]; exact hc3)      have hmem : ∀ x : V, x = a ∨ x = b ∨ x = c := by        intro x        have h : x ∈ ({a, b, c} : Finset V) := huniv ▸ Finset.mem_univ x        simpa [Finset.mem_insert, Finset.mem_singleton] using h      have third : ∀ x y : V, x ≠ y → ¬ G.Adj x y → ∃ z, G.Adj x z ∧ z ≠ x ∧ z ≠ y :=        fun x y hxy hna => by          obtain ⟨z, hz1, hz2⟩ :=            is_caterpillar_iso_of_card_le_three_aux_walk_nbr (hconn x y) hxy hna          exact ⟨z, hz1, hz1.ne', hz2⟩      by_cases h1 : G.Adj a b      · by_cases h2 : G.Adj a c        · refine ⟨a, fun w hw => ?_⟩          rcases hmem w with h | h | h          · exact absurd h hw          · rw [h]; exact h1          · rw [h]; exact h2        · obtain ⟨z, hz1, hz2, hz3⟩ := third c a hac.symm (fun h => h2 h.symm)          have hzb : z = b := by            rcases hmem z with h | h | h            · exact absurd h hz3            · exact h            · exact absurd h hz2          have hbc' : G.Adj b c := (hzb ▸ hz1).symm          refine ⟨b, fun w hw => ?_⟩          rcases hmem w with h | h | h          · rw [h]; exact h1.symm          · exact absurd h hw          · rw [h]; exact hbc'      · obtain ⟨y, hy1, hy2, hy3⟩ := third a b hab h1        have hyc : y = c := by          rcases hmem y with h | h | h          · exact absurd h hy2          · exact absurd h hy3          · exact h        have hac' : G.Adj a c := hyc ▸ hy1        obtain ⟨z, hz1, hz2, hz3⟩ := third b a hab.symm (fun h => h1 h.symm)        have hzc : z = c := by          rcases hmem z with h | h | h          · exact absurd h hz3          · exact absurd h hz2          · exact h        refine ⟨c, fun w hw => ?_⟩        rcases hmem w with h | h | h        · rw [h]; exact hac'.symm        · rw [h]; exact (hzc ▸ hz1).symm        · exact absurd h hwopen SimpleGraph in/-- In a tree with at most three vertices, a vertex adjacent to every other vertex isadjacent exactly to the other vertices. -/private theorem is_caterpillar_iso_of_card_le_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  intro x y  constructor  · intro h    refine ⟨h.ne, ?_⟩    by_contra hc    rw [not_or] at hc    exact is_caterpillar_iso_of_card_le_three_aux_no_triangle hG (hv x hc.1) (hv y hc.2) h  · rintro ⟨hxy, hxv | hyv⟩    · rw [hxv] at hxy ⊢      exact hv y hxy.symm    · rw [hyv] at hxy ⊢      exact (hv x hxy).symm/-- Any two caterpillars on at most 3 vertices of the same order are isomorphic. -/theorem is_caterpillar_iso_of_card_le_three    {V₁ V₂ : Type*} [Fintype V₁] [DecidableEq V₁] [Fintype V₂] [DecidableEq V₂]    (T₁ : SimpleGraph V₁) (T₂ : SimpleGraph V₂)    (hT₁ : is_caterpillar T₁) (hT₂ : is_caterpillar T₂)    (hcard : Fintype.card V₁ = Fintype.card V₂)    (hle : Fintype.card V₁ ≤ 3) :    Nonempty (T₁ ≃g T₂) := by  have h1 : T₁.IsTree := is_caterpillar_isTree T₁ hT₁  have h2 : T₂.IsTree := is_caterpillar_isTree T₂ hT₂  have hle2 : Fintype.card V₂ ≤ 3 := hcard ▸ hle  obtain ⟨v₁, hv₁⟩ := is_caterpillar_iso_of_card_le_three_aux_dom T₁ h1 hle  obtain ⟨v₂, hv₂⟩ := is_caterpillar_iso_of_card_le_three_aux_dom T₂ h2 hle2  have key₁ := is_caterpillar_iso_of_card_le_three_aux_adj T₁ h1 hv₁  have key₂ := is_caterpillar_iso_of_card_le_three_aux_adj T₂ h2 hv₂  obtain ⟨E⟩ := Fintype.card_eq.mp 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