star_graph_power_two_eq_top
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 ⊤.
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).
uses
SimpleGraph.starGraph,SimpleGraph.fromRel_adjhave 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]
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.
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_nilhave 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)
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.
uses
simple_graph_power,SimpleGraph.starGraph,SimpleGraph.top_adjext u v simp only [simple_graph_power, SimpleGraph.starGraph, SimpleGraph.top_adj]
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`.
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.
- Graph distances (`edist`) in Mathlib are valued in the extended natural numbers `ℕ∞` (which includes `∞` for disconnected pairs), so natural number bounds such as 2 are formally coerced to `ℕ∞`.
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.
/-- 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⟩