AFTD Auto-Formalizing Theoretical Domains

petrial_R_is_tree

theoremverified

For every natural number m, the graph R_m is a tree.

Statement

theorem petrial_R_is_tree (m : ℕ) : (petrial_R_graph m).IsTree
Source
arXiv:2611.07503 Section 3
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5

Read back from the Lean

For every natural number $m$, the graph petrial_R_graph m is a tree (i.e., it is connected and acyclic).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The graph R_m consists of a central hub vertex and m disjoint branches, where each branch is a 5-vertex path attached to the hub at its midpoint (vertex 2). To show that R_m is a tree, the proof applies the theorem that a finite graph is a tree if and only if it is connected and satisfies |E| + 1 = |V|. Connectedness is established by showing that every vertex can reach the central hub via its branch's midpoint. To count the edges, the proof establishes a bijection between the darts of R_m and the disjoint union of m incoming hub edges, m outgoing hub edges, and m copies of the darts of the 5-vertex path, yielding 10m darts and hence 5m undirected edges. Since the graph has 5m + 1 vertices, |E| + 1 = 5m + 1 = |V|, proving that R_m is a tree.

  1. The embedding of each 5-path fiber into R_m is defined, and proving connectedness of R_m is reduced to showing reachability between arbitrary vertices.

    For each branch index i < m, the map sending v to (i, v) preserves adjacency and defines a graph homomorphism from the 5-vertex path graph into R_m (petrial_R_is_tree_fiber_hom). Since the vertex set of R_m is nonempty (witnessed by the hub vertex none), SimpleGraph.Connected.mk reduces connectedness of R_m to showing that every pair of vertices u, v is mutually reachable.

    lines 1–8

    uses SimpleGraph.Connected.mk

    def petrial_R_is_tree_fiber_hom (m : ℕ) (i : Fin m) :
        SimpleGraph.pathGraph 5 →g petrial_R_graph m where
      toFun v := some (i, v)
      map_rel' h := ⟨rfl, h⟩
    
    theorem petrial_R_is_tree_connected (m : ℕ) : (petrial_R_graph m).Connected := by
      have : Nonempty (Option (Fin m × Fin 5)) := ⟨none⟩
      refine SimpleGraph.Connected.mk fun u v => ?_
  2. Every vertex of R_m can reach the central hub, and therefore R_m is connected.

    We first show that every vertex x can reach the central hub none (h_to_none). If x = none, this holds by reflexivity (SimpleGraph.Reachable.refl). If x = (i, v), since the 5-vertex path graph is connected (SimpleGraph.pathGraph_connected), vertex v can reach the midpoint vertex 2 in the path graph. Mapping this path along the fiber homomorphism petrial_R_is_tree_fiber_hom yields a path from (i, v) to (i, 2) in R_m. By definition of adjacency, (i, 2) is directly adjacent to none, so composing the path with this edge connects x to none. Finally, any two vertices u and v are connected by routing through the hub: u to none, then none to v.

    lines 9–19

    uses SimpleGraph.Reachable.refl, SimpleGraph.pathGraph_connected, petrial_R_is_tree_fiber_hom

      have h_to_none (x : Option (Fin m × Fin 5)) : (petrial_R_graph m).Reachable x none := by
        match x with
        | none => exact SimpleGraph.Reachable.refl none
        | some (i, v) =>
          have hr : (SimpleGraph.pathGraph 5).Reachable v 2 :=
            (SimpleGraph.pathGraph_connected 4).preconnected v 2
          have hr' : (petrial_R_graph m).Reachable (some (i, v)) (some (i, 2)) :=
            hr.map (petrial_R_is_tree_fiber_hom m i)
          have hadj : (petrial_R_graph m).Adj (some (i, 2)) none := rfl
          exact hr'.trans hadj.reachable
      exact (h_to_none u).trans (h_to_none v).symm
  3. The darts (directed edges) of R_m are in bijection with the disjoint union of m hub-inward darts, m hub-outward darts, and m copies of the darts of the 5-path graph.

    We construct an explicit equivalence petrial_R_is_tree_dart_equiv between the darts of R_m and Fin m ⊕ (Fin m ⊕ (Fin m × Dart(P_5))). An edge cannot have both endpoints at none (False.elim). An edge between none and (i, v) requires v = 2, identifying it with branch i (oriented either toward or away from none). An edge between two fiber vertices requires both endpoints to belong to the same branch i and form a dart of P_5. The inverse function builds darts from each component, and case analysis verifies that both compositions yield the identity.

    lines 20–46

    uses False.elim

    def petrial_R_is_tree_dart_equiv (m : ℕ) :
        (petrial_R_graph m).Dart ≃ Fin m ⊕ (Fin m ⊕ (Fin m × (SimpleGraph.pathGraph 5).Dart)) where
      toFun d :=
        match d with
        | ⟨(none, none), h⟩ => False.elim h
        | ⟨(none, some (i, v)), h⟩ =>
          Sum.inl i
        | ⟨(some (i, v), none), h⟩ =>
          Sum.inr (Sum.inl i)
        | ⟨(some (i₁, v₁), some (i₂, v₂)), h⟩ =>
          Sum.inr (Sum.inr (i₁, ⟨(v₁, v₂), h.2⟩))
      invFun x :=
        match x with
        | Sum.inl i => ⟨(none, some (i, 2)), rfl⟩
        | Sum.inr (Sum.inl i) => ⟨(some (i, 2), none), rfl⟩
        | Sum.inr (Sum.inr (i, d)) => ⟨(some (i, d.fst), some (i, d.snd)), ⟨rfl, d.adj⟩⟩
      left_inv d := by
        rcases d with ⟨⟨a, b⟩, h⟩
        rcases a with _ | ⟨i₁, v₁⟩ <;> rcases b with _ | ⟨i₂, v₂⟩
        · exact False.elim h
        · dsimp; cases h; rfl
        · dsimp; cases h; rfl
        · dsimp; obtain ⟨rfl, hadj⟩ := h; rfl
      right_inv x := by
        rcases x with i | (i | ⟨i, ⟨⟨v₁, v₂⟩, hadj⟩⟩) <;> rfl
    
  4. To show R_m is a tree, it suffices to prove the Euler characteristic formula |E(R_m)| + 1 = |V(R_m)|.

    By SimpleGraph.isTree_iff_connected_and_card, a finite graph is a tree if and only if it is connected and its number of edges plus 1 equals its number of vertices. Since connectedness was proved above in petrial_R_is_tree_connected, it remains only to verify the cardinality condition |E| + 1 = |V|.

    lines 47–50

    uses SimpleGraph.isTree_iff_connected_and_card, petrial_R_is_tree_connected

    /-- For every m, R_m is a tree. -/
    theorem petrial_R_is_tree (m : ℕ) : (petrial_R_graph m).IsTree := by
      rw [SimpleGraph.isTree_iff_connected_and_card]
      refine ⟨petrial_R_is_tree_connected m, ?_⟩
  5. The graph R_m has 10m darts, which implies 2|E(R_m)| = 10m.

    Direct evaluation shows that the 5-vertex path graph has 8 darts (h_path). Transporting cardinality across the dart equivalence petrial_R_is_tree_dart_equiv using Fintype.card_congr shows that R_m has m + m + 8m = 10m darts (h_dart). By SimpleGraph.dart_card_eq_twice_card_edges, the number of darts equals twice the number of undirected edges (2|E| = 10m). Rewriting with Nat.card_eq_fintype_card and SimpleGraph.card_edgeSet expresses this relation in terms of the cardinality of the edge set.

    lines 51–59

    uses Fintype.card_congr, petrial_R_is_tree_dart_equiv, SimpleGraph.dart_card_eq_twice_card_edges, Nat.card_eq_fintype_card, SimpleGraph.card_edgeSet

      have h_path : Fintype.card (SimpleGraph.pathGraph 5).Dart = 8 := by decide
      have h_dart : Fintype.card (petrial_R_graph m).Dart = 10 * m := by
        rw [Fintype.card_congr (petrial_R_is_tree_dart_equiv m)]
        simp [h_path]
        omega
      have hd := SimpleGraph.dart_card_eq_twice_card_edges (petrial_R_graph m)
      rw [h_dart] at hd
      have he : Nat.card ↑(petrial_R_graph m).edgeSet = (petrial_R_graph m).edgeFinset.card := by
        rw [Nat.card_eq_fintype_card, SimpleGraph.card_edgeSet]
  6. The vertex count is 5m + 1, and |E(R_m)| + 1 = |V(R_m)|, which proves that R_m is a tree.

    The vertex set Option (Fin m × Fin 5) has cardinality 1 + 5m = 5m + 1. Linear integer arithmetic (omega) combines |V| = 5m + 1 with 2|E| = 10m (which yields |E| = 5m) to deduce |E| + 1 = 5m + 1 = |V|, completing the proof that R_m is a tree.

    lines 60–62

      have hv : Nat.card (Option (Fin m × Fin 5)) = 5 * m + 1 := by
        simp; omega
      omega
