AFTD Auto-Formalizing Theoretical Domains

simple_graph_two_le_card_of_connected_hop

theoremverified

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.

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

    lines 6–7

      by_contra hlt
      have hle : Fintype.card V ≤ 1 := by omega
  2. 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$.

    lines 8–9

    uses Fintype.card_le_one_iff.mp

      obtain ⟨v⟩ := hconn.nonempty
      have hv : h v = v := (Fintype.card_le_one_iff.mp hle) (h v) v
  3. 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.

    lines 10–11

    uses SimpleGraph.irrefl

      have 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

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