petrial_R_is_tree
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
- petrial_R_graphFor any natural number m, R_m is the simple graph on the vertex type Option (Fin m × Fin 5) obtained by connecting a root vertex none to…
- inst_decidableRel_pathGraphAdjacency in the path graph
pathGraph nis decidable. - instDecidableRelPetrialRGraphAdjFor every natural number m, adjacency between vertices in the graph R_m is decidable.
- Arena.Reachable.transReachability is transitive.
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
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.
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.
uses
SimpleGraph.Connected.mkdef 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 => ?_
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.
uses
SimpleGraph.Reachable.refl,SimpleGraph.pathGraph_connected,petrial_R_is_tree_fiber_homhave 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
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.
uses
False.elimdef 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
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|.
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, ?_⟩
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.
uses
Fintype.card_congr,petrial_R_is_tree_dart_equiv,SimpleGraph.dart_card_eq_twice_card_edges,Nat.card_eq_fintype_card,SimpleGraph.card_edgeSethave 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]
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.
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.
- The dart count of the 5-vertex path graph (8 darts) is established computationally by the decide tactic.
- The linear arithmetic relating the counts of darts, edges, and vertices (10m = 2|E| and |V| = 5m + 1, yielding |E| + 1 = |V|) is discharged automatically by Lean's omega tactic.
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.
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