Fintype.card_congr
An equivalence (bijection) between two finite types implies they have the same cardinality.
False.elim
From a contradiction (a proof of False), any conclusion follows.
Nat.card_eq_fintype_card
For any finite type, its cardinality as a natural number (Nat.card) equals its cardinality as a Fintype (Fintype.card).
SimpleGraph.Connected.mk
A graph on a nonempty vertex set is connected if every pair of vertices can reach each other.
SimpleGraph.Reachable.refl
Every vertex in a graph is reachable from itself by the empty path.
SimpleGraph.card_edgeSet
The cardinality of the edge set as a subtype equals the number of elements in the finite set of edges edgeFinset.
SimpleGraph.dart_card_eq_twice_card_edges
In any finite graph, the number of darts (directed edges) is twice the number of undirected edges.
SimpleGraph.isTree_iff_connected_and_card
A finite graph is a tree if and only if it is connected and its number of edges plus 1 equals its number of vertices.
SimpleGraph.pathGraph_connected
The path graph on n + 1 vertices is connected.
petrial_R_is_tree_connected
For any natural number m, the graph R_m is connected.
petrial_R_is_tree_dart_equiv
The darts of R_m are in bijection with the disjoint union of m hub-inward darts, m hub-outward darts, and m copies of the darts of the 5-vertex path graph.
petrial_R_is_tree_fiber_hom
For each i < m, the inclusion map sending vertex v of the 5-vertex path graph to (i, v) in R_m is a graph homomorphism.

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

