AFTD Auto-Formalizing Theoretical Domains

star_graph_power_two_eq_top

theoremverified

For any natural number m, the square of the star graph on m + 1 vertices is the complete graph.

Statement

theorem star_graph_power_two_eq_top (m : ℕ) :
    simple_graph_power (SimpleGraph.starGraph (0 : Fin (m + 1))) 2 = ⊤
Source
arXiv:2610.13852 Theorem 6.3 proof
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • simple_graph_powerThe d-th power G^d of a graph G: same vertices, two distinct vertices adjacent iff they are joined by a path (equivalently a walk) of…

Read back from the Lean

For every natural number $m$, the 2-step power of the star graph on $\mathrm{Fin}(m + 1)$ centered at $0$ (that is, the graph on $\mathrm{Fin}(m + 1)$ whose edges connect distinct vertices at graph distance at most 2 in the star graph) is equal to the complete graph $\top$ on $\mathrm{Fin}(m + 1)$.

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 power G² connects any two distinct vertices whose extended distance in G is at most 2. In a star graph centered at 0, every other vertex is adjacent to 0, so any two distinct vertices u and v have distance at most 2: if either is 0, they are adjacent (distance 1); otherwise, the walk u → 0 → v gives distance at most 2. Therefore, every pair of distinct vertices is adjacent in the square graph, which means the square graph coincides with the complete graph ⊤.

  1. Two vertices in the star graph centered at 0 are adjacent if and only if they are distinct and at least one of them is 0.

    Unfolding the definition of `SimpleGraph.starGraph` (which is defined via `SimpleGraph.fromRel` with the relation that the first vertex equals 0) and simplifying with `SimpleGraph.fromRel_adj` yields that two vertices a and b are adjacent if and only if a ≠ b and (a = 0 ∨ b = 0).

    lines 4–6

    uses SimpleGraph.starGraph, SimpleGraph.fromRel_adj

      have hadj : ∀ a b : Fin (m+1), (SimpleGraph.starGraph (0 : Fin (m+1))).Adj a b ↔ a ≠ b ∧ (a = 0 ∨ b = 0) := by
        intro a b
        simp [SimpleGraph.starGraph, SimpleGraph.fromRel_adj]
  2. The extended distance between any two distinct vertices in the star graph is at most 2.

    Given distinct vertices u and v, we case split on whether each vertex is the center 0 using `eq_or_ne`. If u = 0, then u and v are adjacent by `hadj`, so the single-edge walk from u to v (`SimpleGraph.Walk.cons ... SimpleGraph.Walk.nil`) has length 1, giving edist u v ≤ 1 ≤ 2 by `SimpleGraph.Walk.edist_le`. Symmetrically, if u ≠ 0 and v = 0, they are adjacent and the distance is at most 1 ≤ 2. Finally, if neither u nor v is 0, both are adjacent to 0 by `hadj`, forming a two-step walk u → 0 → v of length 2, which implies edist u v ≤ 2.

    lines 7–24

    uses eq_or_ne, Or.inl, Or.inr, SimpleGraph.Walk.edist_le, SimpleGraph.Walk.cons, SimpleGraph.Walk.nil, SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_nil

      have hdist : ∀ u v : Fin (m+1), u ≠ v →
          (SimpleGraph.starGraph (0 : Fin (m + 1))).edist u v ≤ ((2:ℕ) : ℕ∞) := by
        intro u v h
        rcases eq_or_ne u 0 with hu | hu
        · have hav : (SimpleGraph.starGraph (0 : Fin (m+1))).Adj u v := (hadj u v).2 ⟨h, Or.inl hu⟩
          have h1 := SimpleGraph.Walk.edist_le (SimpleGraph.Walk.cons hav SimpleGraph.Walk.nil)
          simp only [SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_nil] at h1
          exact h1.trans (by simp)
        · rcases eq_or_ne v 0 with hv | hv
          · have hav : (SimpleGraph.starGraph (0 : Fin (m+1))).Adj u v := (hadj u v).2 ⟨h, Or.inr hv⟩
            have h1 := SimpleGraph.Walk.edist_le (SimpleGraph.Walk.cons hav SimpleGraph.Walk.nil)
            simp only [SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_nil] at h1
            exact h1.trans (by simp)
          · have hav1 : (SimpleGraph.starGraph (0 : Fin (m+1))).Adj u 0 := (hadj u 0).2 ⟨hu, Or.inr rfl⟩
            have hav2 : (SimpleGraph.starGraph (0 : Fin (m+1))).Adj 0 v := (hadj 0 v).2 ⟨fun hh => hv hh.symm, Or.inl rfl⟩
            have h1 := SimpleGraph.Walk.edist_le (SimpleGraph.Walk.cons hav1 (SimpleGraph.Walk.cons hav2 SimpleGraph.Walk.nil))
            simp only [SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_nil] at h1
            exact h1.trans (by simp)
  3. By extensionality, proving the square of the star graph is ⊤ reduces to showing that for any vertices u and v, adjacency in the square graph is equivalent to u ≠ v.

    By graph extensionality (`ext`), two simple graphs are equal if they share the same adjacency relation. Simplifying with the definitions of `simple_graph_power`, `SimpleGraph.starGraph`, and `SimpleGraph.top_adj` reduces the equality to showing that u ≠ v ∧ edist u v ≤ 2 is equivalent to u ≠ v.

    lines 25–26

    uses simple_graph_power, SimpleGraph.starGraph, SimpleGraph.top_adj

      ext u v
      simp only [simple_graph_power, SimpleGraph.starGraph, SimpleGraph.top_adj]
  4. Two vertices are distinct if and only if they are distinct and have distance at most 2 in the star graph.

    We prove both directions of the equivalence (`constructor`). In the forward direction, an edge in the graph square implies u ≠ v by definition (`h.1`). In the backward direction, if u ≠ v, the distance bound edist u v ≤ 2 is provided by the helper lemma `hdist`.

    lines 27–29

      constructor
      · intro h; exact h.1
      · intro h; exact ⟨h, hdist u v h⟩
