tree_card_four_iso_of_exists_degree_three
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.
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.
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_leintro 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])
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.
uses
Finset.mem_erase,Finset.mem_univ,and_true,SimpleGraph.mem_neighborFinsethave 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
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.
uses
SimpleGraph.Walk.cons_isPath_iffhave 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]
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.
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
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.
uses
Or.inl,Or.inr,tree_card_four_iso_of_exists_degree_three_no_triangleconstructor · 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
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).
· rintro ⟨hne, rfl | rfl⟩ · exact hv y hne.symm · exact (hv x hne).symm
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₂).
uses
tree_card_four_iso_of_exists_degree_three_aux,tree_card_four_iso_of_exists_degree_three_aux_adjobtain ⟨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₂
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₂.
uses
Fintype.card_eqobtain ⟨E⟩ : Nonempty (V₁ ≃ V₂) := by rw [← Fintype.card_eq] rw [hcard₁, hcard₂]
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.
uses
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 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₁.
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]
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
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.
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]