is_graceful_tree_star_two
The two-vertex star tree on Fin 2 is a graceful tree.
Statement
theorem is_graceful_tree_star_two : is_graceful_tree (SimpleGraph.starGraph (0 : Fin 2))- Source
- arXiv:2611.01340 Section 1
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_graceful_treeA tree G on a finite vertex type W is graceful if there exists a bijection f : W ≃ Fin (Fintype.card W) such that for all edges {u₁, v₁}…
Read back from the Lean
The star graph on the vertex type Fin 2 centered at 0 is a graceful tree; that is, it is a tree (connected and acyclic), and there exists a bijection f : Fin 2 ≃ Fin 2 such that for all vertices u₁, v₁, u₂, v₂ : Fin 2, if u₁ is adjacent to v₁ and u₂ is adjacent to v₂, and Nat.dist (f u₁) (f v₁) = Nat.dist (f u₂) (f v₂), then the unordered edge s(u₁, v₁) equals s(u₂, v₂).
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
To prove that the two-vertex star tree is graceful, we show it is a tree and exhibit a graceful labeling. The star graph is a tree by SimpleGraph.isTree_starGraph, and we choose the identity map on Fin 2 as the labeling bijection via Equiv.refl. Because Fin 2 has only two vertices, any two edges with distinct endpoints are identical, so the graceful distinct-weights condition holds trivially.
The star graph on Fin 2 is a tree, and the identity map on Fin 2 serves as a candidate graceful labeling.
A graph is a graceful tree if it is a tree and admits a bijection to Fin (cardinality) such that the absolute differences of labels across edges are distinct. We instantiate the tree property using SimpleGraph.isTree_starGraph 0 and supply the identity bijection Equiv.refl (Fin 2) as the candidate labeling, leaving the obligation to verify that equal edge weights imply identical edges.
uses
SimpleGraph.isTree_starGraph,Equiv.reflrefine ⟨SimpleGraph.isTree_starGraph 0, Equiv.refl _, ?_⟩Any two edges in the star graph on Fin 2 with the same weight are identical.
We introduce two edges u₁ ~ v₁ and u₂ ~ v₂ whose endpoints have equal distances under the identity labeling. Because a simple graph has no self-loops, u₁ ≠ v₁ and u₂ ≠ v₂ (from h1.ne and h2.ne). On a two-element set Fin 2, there is only one pair of distinct elements: for all a ≠ b and c ≠ d in Fin 2, the unordered pairs s(a, b) and s(c, d) are equal, which is checked by finite evaluation (decide). Applying this to u₁, v₁ and u₂, v₂ shows s(u₁, v₁) = s(u₂, v₂), concluding the proof.
intro u₁ v₁ u₂ v₂ h1 h2 _ have : ∀ a b c d : Fin 2, a ≠ b → c ≠ d → s(a, b) = s(c, d) := by decide exact this u₁ v₁ u₂ v₂ h1.ne h2.ne
SimpleGraph.isTree_starGraph- For any vertex r, the star graph centered at r is a tree.
Equiv.refl- The identity equivalence (bijection) from a type to itself.
- The auxiliary claim on line 5 that any two pairs of distinct elements in Fin 2 form the same edge is proved by `decide`, which exhaustively checks all cases by finite computation.
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.
/-- Sanity check: the star tree on 2 vertices (a single edge) is graceful. -/theorem is_graceful_tree_star_two : is_graceful_tree (SimpleGraph.starGraph (0 : Fin 2)) := by refine ⟨SimpleGraph.isTree_starGraph 0, Equiv.refl _, ?_⟩ intro u₁ v₁ u₂ v₂ h1 h2 _ have : ∀ a b c d : Fin 2, a ≠ b → c ≠ d → s(a, b) = s(c, d) := by decide exact this u₁ v₁ u₂ v₂ h1.ne h2.ne