SimpleGraph.starGraph
The star graph on a vertex type with a specified center vertex, where edges connect the center to every other vertex.
SimpleGraph.fromRel_adj
Two vertices are adjacent in the simple graph induced by a binary relation r if and only if they are distinct and either r v w or r w v holds.
eq_or_ne
For any two terms x and y, either x = y or x ≠ y (excluded middle for equality).
Or.inl
From a proof of a, infer the disjunction a ∨ b.
Or.inr
From a proof of b, infer the disjunction a ∨ b.
SimpleGraph.Walk.edist_le
The extended distance between two vertices in a graph is bounded above by the length of any walk connecting them.
SimpleGraph.Walk.cons
Prepends an edge between adjacent vertices u and v to a walk from v to w, producing a walk from u to w.
SimpleGraph.Walk.nil
The empty walk from a vertex u to itself, having length 0.
SimpleGraph.Walk.length_cons
Prepending an edge to a walk increases its length by 1.
SimpleGraph.Walk.length_nil
The length of the trivial walk from a vertex to itself is 0.
simple_graph_power
The d-th power of a simple graph G, in which two distinct vertices are adjacent if and only if their extended distance in G is at most d.
SimpleGraph.top_adj
In the complete graph ⊤, two vertices are adjacent if and only if they are distinct.

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

/-- The square of a star graph on m + 1 vertices is the complete graph. -/theorem star_graph_power_two_eq_top (m : ℕ) :    simple_graph_power (SimpleGraph.starGraph (0 : Fin (m + 1))) 2 = ⊤ := by  have hadj : ∀ a b : Fin (m+1), (SimpleGraph.starGraph (0 : Fin (m+1))).Adj a b ↔ a ≠ b ∧ (a = 0 ∨ b = 0) := by    intro a b    simp [SimpleGraph.starGraph, SimpleGraph.fromRel_adj]  have hdist : ∀ u v : Fin (m+1), u ≠ v →      (SimpleGraph.starGraph (0 : Fin (m + 1))).edist u v ≤ ((2:ℕ) : ℕ∞) := by    intro u v h    rcases eq_or_ne u 0 with hu | hu    · have hav : (SimpleGraph.starGraph (0 : Fin (m+1))).Adj u v := (hadj u v).2 ⟨h, Or.inl hu⟩      have h1 := SimpleGraph.Walk.edist_le (SimpleGraph.Walk.cons hav SimpleGraph.Walk.nil)      simp only [SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_nil] at h1      exact h1.trans (by simp)    · rcases eq_or_ne v 0 with hv | hv      · have hav : (SimpleGraph.starGraph (0 : Fin (m+1))).Adj u v := (hadj u v).2 ⟨h, Or.inr hv⟩        have h1 := SimpleGraph.Walk.edist_le (SimpleGraph.Walk.cons hav SimpleGraph.Walk.nil)        simp only [SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_nil] at h1        exact h1.trans (by simp)      · have hav1 : (SimpleGraph.starGraph (0 : Fin (m+1))).Adj u 0 := (hadj u 0).2 ⟨hu, Or.inr rfl⟩        have hav2 : (SimpleGraph.starGraph (0 : Fin (m+1))).Adj 0 v := (hadj 0 v).2 ⟨fun hh => hv hh.symm, Or.inl rfl⟩        have h1 := SimpleGraph.Walk.edist_le (SimpleGraph.Walk.cons hav1 (SimpleGraph.Walk.cons hav2 SimpleGraph.Walk.nil))        simp only [SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_nil] at h1        exact h1.trans (by simp)  ext u v  simp only [simple_graph_power, SimpleGraph.starGraph, SimpleGraph.top_adj]  constructor  · intro h; exact h.1  · intro h; exact ⟨h, hdist u v h⟩
See it in the graphDiscuss this resultChallenge it