is_caterpillar_iso_of_card_le_three
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
- is_caterpillar_isTreeEvery caterpillar graph is a tree.
- is_caterpillarA graph is a caterpillar if it is a tree containing a path such that every vertex is either on the path or adjacent to a vertex on the path.
- Arena.Reachable.transReachability is transitive.
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.
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.
obtain ⟨p⟩ := h cases p with | nil => exact absurd rfl hxy | cons hd tl => exact ⟨_, hd, fun he => hna (he ▸ hd)⟩
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.
uses
Walk.cons_isPath_iff,Walk.IsPath.nil,Walk.support_nil,List.mem_singleton,Walk.support_cons,List.mem_conshave 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
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.
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
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.
uses
Fintype.card_pos,Nat.lt_or_ge,Fintype.card_le_one_iff_subsingleton.mp,Classical.arbitrary,Subsingleton.elimhaveI : 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⟩
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.
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
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.
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⟩
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.
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'
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.
· 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
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.
uses
not_or,is_caterpillar_iso_of_card_le_three_aux_no_triangleintro 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
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.
· rintro ⟨hxy, hxv | hyv⟩ · rw [hxv] at hxy ⊢ exact hv y hxy.symm · rw [hyv] at hxy ⊢ exact (hv x hxy).symmBoth 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₂.
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.mphave 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
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.
uses
Equiv.swap,Equiv.swap_apply_eq_iff,Equiv.swap_apply_right,Equiv.injectivehave 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
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₁.
uses
RelIso.mk,ne_eqrefine ⟨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)
- Although the theorem is stated for caterpillars, the proof only uses the fact that caterpillars are trees; any two trees on at most 3 vertices of equal size are isomorphic by the exact same argument.
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.
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]