def petrial_R_is_tree_fiber_hom (m : ℕ) (i : Fin m) :    SimpleGraph.pathGraph 5 →g petrial_R_graph m where  toFun v := some (i, v)  map_rel' h := ⟨rfl, h⟩theorem petrial_R_is_tree_connected (m : ℕ) : (petrial_R_graph m).Connected := by  have : Nonempty (Option (Fin m × Fin 5)) := ⟨none⟩  refine SimpleGraph.Connected.mk fun u v => ?_  have h_to_none (x : Option (Fin m × Fin 5)) : (petrial_R_graph m).Reachable x none := by    match x with    | none => exact SimpleGraph.Reachable.refl none    | some (i, v) =>      have hr : (SimpleGraph.pathGraph 5).Reachable v 2 :=        (SimpleGraph.pathGraph_connected 4).preconnected v 2      have hr' : (petrial_R_graph m).Reachable (some (i, v)) (some (i, 2)) :=        hr.map (petrial_R_is_tree_fiber_hom m i)      have hadj : (petrial_R_graph m).Adj (some (i, 2)) none := rfl      exact hr'.trans hadj.reachable  exact (h_to_none u).trans (h_to_none v).symmdef petrial_R_is_tree_dart_equiv (m : ℕ) :    (petrial_R_graph m).Dart ≃ Fin m ⊕ (Fin m ⊕ (Fin m × (SimpleGraph.pathGraph 5).Dart)) where  toFun d :=    match d with    | ⟨(none, none), h⟩ => False.elim h    | ⟨(none, some (i, v)), h⟩ =>      Sum.inl i    | ⟨(some (i, v), none), h⟩ =>      Sum.inr (Sum.inl i)    | ⟨(some (i₁, v₁), some (i₂, v₂)), h⟩ =>      Sum.inr (Sum.inr (i₁, ⟨(v₁, v₂), h.2⟩))  invFun x :=    match x with    | Sum.inl i => ⟨(none, some (i, 2)), rfl⟩    | Sum.inr (Sum.inl i) => ⟨(some (i, 2), none), rfl⟩    | Sum.inr (Sum.inr (i, d)) => ⟨(some (i, d.fst), some (i, d.snd)), ⟨rfl, d.adj⟩⟩  left_inv d := by    rcases d with ⟨⟨a, b⟩, h⟩    rcases a with _ | ⟨i₁, v₁⟩ <;> rcases b with _ | ⟨i₂, v₂⟩    · exact False.elim h    · dsimp; cases h; rfl    · dsimp; cases h; rfl    · dsimp; obtain ⟨rfl, hadj⟩ := h; rfl  right_inv x := by    rcases x with i | (i | ⟨i, ⟨⟨v₁, v₂⟩, hadj⟩⟩) <;> rfl/-- For every m, R_m is a tree. -/theorem petrial_R_is_tree (m : ℕ) : (petrial_R_graph m).IsTree := by  rw [SimpleGraph.isTree_iff_connected_and_card]  refine ⟨petrial_R_is_tree_connected m, ?_⟩  have h_path : Fintype.card (SimpleGraph.pathGraph 5).Dart = 8 := by decide  have h_dart : Fintype.card (petrial_R_graph m).Dart = 10 * m := by    rw [Fintype.card_congr (petrial_R_is_tree_dart_equiv m)]    simp [h_path]    omega  have hd := SimpleGraph.dart_card_eq_twice_card_edges (petrial_R_graph m)  rw [h_dart] at hd  have he : Nat.card ↑(petrial_R_graph m).edgeSet = (petrial_R_graph m).edgeFinset.card := by    rw [Nat.card_eq_fintype_card, SimpleGraph.card_edgeSet]  have hv : Nat.card (Option (Fin m × Fin 5)) = 5 * m + 1 := by    simp; omega  omega
See it in the graphDiscuss this resultChallenge it