simple_graph_two_le_card_of_connected_hop
Every connected simple graph on a finite vertex set that admits a hop has at least two vertices.
Statement
theorem simple_graph_two_le_card_of_connected_hop {V : Type*} [Fintype V] (G : SimpleGraph V) (hconn : G.Connected) (h : Equiv.Perm V) (hh : simple_graph_is_hop G h) : 2 ≤ Fintype.card V
- Source
- arXiv:2610.18463, Section 1
- Verified
- 27 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.
Read back from the Lean
For any finite type V, any simple graph G on V, assuming G is connected (G.Connected), and for any permutation h of V such that h is a hop on G (i.e., every vertex v is adjacent to h v), the cardinality of V is at least 2.
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 proof proceeds by contradiction. If a connected finite simple graph has fewer than two vertices, its vertex set must have size at most one, yet it contains a vertex because connected graphs are nonempty. The assumed hop permutation must therefore fix this unique vertex. But the hop property requires every vertex to be adjacent to its image, which forces a self-loop, contradicting the irreflexivity of simple graphs.
We may assume for contradiction that the vertex set has at most one element, $|V| \le 1$.
We argue by contradiction, assuming the negation $\neg (2 \le |V|)$. By linear arithmetic on natural numbers (`omega`), this is equivalent to $|V| \le 1$.
by_contra hlt have hle : Fintype.card V ≤ 1 := by omega
There exists a vertex $v \in V$ that is fixed by $h$, so $h(v) = v$.
Because $G$ is connected, its vertex set $V$ is nonempty, so we obtain a vertex $v \in V$. Since $|V| \le 1$, any two elements in $V$ are equal by `Fintype.card_le_one_iff.mp`. Applying this to $h(v)$ and $v$ yields $h(v) = v$.
uses
Fintype.card_le_one_iff.mpobtain ⟨v⟩ := hconn.nonempty have hv : h v = v := (Fintype.card_le_one_iff.mp hle) (h v) v
A contradiction is reached, as $v$ would be adjacent to itself in a simple graph.
By definition of a hop, every vertex $u$ satisfies $G.\mathrm{Adj}(u, h(u))$. Specializing to $u = v$ and simplifying using $h(v) = v$ shows that $v$ is adjacent to itself. However, simple graphs are loopless (`SimpleGraph.irrefl`), which contradicts this self-loop and finishes the proof.
uses
SimpleGraph.irreflhave hvv : G.Adj v v := by simpa [hv] using hh v exact SimpleGraph.irrefl G hvv
Fintype.card_le_one_iff.mp- If a finite type has cardinality at most 1, then any two of its elements are equal.
SimpleGraph.irrefl- In a simple graph, no vertex is adjacent to itself (adjacency is irreflexive).
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.
/-- Every connected finite simple graph admitting a hop has at least two vertices. -/theorem simple_graph_two_le_card_of_connected_hop {V : Type*} [Fintype V] (G : SimpleGraph V) (hconn : G.Connected) (h : Equiv.Perm V) (hh : simple_graph_is_hop G h) : 2 ≤ Fintype.card V := by by_contra hlt have hle : Fintype.card V ≤ 1 := by omega obtain ⟨v⟩ := hconn.nonempty have hv : h v = v := (Fintype.card_le_one_iff.mp hle) (h v) v have hvv : G.Adj v v := by simpa [hv] using hh v exact SimpleGraph.irrefl G hvv