AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_hop_top_iff

theoremverified

In a complete graph, the hops are exactly the derangements (fixed-point-free permutations).

Statement

theorem simple_graph_is_hop_top_iff {V : Type*} (h : Equiv.Perm V) :
    simple_graph_is_hop (⊤ : SimpleGraph V) h ↔ ∀ v, h v ≠ v
Source
Sanity lemma for hops, arXiv:2610.18463 (The group generated by a graph's derangements), Sec. 1 (in a complete graph every derangement is a hop).
Verified
15 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • simple_graph_is_hopA hop (graph derangement) of a graph G is a permutation h of the vertices that sends every vertex v to a neighbour h(v) of v.

The proof, explained

By definition, a permutation is a hop on a graph if every vertex is adjacent to its image. In the complete graph, two vertices are adjacent if and only if they are distinct, so being a hop means v ≠ h(v) for every vertex v. Applying the symmetry of inequality across all vertices shows that this is equivalent to h(v) ≠ v for all v, meaning h has no fixed points.

  1. A permutation h is a hop on the complete graph ⊤ if and only if v ≠ h(v) for all vertices v.

    By definition (`simple_graph_is_hop`), h is a hop if every vertex v is adjacent to h(v). In the complete graph ⊤, adjacency between two vertices is equivalent to their being distinct (`SimpleGraph.top_adj`), simplifying the hop condition directly to ∀ v, v ≠ h(v).

    line 3

    uses simple_graph_is_hop, SimpleGraph.top_adj

      simp only [simple_graph_is_hop, SimpleGraph.top_adj]
  2. The condition ∀ v, v ≠ h(v) is equivalent to ∀ v, h(v) ≠ v.

    For every vertex v, the inequality v ≠ h(v) is equivalent to h(v) ≠ v by symmetry of inequality (`ne_comm`). Passing this equivalence through the universal quantifier (`forall_congr'`) yields the claimed characterization.

    line 4

    uses forall_congr', ne_comm

      exact forall_congr' fun v => ne_comm
SimpleGraph.top_adj
Two vertices in the complete graph are adjacent if and only if they are distinct.
simple_graph_is_hop
A permutation h is a hop on a graph G if every vertex v is adjacent to h(v).
forall_congr'
If two predicates are pointwise equivalent, then their universal quantifications are equivalent.
ne_comm
Inequality is symmetric: a ≠ b is equivalent to b ≠ a.

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_is_hop_top_iff {V : Type*} (h : Equiv.Perm V) :    simple_graph_is_hop (⊤ : SimpleGraph V) h ↔ ∀ v, h v ≠ v := by  simp only [simple_graph_is_hop, SimpleGraph.top_adj]  exact forall_congr' fun v => ne_comm
See it in the graphDiscuss this resultChallenge it