simple_graph_power_one
G^1 = G.
Statement
theorem simple_graph_power_one {V : Type*} (G : SimpleGraph V) : simple_graph_power G 1 = G
- Source
- Sanity lemma for simple_graph_power (arXiv:2610.09300 (On graphs whose powers are well-covered)).
- Verified
- 11 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…
- Used by 7
- is_mutual_visibility_set_emptyThe empty set of vertices in any simple graph G is a mutual-visibility set.
- forall_power_well_covered_of_well_covered_diam_le_twoLet G be a finite connected well-covered graph of diameter at most 2. Then G^d is well-covered for every d ≥ 1.
- cycle_seven_power_one_well_coveredThe first power (the graph itself) of the 7-cycle graph is well-covered.
- bot_isTwoKTwoFreeThe empty graph on any vertex type is 2K₂-free.
- forall_power_well_covered_of_well_covered_diam_le_threeLet G be a finite connected simple graph of diameter at most 3. If G and its second power G^2 are both well-covered, then every positive…
- bipartite_all_powers_well_covered_diameter_le_twoEvery finite connected bipartite simple graph G with at least two vertices whose positive integer powers G^d (for d ≥ 1) are all…
- is_linear_forest_botThe empty simple graph on any vertex type is a linear forest.
The proof, explained
The 1-power of a simple graph G connects distinct vertices whose graph distance is at most 1. By graph extensionality, this equals G because two vertices are distinct and at distance at most 1 if and only if their distance is exactly 1, which is equivalent to adjacency in G.
To show G^1 = G, it suffices to show that any two vertices u and v are adjacent in G^1 if and only if they are adjacent in G.
By extensionality for simple graphs (ext), two graphs are equal if they have the same adjacency relation on all pairs of vertices. Unfolding the definition of simple_graph_power, u and v are adjacent in G^1 if and only if u ≠ v and G.edist u v ≤ 1. We then split the equivalence into two implications.
ext u v simp only [simple_graph_power] constructor
If u ≠ v and G.edist u v ≤ 1, then G.edist u v ≠ 0.
Assume u ≠ v and G.edist u v ≤ 1. If their distance were 0, SimpleGraph.edist_eq_zero_iff.1 would imply u = v, contradicting u ≠ v.
uses
SimpleGraph.edist_eq_zero_iff.1· rintro ⟨hne, hle⟩ have h0 : G.edist u v ≠ 0 := by intro h; exact hne (SimpleGraph.edist_eq_zero_iff.1 h)If u and v are adjacent in G^1, then they are adjacent in G.
Since G.edist u v ≠ 0, Order.one_le_iff_ne_zero.2 gives 1 ≤ G.edist u v. Together with G.edist u v ≤ 1, antisymmetry (le_antisymm) forces G.edist u v = 1. By SimpleGraph.edist_eq_one_iff_adj.1, two vertices at distance 1 are adjacent in G.
uses
le_antisymm,Order.one_le_iff_ne_zero.2,SimpleGraph.edist_eq_one_iff_adj.1have h1 : G.edist u v = 1 := by have : G.edist u v ≤ 1 := by exact_mod_cast hle exact le_antisymm this (Order.one_le_iff_ne_zero.2 h0) exact SimpleGraph.edist_eq_one_iff_adj.1 h1
If u and v are adjacent in G, then they are adjacent in G^1.
Assume u and v are adjacent in G. In a simple graph, adjacent vertices are distinct (u ≠ v). Furthermore, adjacent vertices have distance 1 by SimpleGraph.edist_eq_one_iff_adj.2, so G.edist u v ≤ 1. Both conditions for adjacency in G^1 are satisfied.
uses
SimpleGraph.edist_eq_one_iff_adj.2· intro h exact ⟨h.ne, by rw [SimpleGraph.edist_eq_one_iff_adj.2 h]; simp⟩
SimpleGraph.edist_eq_zero_iff.1- If the extended distance between two vertices in a simple graph is 0, then the vertices are equal.
le_antisymm- If a ≤ b and b ≤ a in a partial order, then a = b.
Order.one_le_iff_ne_zero.2- In a discrete ordered structure, a non-zero element is at least 1.
SimpleGraph.edist_eq_one_iff_adj.1- If the extended distance between two vertices in a simple graph is 1, then they are adjacent.
SimpleGraph.edist_eq_one_iff_adj.2- If two vertices in a simple graph are adjacent, then their extended distance is 1.
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.
theorem simple_graph_power_one {V : Type*} (G : SimpleGraph V) : simple_graph_power G 1 = G := by ext u v simp only [simple_graph_power] constructor · rintro ⟨hne, hle⟩ have h0 : G.edist u v ≠ 0 := by intro h; exact hne (SimpleGraph.edist_eq_zero_iff.1 h) have h1 : G.edist u v = 1 := by have : G.edist u v ≤ 1 := by exact_mod_cast hle exact le_antisymm this (Order.one_le_iff_ne_zero.2 h0) exact SimpleGraph.edist_eq_one_iff_adj.1 h1 · intro h exact ⟨h.ne, by rw [SimpleGraph.edist_eq_one_iff_adj.2 h]; simp⟩