op223_tree_fin_four_iso_path_or_star
Every tree on four vertices is isomorphic either to the path graph on four vertices or to the star K_{1,3}.
Statement
theorem op223_tree_fin_four_iso_path_or_star (X : SimpleGraph (Fin 4)) (hX : X.IsTree) :
Nonempty (X ≃g SimpleGraph.pathGraph 4) ∨
Nonempty (X ≃g completeBipartiteGraph (Fin 1) (Fin 3))- Source
- step towards op223_sustainable_tree_fin_four
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- simple_graph_is_tree_sum_choose_degree_eq_iff_starFor a tree T on k ≥ 2 vertices, σ₂(T) = C(k−1,2) if and only if T is a star K_{1,k−1}: some vertex r is adjacent to every other vertex and…
- simple_graph_is_tree_sum_choose_degree_eq_iff_pathFor a tree T on k ≥ 2 vertices, σ₂(T) = k − 2 if and only if T is isomorphic to the path P_k.
- simple_graph_is_tree_card_sub_two_le_sum_choose_degree_le_chooseFor a tree T on k ≥ 2 vertices, σ₂(T) = ∑_v C(d_T(v),2) satisfies k − 2 ≤ σ₂(T) ≤ C(k−1,2).
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
- Used by 1
- op223_nonsustainable_tree_fin_fourEvery non-sustainable tree on four vertices is isomorphic to the star graph K_{1,3}.
The proof, explained
For any tree X on 4 vertices, the sum of binomial coefficients of vertex degrees, S = ∑_{v} (deg(v) choose 2), is known to satisfy |V| - 2 ≤ S ≤ (|V|-1 choose 2), which numerically specializes to 2 ≤ S ≤ 3. Consequently, S must be either 2 or 3. If S = 2, the lower bound is attained, which characterizes path graphs, so X is isomorphic to P₄; if S = 3, the upper bound is attained, which characterizes star graphs, and an explicit isomorphism establishes that X is isomorphic to K_{1,3}.
Definition of a bijection between Fin 4 and Fin 1 ⊕ Fin 3 sending a chosen vertex r to Sum.inl 0
Since Fin 4 and Fin 1 ⊕ Fin 3 both have cardinality 4, Fintype.equivOfCardEq gives an initial bijection between them. Composing this with the transposition swapping the image of r and Sum.inl 0 produces a bijection that maps r to Sum.inl 0.
uses
Fintype.equivOfCardEqnoncomputable def op223_tree_fin_four_iso_path_or_star_equiv (r : Fin 4) : Fin 4 ≃ Fin 1 ⊕ Fin 3 := let e₀ : Fin 4 ≃ Fin 1 ⊕ Fin 3 := Fintype.equivOfCardEq (by decide) e₀.trans (Equiv.swap (e₀ r) (Sum.inl 0))
The equivalence maps the center vertex r to Sum.inl 0
Unfolding the definition of op223_tree_fin_four_iso_path_or_star_equiv, the vertex r is mapped first by the initial bijection to e₀(r), and then the swap between e₀(r) and Sum.inl 0 sends e₀(r) directly to Sum.inl 0 by Equiv.swap_apply_left.
uses
op223_tree_fin_four_iso_path_or_star_equiv,Equiv.swap_apply_lefttheorem op223_tree_fin_four_iso_path_or_star_equiv_apply_center (r : Fin 4) : op223_tree_fin_four_iso_path_or_star_equiv r r = Sum.inl 0 := by dsimp [op223_tree_fin_four_iso_path_or_star_equiv] exact Equiv.swap_apply_left _ _
An element maps to Sum.inl 0 under the bijection if and only if it equals r
After rewriting the adjacency conditions of both the star graph and the complete bipartite graph, we observe that because the bijection sends r to Sum.inl 0, injectivity implies that any vertex maps to Sum.inl 0 if and only if that vertex is r.
uses
SimpleGraph.starGraph_adj,completeBipartiteGraph_adj,op223_tree_fin_four_iso_path_or_star_equiv_apply_centernoncomputable def op223_tree_fin_four_iso_path_or_star_starIso (r : Fin 4) : SimpleGraph.starGraph r ≃g completeBipartiteGraph (Fin 1) (Fin 3) where toEquiv := op223_tree_fin_four_iso_path_or_star_equiv r map_rel_iff' {x y} := by rw [SimpleGraph.starGraph_adj, completeBipartiteGraph_adj] have hx : op223_tree_fin_four_iso_path_or_star_equiv r x = Sum.inl 0 ↔ x = r := by rw [← op223_tree_fin_four_iso_path_or_star_equiv_apply_center r] exact (op223_tree_fin_four_iso_path_or_star_equiv r).injective.eq_iff have hy : op223_tree_fin_four_iso_path_or_star_equiv r y = Sum.inl 0 ↔ y = r := by rw [← op223_tree_fin_four_iso_path_or_star_equiv_apply_center r] exact (op223_tree_fin_four_iso_path_or_star_equiv r).injective.eq_iff
Characterization of left and right components in Fin 1 ⊕ Fin 3 automation
Since Fin 1 contains only the element 0, an element in Fin 1 ⊕ Fin 3 belongs to the left component if and only if it equals Sum.inl 0, and belongs to the right component if and only if it is not Sum.inl 0. Both equivalences are proved by case analysis on the sum type and Fin 1, solved by simp. Rewriting with these rules simplifies the bipartite adjacency condition.
have h_left (z : Fin 1 ⊕ Fin 3) : z.isLeft = true ↔ z = Sum.inl 0 := by cases z with | inl a => fin_cases a simp | inr b => simp have h_right (z : Fin 1 ⊕ Fin 3) : z.isRight = true ↔ z ≠ Sum.inl 0 := by cases z with | inl a => fin_cases a simp | inr b => simp rw [h_left, h_right, h_left, h_right]
The bijection preserves adjacency, defining an isomorphism between the star graph and K_{1,3}
The condition for adjacency in the complete bipartite graph—that one endpoint is in the left component and the other in the right—translates to one endpoint being r and the other being distinct from r. This matches the definition of adjacency in the star graph centered at r, concluding the isomorphism.
have hx_ne : op223_tree_fin_four_iso_path_or_star_equiv r x ≠ Sum.inl 0 ↔ x ≠ r := not_iff_not.2 hx have hy_ne : op223_tree_fin_four_iso_path_or_star_equiv r y ≠ Sum.inl 0 ↔ y ≠ r := not_iff_not.2 hy rw [hx, hy, hx_ne, hy_ne] constructor · rintro (⟨rfl, hy⟩ | ⟨hx, rfl⟩) · exact ⟨fun h => hy (h ▸ rfl), Or.inl rfl⟩ · exact ⟨fun h => hx (h ▸ rfl), Or.inr rfl⟩ · rintro ⟨hxy, rfl | rfl⟩ · exact Or.inl ⟨rfl, hxy.symm⟩ · exact Or.inr ⟨hxy, rfl⟩
For any tree on 4 vertices, 2 ≤ ∑ v, (deg(v) choose 2) ≤ 3 automation
A general theorem bounds the sum of binomial coefficients of vertex degrees in any tree between |V| - 2 and (|V|-1 choose 2). Substituting |V| = 4 gives a lower bound of 4 - 2 = 2 and an upper bound of (3 choose 2) = 3. Linear arithmetic via omega confirms that the sum is bounded between 2 and 3.
uses
simple_graph_is_tree_card_sub_two_le_sum_choose_degree_le_choose/-- The only trees on four vertices are the path P4 and the star K_{1,3}. -/ theorem op223_tree_fin_four_iso_path_or_star (X : SimpleGraph (Fin 4)) (hX : X.IsTree) : Nonempty (X ≃g SimpleGraph.pathGraph 4) ∨ Nonempty (X ≃g completeBipartiteGraph (Fin 1) (Fin 3)) := by classical have hk : 2 ≤ Fintype.card (Fin 4) := by decide have hbounds := simple_graph_is_tree_card_sub_two_le_sum_choose_degree_le_choose X hX hk have hcard : Fintype.card (Fin 4) = 4 := rfl have hchoose : (4 - 1).choose 2 = 3 := by decide rw [hcard] at hbounds have h_le : 2 ≤ ∑ v, (X.degree v).choose 2 ∧ ∑ v, (X.degree v).choose 2 ≤ 3 := by omega
If ∑ v, (deg(v) choose 2) = 3, then X is isomorphic to K_{1,3}
When the degree sum achieves the upper bound 3 = (4 - 1 choose 2), the equality characterization for trees proves that X is a star graph centered at some vertex r. Composing this with op223_tree_fin_four_iso_path_or_star_starIso shows X is isomorphic to the complete bipartite graph K_{1,3}.
uses
eq_or_lt_of_le,simple_graph_is_tree_sum_choose_degree_eq_iff_star,op223_tree_fin_four_iso_path_or_star_starIsorcases eq_or_lt_of_le h_le.2 with h3 | hlt · -- sum is 3: star right have hsum : ∑ v, (X.degree v).choose 2 = (Fintype.card (Fin 4) - 1).choose 2 := by rw [hcard, hchoose] exact h3 rw [simple_graph_is_tree_sum_choose_degree_eq_iff_star X hX hk] at hsum obtain ⟨r, rfl⟩ := hsum exact ⟨op223_tree_fin_four_iso_path_or_star_starIso r⟩
If ∑ v, (deg(v) choose 2) < 3, then X is isomorphic to the path graph P₄ automation
Since the integer sum is at least 2 and strictly less than 3, omega deduces that the sum must equal 2 = 4 - 2. By the lower-bound equality characterization for trees, attaining |V| - 2 is equivalent to X being isomorphic to the path graph on 4 vertices.
uses
simple_graph_is_tree_sum_choose_degree_eq_iff_path· -- sum is 2: path left have h2 : ∑ v, (X.degree v).choose 2 = 2 := by omega have hsum : ∑ v, (X.degree v).choose 2 = Fintype.card (Fin 4) - 2 := by rw [hcard] exact h2 rw [simple_graph_is_tree_sum_choose_degree_eq_iff_path X hX hk] at hsum rw [hcard] at hsum exact hsum
Fintype.equivOfCardEq- Two finite types with the same cardinality are in bijection.
op223_tree_fin_four_iso_path_or_star_equiv- A bijection between Fin 4 and Fin 1 ⊕ Fin 3 mapping a designated vertex r to Sum.inl 0.
Equiv.swap_apply_left- The transposition swapping a and b maps a to b.
SimpleGraph.starGraph_adj- In a star graph with center r, two vertices are adjacent if and only if they are distinct and at least one of them equals r.
completeBipartiteGraph_adj- In a complete bipartite graph on types V and W, two vertices in V ⊕ W are adjacent if and only if one is in the left part and the other is in the right part.
op223_tree_fin_four_iso_path_or_star_equiv_apply_center- The equivalence op223_tree_fin_four_iso_path_or_star_equiv r maps the vertex r to Sum.inl 0.
simple_graph_is_tree_card_sub_two_le_sum_choose_degree_le_choose- For any tree on at least two vertices, the sum of binomial coefficients of vertex degrees ∑_v (deg(v) choose 2) is bounded between |V| - 2 and (|V| - 1 choose 2).
eq_or_lt_of_le- In any partial order, if a ≤ b then either a = b or a < b.
simple_graph_is_tree_sum_choose_degree_eq_iff_star- In a tree with at least two vertices, the sum of binomial coefficients of vertex degrees attains the upper bound (|V| - 1 choose 2) if and only if the graph is a star graph.
op223_tree_fin_four_iso_path_or_star_starIso- The star graph on Fin 4 centered at r is isomorphic to the complete bipartite graph K_{1,3} on Fin 1 and Fin 3.
simple_graph_is_tree_sum_choose_degree_eq_iff_path- In a tree with at least two vertices, the sum of binomial coefficients of vertex degrees attains the lower bound |V| - 2 if and only if the graph is isomorphic to a path graph on |V| vertices.
- The degree-sum bounds on trees and the numerical case analysis (2 ≤ S ≤ 3, leading to S = 2 or S = 3) rely on the Presburger arithmetic tactic `omega`.
- The lemmas establishing the star graph isomorphism (lines 10–44) are formal verifications that Mathlib's star graph on Fin 4 is isomorphic to the complete bipartite graph defined on the disjoint union Fin 1 ⊕ Fin 3.
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.
noncomputable def op223_tree_fin_four_iso_path_or_star_equiv (r : Fin 4) : Fin 4 ≃ Fin 1 ⊕ Fin 3 := let e₀ : Fin 4 ≃ Fin 1 ⊕ Fin 3 := Fintype.equivOfCardEq (by decide) e₀.trans (Equiv.swap (e₀ r) (Sum.inl 0))theorem op223_tree_fin_four_iso_path_or_star_equiv_apply_center (r : Fin 4) : op223_tree_fin_four_iso_path_or_star_equiv r r = Sum.inl 0 := by dsimp [op223_tree_fin_four_iso_path_or_star_equiv] exact Equiv.swap_apply_left _ _noncomputable def op223_tree_fin_four_iso_path_or_star_starIso (r : Fin 4) : SimpleGraph.starGraph r ≃g completeBipartiteGraph (Fin 1) (Fin 3) where toEquiv := op223_tree_fin_four_iso_path_or_star_equiv r map_rel_iff' {x y} := by rw [SimpleGraph.starGraph_adj, completeBipartiteGraph_adj] have hx : op223_tree_fin_four_iso_path_or_star_equiv r x = Sum.inl 0 ↔ x = r := by rw [← op223_tree_fin_four_iso_path_or_star_equiv_apply_center r] exact (op223_tree_fin_four_iso_path_or_star_equiv r).injective.eq_iff have hy : op223_tree_fin_four_iso_path_or_star_equiv r y = Sum.inl 0 ↔ y = r := by rw [← op223_tree_fin_four_iso_path_or_star_equiv_apply_center r] exact (op223_tree_fin_four_iso_path_or_star_equiv r).injective.eq_iff have h_left (z : Fin 1 ⊕ Fin 3) : z.isLeft = true ↔ z = Sum.inl 0 := by cases z with | inl a => fin_cases a simp | inr b => simp have h_right (z : Fin 1 ⊕ Fin 3) : z.isRight = true ↔ z ≠ Sum.inl 0 := by cases z with | inl a => fin_cases a simp | inr b => simp rw [h_left, h_right, h_left, h_right] have hx_ne : op223_tree_fin_four_iso_path_or_star_equiv r x ≠ Sum.inl 0 ↔ x ≠ r := not_iff_not.2 hx have hy_ne : op223_tree_fin_four_iso_path_or_star_equiv r y ≠ Sum.inl 0 ↔ y ≠ r := not_iff_not.2 hy rw [hx, hy, hx_ne, hy_ne] constructor · rintro (⟨rfl, hy⟩ | ⟨hx, rfl⟩) · exact ⟨fun h => hy (h ▸ rfl), Or.inl rfl⟩ · exact ⟨fun h => hx (h ▸ rfl), Or.inr rfl⟩ · rintro ⟨hxy, rfl | rfl⟩ · exact Or.inl ⟨rfl, hxy.symm⟩ · exact Or.inr ⟨hxy, rfl⟩/-- The only trees on four vertices are the path P4 and the star K_{1,3}. -/theorem op223_tree_fin_four_iso_path_or_star (X : SimpleGraph (Fin 4)) (hX : X.IsTree) : Nonempty (X ≃g SimpleGraph.pathGraph 4) ∨ Nonempty (X ≃g completeBipartiteGraph (Fin 1) (Fin 3)) := by classical have hk : 2 ≤ Fintype.card (Fin 4) := by decide have hbounds := simple_graph_is_tree_card_sub_two_le_sum_choose_degree_le_choose X hX hk have hcard : Fintype.card (Fin 4) = 4 := rfl have hchoose : (4 - 1).choose 2 = 3 := by decide rw [hcard] at hbounds have h_le : 2 ≤ ∑ v, (X.degree v).choose 2 ∧ ∑ v, (X.degree v).choose 2 ≤ 3 := by omega rcases eq_or_lt_of_le h_le.2 with h3 | hlt · -- sum is 3: star right have hsum : ∑ v, (X.degree v).choose 2 = (Fintype.card (Fin 4) - 1).choose 2 := by rw [hcard, hchoose] exact h3 rw [simple_graph_is_tree_sum_choose_degree_eq_iff_star X hX hk] at hsum obtain ⟨r, rfl⟩ := hsum exact ⟨op223_tree_fin_four_iso_path_or_star_starIso r⟩ · -- sum is 2: path left have h2 : ∑ v, (X.degree v).choose 2 = 2 := by omega have hsum : ∑ v, (X.degree v).choose 2 = Fintype.card (Fin 4) - 2 := by rw [hcard] exact h2 rw [simple_graph_is_tree_sum_choose_degree_eq_iff_path X hX hk] at hsum rw [hcard] at hsum exact hsum