tree_card_four_iso_path_graph
Any tree on 4 vertices with all degrees at most 2 is isomorphic to the standard path graph pathGraph 4.
Statement
theorem tree_card_four_iso_path_graph {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) : Nonempty (T ≃g SimpleGraph.pathGraph 4)
- Source
- step towards tree_card_four_iso_of_degree_le_two
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 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
To prove that any tree on 4 vertices with maximum degree at most 2 is isomorphic to the 4-vertex path graph, the argument first uses an auxiliary theorem to obtain four distinct vertices a, b, c, d whose only edges are {a, b}, {b, c}, and {c, d}. The map sending the vertices 0, 1, 2, 3 of Fin 4 to a, b, c, d is shown to be injective by finite case exhaustion and hence bijective by cardinality. Finally, an exhaustive check of all 16 index pairs verifies that this bijection preserves adjacency in both directions, establishing the graph isomorphism.
The vertices of T can be labeled as four distinct elements a, b, c, d such that the edges of T are precisely {a, b}, {b, c}, and {c, d}.
By the classification lemma `tree_card_four_path_edges`, any tree on 4 vertices whose vertices all have degree at most 2 is a simple path. Applying this gives four distinct vertices a, b, c, d ∈ V, their pairwise distinctness, and an explicit characterization `h_adj` stating that two vertices are adjacent in T if and only if they form one of the pairs {a, b}, {b, c}, or {c, d}.
uses
tree_card_four_path_edgesobtain ⟨a, b, c, d, hab, hac, had, hbc, hbd, hcd, -, h_adj⟩ := tree_card_four_path_edges T hT hcard hdegThe map f : Fin 4 → V sending 0, 1, 2, 3 to a, b, c, d respectively is injective.
Assume f(u) = f(v) for u, v ∈ Fin 4. A brute-force case analysis on all 4 × 4 = 16 pairs of values for (u, v) shows that whenever u ≠ v, the equality f(u) = f(v) contradicts the pairwise distinctness of a, b, c, d. Hence u = v in every case.
let f : Fin 4 → V := ![a, b, c, d] have hinj : Function.Injective f := by intro u v h fin_cases u <;> fin_cases v <;> aesop
The map f is bijective and therefore defines an equivalence e : Fin 4 ≃ V.
Since Fin 4 and V both have cardinality 4 (by `Fintype.card_fin` and the hypothesis `hcard`), the injective map f is automatically bijective by `Fintype.bijective_iff_injective_and_card`. Using `Equiv.ofBijective`, f is promoted to an equivalence e between Fin 4 and V.
uses
Fintype.bijective_iff_injective_and_card,Fintype.card_fin,Equiv.ofBijectivehave hbij : Function.Bijective f := (Fintype.bijective_iff_injective_and_card f).mpr ⟨hinj, by rw [Fintype.card_fin, hcard]⟩ let e : Fin 4 ≃ V := Equiv.ofBijective f hbij
The equivalence e preserves adjacency: for any u, v ∈ Fin 4, e(u) and e(v) are adjacent in T if and only if u and v are adjacent in the 4-vertex path graph.
Given u, v ∈ Fin 4, we evaluate both sides across all 16 possible pairs of indices. For each pair, adjacency in the path graph is unfolded via `SimpleGraph.pathGraph_adj` into |u - v| = 1, while adjacency in T is unfolded via `h_adj`. In each case, both conditions evaluate to equivalent boolean values (both true for adjacent indices {0, 1}, {1, 2}, {2, 3} and both false otherwise).
uses
SimpleGraph.pathGraph_adjhave h_rel : ∀ {u v : Fin 4}, T.Adj (e u) (e v) ↔ (SimpleGraph.pathGraph 4).Adj u v := by intro u v fin_cases u <;> fin_cases v <;> { rw [SimpleGraph.pathGraph_adj, h_adj] dsimp [e, f, Equiv.ofBijective] aesop }
T is isomorphic to the path graph on 4 vertices.
Combining the vertex equivalence e with the adjacency equivalence `h_rel` via `RelIso.mk` gives an isomorphism of graphs from the path graph on 4 vertices to T. Inverting this isomorphism (`r.symm`) yields an isomorphism from T to the path graph, witnessing that the type of such isomorphisms is nonempty.
uses
RelIso.mkhave r : (SimpleGraph.pathGraph 4).Adj ≃r T.Adj := RelIso.mk e h_rel exact ⟨r.symm⟩
tree_card_four_path_edges- In any tree on 4 vertices where every vertex has degree at most 2, there exist four distinct vertices that exhaust the graph and whose adjacent pairs are precisely the three consecutive edges of a simple path.
Fintype.bijective_iff_injective_and_card- A function between finite types of the same cardinality is bijective if and only if it is injective.
Fintype.card_fin- The cardinality of Fin n is n.
Equiv.ofBijective- A bijective function can be promoted to an equivalence (a bijection with a two-sided inverse).
SimpleGraph.pathGraph_adj- In the standard path graph on n vertices, two vertices u and v are adjacent if and only if |u - v| = 1.
RelIso.mk- An equivalence of types that preserves and reflects a binary relation constitutes a relational isomorphism.
- Both the injectivity of the vertex mapping and the preservation of adjacency are proved by exhaustively checking all 16 pairs of indices in Fin 4 using `fin_cases` and `aesop`, rather than by general algebraic arguments.
- In Lean, graph isomorphisms (denoted `≃g`) are defined as relational isomorphisms (`RelIso`) between the graphs' adjacency relations.
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.
/-- Any tree on 4 vertices with all degrees at most 2 is isomorphic to the standard path graph on 4 vertices. -/theorem tree_card_four_iso_path_graph {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) : Nonempty (T ≃g SimpleGraph.pathGraph 4) := by obtain ⟨a, b, c, d, hab, hac, had, hbc, hbd, hcd, -, h_adj⟩ := tree_card_four_path_edges T hT hcard hdeg let f : Fin 4 → V := ![a, b, c, d] have hinj : Function.Injective f := by intro u v h fin_cases u <;> fin_cases v <;> aesop have hbij : Function.Bijective f := (Fintype.bijective_iff_injective_and_card f).mpr ⟨hinj, by rw [Fintype.card_fin, hcard]⟩ let e : Fin 4 ≃ V := Equiv.ofBijective f hbij have h_rel : ∀ {u v : Fin 4}, T.Adj (e u) (e v) ↔ (SimpleGraph.pathGraph 4).Adj u v := by intro u v fin_cases u <;> fin_cases v <;> { rw [SimpleGraph.pathGraph_adj, h_adj] dsimp [e, f, Equiv.ofBijective] aesop } have r : (SimpleGraph.pathGraph 4).Adj ≃r T.Adj := RelIso.mk e h_rel exact ⟨r.symm⟩