AFTD Auto-Formalizing Theoretical Domains

simple_graph_power_one

theoremverified

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

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.

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

    lines 3–5

      ext u v
      simp only [simple_graph_power]
      constructor
  2. 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.

    lines 6–8

    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)
  3. 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.

    lines 9–12

    uses le_antisymm, Order.one_le_iff_ne_zero.2, SimpleGraph.edist_eq_one_iff_adj.1

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

    lines 13–14

    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

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