simple_graph_is_hop_top_iff
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.
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).
uses
simple_graph_is_hop,SimpleGraph.top_adjsimp only [simple_graph_is_hop, SimpleGraph.top_adj]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.
uses
forall_congr',ne_commexact 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
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_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