simple_graph_edgeSet_is_leap_closed
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.
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.
uses
subset_rflrefine ⟨subset_rfl, ?_⟩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`).
uses
False.elimintro 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
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.
/-- 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)