AFTD Auto-Formalizing Theoretical Domains

is_graceful_tree_star_two

theoremverified

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.

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

    line 3

    uses SimpleGraph.isTree_starGraph, Equiv.refl

      refine ⟨SimpleGraph.isTree_starGraph 0, Equiv.refl _, ?_⟩
  2. 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.

    lines 4–6

      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.

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

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