AFTD Auto-Formalizing Theoretical Domains

op223_tree_fin_four_iso_path_or_star

theoremverified

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
Used by 1

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}.

  1. 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.

    lines 1–4

    uses Fintype.equivOfCardEq

    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))
    
  2. 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.

    lines 5–9

    uses op223_tree_fin_four_iso_path_or_star_equiv, Equiv.swap_apply_left

    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 _ _
    
  3. 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.

    lines 10–20

    uses SimpleGraph.starGraph_adj, completeBipartiteGraph_adj, op223_tree_fin_four_iso_path_or_star_equiv_apply_center

    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
  4. 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.

    lines 21–33

        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]
  5. 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.

    lines 34–44

        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⟩
    
  6. 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.

    lines 45–56

    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
  7. 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}.

    lines 57–65

    uses eq_or_lt_of_le, simple_graph_is_tree_sum_choose_degree_eq_iff_star, op223_tree_fin_four_iso_path_or_star_starIso

      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⟩
  8. 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.

    lines 66–74

    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.

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

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
See it in the graphDiscuss this resultChallenge it