AFTD Auto-Formalizing Theoretical Domains

simple_graph_edgeSet_is_leap_closed

theoremverified

For any simple graph G, its full edge set E(G) is leap-closed.

Statement

theorem simple_graph_edgeSet_is_leap_closed {V : Type*} (G : SimpleGraph V) :
    simple_graph_is_leap_closed G G.edgeSet
Source
arXiv:2610.18463 Question 5.9
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • simple_graph_is_leap_closedAn edge subset F of a simple graph G is leap-closed (leap-maximal) if F is a subset of the edge set of G and for every edge e in E(G) \ F,…
  • simple_graph_leap_groupThe leap group Λ₁(G) of a graph G: the subgroup of the symmetric group on the vertices generated by the hops of G.

Read back from the Lean

For every type V and every simple graph G on V, the full edge set G.edgeSet is leap closed with respect to G.

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

By definition, a set of edges $F$ is leap-closed in a simple graph $G$ if $F \subseteq E(G)$ and every edge in $E(G) \setminus F$ strictly increases the leap group when added to $F$. When $F = E(G)$, the inclusion $E(G) \subseteq E(G)$ holds trivially by reflexivity, and the second condition holds vacuously because the set difference $E(G) \setminus E(G)$ is empty.

  1. The edge set $E(G)$ is a subset of itself, reducing the goal to the condition on edges in $E(G) \setminus E(G)$.

    By definition, a set of edges $F$ is leap-closed if $F \subseteq E(G)$ and every edge in $E(G) \setminus F$ strictly enlarges the leap group when added to $F$. The first conjunct $E(G) \subseteq E(G)$ holds trivially by reflexivity of inclusion (`subset_rfl`), leaving only the second condition to verify.

    line 4

    uses subset_rfl

      refine ⟨subset_rfl, ?_⟩
  2. The condition on edges in $E(G) \setminus E(G)$ holds vacuously.

    Assume an edge $e$ belongs to the set difference $E(G) \setminus E(G)$ (`intro e he`). By definition of set difference, the hypothesis $he$ asserts both $e \in E(G)$ ($he.1$) and $e \notin E(G)$ ($he.2$). Applying the negation to the membership assumption yields a contradiction, from which the goal follows immediately by the principle of explosion (`False.elim`).

    lines 5–6

    uses False.elim

      intro e he
      exact False.elim (he.2 he.1)
subset_rfl
Every element of a preorder (such as a set under inclusion) is less than or equal to itself ($a \subseteq a$).
False.elim
From a contradiction (falsehood), any proposition follows.

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

/-- The ground edge set of a simple graph is leap-closed. -/theorem simple_graph_edgeSet_is_leap_closed {V : Type*} (G : SimpleGraph V) :    simple_graph_is_leap_closed G G.edgeSet := by  refine ⟨subset_rfl, ?_⟩  intro e he  exact False.elim (he.2 he.1)
See it in the graphDiscuss this resultChallenge it