simple_graph_completeGraph_three_leap_closed_not_intersection_closed
The collection of leap-closed edge subsets of the complete graph K₃ on 3 vertices is not closed under intersection.
Statement
theorem simple_graph_completeGraph_three_leap_closed_not_intersection_closed :
∃ F₁ F₂ : Set (Sym2 (Fin 3)),
simple_graph_is_leap_closed (⊤ : SimpleGraph (Fin 3)) F₁ ∧
simple_graph_is_leap_closed (⊤ : SimpleGraph (Fin 3)) F₂ ∧
¬ simple_graph_is_leap_closed (⊤ : SimpleGraph (Fin 3)) (F₁ ∩ F₂)- Source
- arXiv:2610.18463 Question 5.9
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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.
- simple_graph_is_hop_mem_leap_groupEvery hop lies in the leap group.
- 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.
- Used by 1
- simple_graph_hop_or_leap_maximal_not_matroid_flatsNeither the collection of hop-closed edge subsets nor the collection of leap-closed edge subsets forms the set of flats of a matroid for…
Read back from the Lean
There exist two sets of unordered pairs of vertices in Fin 3, $F₁$ and $F₂$, such that both $F₁$ and $F₂$ are leap-closed in the complete graph on Fin 3 (⊤ : SimpleGraph (Fin 3)), but their intersection $F₁ ∩ F₂$ is not leap-closed in that complete graph.
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 theorem is proved by exhibiting an explicit counterexample in the complete graph K₃ on vertices {0, 1, 2}: the two 2-edge paths F₁ = {s(0,1), s(0,2)} and F₂ = {s(0,1), s(1,2)}. Neither path admits any hop permutations because injectivity would force both degree-1 vertices to map to the central vertex, so their leap groups are trivial (⊥); adding their unique missing edge completes K₃, whose leap group is non-trivial (containing the 3-cycle rotation), so both F₁ and F₂ are leap-closed. However, their intersection is the single edge {s(0,1)}, which also has trivial leap group, and adding s(0,2) to it yields the path F₁, whose leap group is still trivial, contradicting the strict increase required for leap-closedness.
In the path with edge set {s(0,1), s(0,2)}, any neighbor of vertex 1 must be 0.
Exhaustive case analysis on x ∈ Fin 3 shows that s(1, x) ∈ {s(0,1), s(0,2)} only holds when x = 0.
fin_cases x <;> simp_allIn the path with edge set {s(0,1), s(0,2)}, any neighbor of vertex 2 must be 0.
Exhaustive case analysis on x ∈ Fin 3 shows that s(2, x) ∈ {s(0,1), s(0,2)} only holds when x = 0.
fin_cases x <;> simp_allIn the path with edge set {s(0,1), s(1,2)}, any neighbor of vertex 0 must be 1.
Exhaustive case analysis on x ∈ Fin 3 shows that s(0, x) ∈ {s(0,1), s(1,2)} only holds when x = 1.
fin_cases x <;> simp_allIn the path with edge set {s(0,1), s(1,2)}, any neighbor of vertex 2 must be 1.
Exhaustive case analysis on x ∈ Fin 3 shows that s(2, x) ∈ {s(0,1), s(1,2)} only holds when x = 1.
fin_cases x <;> simp_allIn the graph with single edge {s(0,1)}, vertex 2 has no neighbors.
Checking each vertex in Fin 3 confirms that no edge s(2, x) is equal to s(0,1).
fin_cases x <;> simp_allThe two-edge path 1–0–2 with edge set {s(0,1), s(0,2)} has no hop permutations.
If h were a hop, vertices 1 and 2 would both have to map to their unique neighbor 0, so h(1) = 0 and h(2) = 0. By injectivity of h, this implies 1 = 2, which is impossible.
uses
SimpleGraph.fromEdgeSet_adj,simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_path_a,simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_path_bintro hh have h1 := hh 1 rw [SimpleGraph.fromEdgeSet_adj] at h1 have h2 := hh 2 rw [SimpleGraph.fromEdgeSet_adj] at h2 exact absurd (h.injective ((simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_path_a (h 1) h1.1).trans (simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_path_b (h 2) h2.1).symm)) (by decide)
The two-edge path 0–1–2 with edge set {s(0,1), s(1,2)} has no hop permutations.
If h were a hop, vertices 0 and 2 would both have to map to their unique neighbor 1, so h(0) = 1 and h(2) = 1. By injectivity of h, this implies 0 = 2, which is impossible.
uses
SimpleGraph.fromEdgeSet_adj,simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_path_c,simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_path_dintro hh have h1 := hh 0 rw [SimpleGraph.fromEdgeSet_adj] at h1 have h2 := hh 2 rw [SimpleGraph.fromEdgeSet_adj] at h2 exact absurd (h.injective ((simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_path_c (h 0) h1.1).trans (simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_path_d (h 2) h2.1).symm)) (by decide)
The graph consisting of the single edge {s(0,1)} has no hop permutations.
A hop must map every vertex to an adjacent vertex, but vertex 2 is isolated in this graph and has no neighbors.
uses
SimpleGraph.fromEdgeSet_adj,simple_graph_completeGraph_three_leap_closed_not_intersection_closed_not_mem_singleintro hh have h2 := hh 2 rw [SimpleGraph.fromEdgeSet_adj] at h2 exact simple_graph_completeGraph_three_leap_closed_not_intersection_closed_not_mem_single (h 2) h2.1
If a graph on Fin 3 has no hop permutations, its leap group is trivial.
The leap group is the subgroup generated by all hops. When no hops exist, the generating set is empty, so its subgroup closure is the trivial subgroup ⊥.
uses
simple_graph_leap_group,Subgroup.closure_eq_bot_iffrw [simple_graph_leap_group, Subgroup.closure_eq_bot_iff] intro h hh exact absurd hh (hG h)
Every edge of the complete graph K₃ on Fin 3 is s(0,1), s(0,2), or s(1,2).
Edges of K₃ are non-diagonal unordered pairs s(a, b) with a ≠ b. Testing all pairs of vertices in Fin 3 confirms that only these three unordered pairs arise.
uses
SimpleGraph.edgeSet_top,Sym2.ind,Set.mem_compl_iff,Sym2.mem_diagSet,Sym2.mk_isDiag_iffrw [SimpleGraph.edgeSet_top] at he induction e using Sym2.ind with | h a b => simp only [Set.mem_compl_iff, Sym2.mem_diagSet, Sym2.mk_isDiag_iff] at he fin_cases a <;> fin_cases b <;> simp_all
An unordered pair s(v, w) belongs to {s(0,1), s(0,2), s(1,2)} if and only if v ≠ w.
Exhaustive case analysis over all pairs of vertices in Fin 3 establishes the equivalence.
fin_cases v <;> fin_cases w <;> simp_allAny edge set containing the three edges {s(0,1), s(0,2), s(1,2)} gives the complete graph K₃.
Two vertices v and w are adjacent in K₃ precisely when v ≠ w, in which case s(v, w) belongs to {s(0,1), s(0,2), s(1,2)} and hence to any superset S.
uses
SimpleGraph.fromEdgeSet_adj,SimpleGraph.top_adj,simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_three_edgesext v w rw [SimpleGraph.fromEdgeSet_adj, SimpleGraph.top_adj] exact ⟨fun h => h.2, fun h => ⟨hS (by rw [simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_three_edges]; exact h), h⟩⟩
The leap group of the complete graph K₃ is non-trivial.
The 3-cycle rotation permutation finRotate 3 maps each vertex to a distinct vertex. In the complete graph K₃, any two distinct vertices are adjacent, so the rotation is a hop. Since finRotate 3 is not the identity, the leap group containing it cannot be trivial.
uses
simple_graph_is_hop_mem_leap_group,SimpleGraph.top_adj,Subgroup.mem_botintro hbot have hmem : finRotate 3 ∈ simple_graph_leap_group (⊤ : SimpleGraph (Fin 3)) := simple_graph_is_hop_mem_leap_group _ _ (by intro v rw [SimpleGraph.top_adj] fin_cases v <;> decide) rw [hbot, Subgroup.mem_bot] at hmem exact absurd hmem (by decide)
The intersection of {s(0,1), s(0,2)} and {s(0,1), s(1,2)} is the single-edge set {s(0,1)}.
Evaluating set membership on all unordered pairs of vertices in Fin 3 shows that s(0,1) is the unique common edge.
uses
Sym2.indext x induction x using Sym2.ind with | h a b => fin_cases a <;> fin_cases b <;> simp_all
Choose F₁ = {s(0,1), s(0,2)} and F₂ = {s(0,1), s(1,2)}, and verify that F₁ is a subset of the edges of K₃.
We provide F₁ and F₂ as witnesses for the existential claim. Checking both elements s(0,1) and s(0,2) shows they connect distinct vertices, hence belong to the edge set of K₃.
uses
Set.mem_insert_iff,Set.mem_singleton_iff,SimpleGraph.mem_edgeSet,SimpleGraph.top_adjrefine ⟨({s(0,1), s(0,2)} : Set (Sym2 (Fin 3))), ({s(0,1), s(1,2)} : Set (Sym2 (Fin 3))), ?_, ?_, ?_⟩ · refine ⟨?_, ?_⟩ · intro x hx simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hx rcases hx with rfl | rfl <;> rw [SimpleGraph.mem_edgeSet, SimpleGraph.top_adj] <;> decide
The edge set F₁ is leap-closed in K₃.
The only edge of K₃ not in F₁ is s(1,2). The leap group of F₁ is trivial because F₁ has no hops. Adding s(1,2) to F₁ yields all edges of K₃, whose leap group is non-trivial, so the leap group strictly increases.
uses
simple_graph_completeGraph_three_leap_closed_not_intersection_closed_edge_cases,simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_eq_bot,simple_graph_completeGraph_three_leap_closed_not_intersection_closed_hop_free_path_a,bot_lt_iff_ne_bot,simple_graph_completeGraph_three_leap_closed_not_intersection_closed_fromEdgeSet_eq_top,simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_top_ne_bot· intro e he obtain ⟨heE, heF⟩ := he have he12 : e = s(1,2) := by rcases simple_graph_completeGraph_three_leap_closed_not_intersection_closed_edge_cases e heE with h | h | h · rw [h] at heF; simp at heF · rw [h] at heF; simp at heF · exact h rw [simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_eq_bot _ simple_graph_completeGraph_three_leap_closed_not_intersection_closed_hop_free_path_a, he12, bot_lt_iff_ne_bot] have hg : SimpleGraph.fromEdgeSet (insert s(1,2) ({s(0,1), s(0,2)} : Set (Sym2 (Fin 3)))) = ⊤ := simple_graph_completeGraph_three_leap_closed_not_intersection_closed_fromEdgeSet_eq_top _ (by intro x hx; simp at hx ⊢; tauto) rw [hg] exact simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_top_ne_bot
The edge set F₂ is a subset of the edges of K₃.
Both edges s(0,1) and s(1,2) connect distinct vertices, so F₂ ⊆ E(K₃).
uses
Set.mem_insert_iff,Set.mem_singleton_iff,SimpleGraph.mem_edgeSet,SimpleGraph.top_adj· refine ⟨?_, ?_⟩ · intro x hx simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hx rcases hx with rfl | rfl <;> rw [SimpleGraph.mem_edgeSet, SimpleGraph.top_adj] <;> decide
The edge set F₂ is leap-closed in K₃.
The only edge of K₃ not in F₂ is s(0,2). The leap group of F₂ is trivial because F₂ has no hops. Adding s(0,2) to F₂ yields the complete graph K₃, whose leap group is non-trivial, so the leap group strictly increases.
uses
simple_graph_completeGraph_three_leap_closed_not_intersection_closed_edge_cases,simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_eq_bot,simple_graph_completeGraph_three_leap_closed_not_intersection_closed_hop_free_path_b,bot_lt_iff_ne_bot,simple_graph_completeGraph_three_leap_closed_not_intersection_closed_fromEdgeSet_eq_top,simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_top_ne_bot· intro e he obtain ⟨heE, heF⟩ := he have he02 : e = s(0,2) := by rcases simple_graph_completeGraph_three_leap_closed_not_intersection_closed_edge_cases e heE with h | h | h · rw [h] at heF; simp at heF · exact h · rw [h] at heF; simp at heF rw [simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_eq_bot _ simple_graph_completeGraph_three_leap_closed_not_intersection_closed_hop_free_path_b, he02, bot_lt_iff_ne_bot] have hg : SimpleGraph.fromEdgeSet (insert s(0,2) ({s(0,1), s(1,2)} : Set (Sym2 (Fin 3)))) = ⊤ := simple_graph_completeGraph_three_leap_closed_not_intersection_closed_fromEdgeSet_eq_top _ (by intro x hx; simp at hx ⊢; tauto) rw [hg] exact simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_top_ne_bot
If F₁ ∩ F₂ = {s(0,1)} were leap-closed, adding s(0,2) would strictly enlarge its leap group from ⊥.
The intersection simplifies to the single-edge set {s(0,1)}. If it were leap-closed, adding the missing edge s(0,2) would strictly increase its leap group, which is ⊥ since the single-edge graph is hop-free.
uses
simple_graph_completeGraph_three_leap_closed_not_intersection_closed_inter_eq,simple_graph_is_leap_closed,SimpleGraph.mem_edgeSet,SimpleGraph.top_adj,simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_eq_bot,simple_graph_completeGraph_three_leap_closed_not_intersection_closed_hop_free_single· rw [simple_graph_completeGraph_three_leap_closed_not_intersection_closed_inter_eq] simp only [simple_graph_is_leap_closed] rintro ⟨-, hcond⟩ have hmem : s(0,2) ∈ (⊤ : SimpleGraph (Fin 3)).edgeSet \ ({s(0,1)} : Set (Sym2 (Fin 3))) := by refine ⟨?_, ?_⟩ · rw [SimpleGraph.mem_edgeSet, SimpleGraph.top_adj]; decide · simp have hlt := hcond s(0,2) hmem rw [simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_eq_bot _ simple_graph_completeGraph_three_leap_closed_not_intersection_closed_hop_free_single] at hlt
The intersection F₁ ∩ F₂ is not leap-closed, concluding the proof.
The augmented edge set {s(0,2), s(0,1)} is the two-edge path F₁, which also has trivial leap group ⊥. This yields ⊥ < ⊥, contradicting the irreflexivity of <.
uses
Set.mem_insert_iff,Set.mem_singleton_iff,simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_eq_bot,simple_graph_completeGraph_three_leap_closed_not_intersection_closed_hop_free_path_a,lt_irreflhave hg : SimpleGraph.fromEdgeSet (insert s(0,2) ({s(0,1)} : Set (Sym2 (Fin 3)))) = SimpleGraph.fromEdgeSet ({s(0,1), s(0,2)} : Set (Sym2 (Fin 3))) := by congr 1 ext x simp only [Set.mem_insert_iff, Set.mem_singleton_iff] tauto rw [hg, simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_eq_bot _ simple_graph_completeGraph_three_leap_closed_not_intersection_closed_hop_free_path_a] at hlt exact lt_irrefl ⊥ hlt
bot_lt_iff_ne_bot- The bottom element ⊥ is strictly less than a if and only if a ≠ ⊥.
lt_irrefl- Strict inequality is irreflexive: no element is strictly less than itself.
Set.mem_compl_iff- An element belongs to the complement of a set if and only if it does not belong to the set.
Set.mem_insert_iff- An element belongs to insert a s if and only if it equals a or belongs to s.
Set.mem_singleton_iff- An element belongs to the singleton {b} if and only if it equals b.
SimpleGraph.fromEdgeSet_adj- In a graph constructed from an edge set, two vertices are adjacent if and only if their unordered pair is in the edge set and they are distinct.
SimpleGraph.mem_edgeSet- An unordered pair s(v, w) belongs to the edge set of a graph if and only if v and w are adjacent.
SimpleGraph.edgeSet_top- The edge set of the complete graph consists of all non-diagonal unordered pairs.
SimpleGraph.top_adj- Two vertices are adjacent in the complete graph if and only if they are distinct.
simple_graph_completeGraph_three_leap_closed_not_intersection_closed_edge_cases- Every edge of the complete graph K₃ on Fin 3 is one of s(0,1), s(0,2), or s(1,2).
simple_graph_completeGraph_three_leap_closed_not_intersection_closed_fromEdgeSet_eq_top- Any edge set containing the three edges of K₃ defines the complete graph.
simple_graph_completeGraph_three_leap_closed_not_intersection_closed_hop_free_path_a- The two-edge path with edge set {s(0,1), s(0,2)} has no hop permutations.
simple_graph_completeGraph_three_leap_closed_not_intersection_closed_hop_free_path_b- The two-edge path with edge set {s(0,1), s(1,2)} has no hop permutations.
simple_graph_completeGraph_three_leap_closed_not_intersection_closed_hop_free_single- The graph consisting of the single edge {s(0,1)} has no hop permutations.
simple_graph_completeGraph_three_leap_closed_not_intersection_closed_inter_eq- The intersection of {s(0,1), s(0,2)} and {s(0,1), s(1,2)} is {s(0,1)}.
simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_eq_bot- If a graph on Fin 3 has no hops, its leap group is trivial.
simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_top_ne_bot- The leap group of the complete graph K₃ on Fin 3 is non-trivial.
simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_path_a- In the path with edge set {s(0,1), s(0,2)}, any neighbor of vertex 1 must be 0.
simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_path_b- In the path with edge set {s(0,1), s(0,2)}, any neighbor of vertex 2 must be 0.
simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_path_c- In the path with edge set {s(0,1), s(1,2)}, any neighbor of vertex 0 must be 1.
simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_path_d- In the path with edge set {s(0,1), s(1,2)}, any neighbor of vertex 2 must be 1.
simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_three_edges- An unordered pair of vertices in Fin 3 belongs to {s(0,1), s(0,2), s(1,2)} if and only if the vertices are distinct.
simple_graph_completeGraph_three_leap_closed_not_intersection_closed_not_mem_single- In the single-edge graph with edge {s(0,1)}, vertex 2 has no neighbors.
simple_graph_is_hop_mem_leap_group- Every hop permutation of a simple graph belongs to its leap group.
simple_graph_is_leap_closed- An edge subset F of G is leap-closed if adding any missing edge of G strictly increases the leap group.
simple_graph_leap_group- The leap group of a simple graph is the subgroup generated by all its hop permutations.
Subgroup.closure_eq_bot_iff- The subgroup generated by a set is trivial if and only if every element in the generating set is the identity.
Subgroup.mem_bot- An element belongs to the trivial subgroup ⊥ if and only if it is the identity element 1.
Sym2.ind- Induction principle for unordered pairs: a property holds for all pairs in Sym₂(α) if it holds for s(x, y) for all x, y.
Sym2.mem_diagSet- A pair in Sym₂(α) is in the diagonal set if and only if it is diagonal.
Sym2.mk_isDiag_iff- An unordered pair s(x, y) is diagonal if and only if x = y.
- Properties of small subgraphs on Fin 3 (such as edge membership, neighborhood determinations, and absence of fixed points) are verified mechanically by exhaustive case analysis (`fin_cases`) and decision procedures (`decide`, `simp_all`).
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.
open scoped Sym2/-- In the path 1–0–2, vertex 1 has only neighbour 0. -/private lemma simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_path_a (x : Fin 3) (hx : s(1, x) ∈ ({s(0,1), s(0,2)} : Set (Sym2 (Fin 3)))) : x = 0 := by fin_cases x <;> simp_all/-- In the path 1–0–2, vertex 2 has only neighbour 0. -/private lemma simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_path_b (x : Fin 3) (hx : s(2, x) ∈ ({s(0,1), s(0,2)} : Set (Sym2 (Fin 3)))) : x = 0 := by fin_cases x <;> simp_all/-- In the path 0–1–2, vertex 0 has only neighbour 1. -/private lemma simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_path_c (x : Fin 3) (hx : s(0, x) ∈ ({s(0,1), s(1,2)} : Set (Sym2 (Fin 3)))) : x = 1 := by fin_cases x <;> simp_all/-- In the path 0–1–2, vertex 2 has only neighbour 1. -/private lemma simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_path_d (x : Fin 3) (hx : s(2, x) ∈ ({s(0,1), s(1,2)} : Set (Sym2 (Fin 3)))) : x = 1 := by fin_cases x <;> simp_all/-- In the single-edge graph on 0–1, vertex 2 has no neighbour. -/private lemma simple_graph_completeGraph_three_leap_closed_not_intersection_closed_not_mem_single (x : Fin 3) (hx : s(2, x) ∈ ({s(0,1)} : Set (Sym2 (Fin 3)))) : False := by fin_cases x <;> simp_all/-- The path 1–0–2 has no hop: both leaves would have to be sent to the middle vertex 0. -/private lemma simple_graph_completeGraph_three_leap_closed_not_intersection_closed_hop_free_path_a (h : Equiv.Perm (Fin 3)) : ¬ simple_graph_is_hop (SimpleGraph.fromEdgeSet ({s(0,1), s(0,2)} : Set (Sym2 (Fin 3)))) h := by intro hh have h1 := hh 1 rw [SimpleGraph.fromEdgeSet_adj] at h1 have h2 := hh 2 rw [SimpleGraph.fromEdgeSet_adj] at h2 exact absurd (h.injective ((simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_path_a (h 1) h1.1).trans (simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_path_b (h 2) h2.1).symm)) (by decide)/-- The path 0–1–2 has no hop: both leaves would have to be sent to the middle vertex 1. -/private lemma simple_graph_completeGraph_three_leap_closed_not_intersection_closed_hop_free_path_b (h : Equiv.Perm (Fin 3)) : ¬ simple_graph_is_hop (SimpleGraph.fromEdgeSet ({s(0,1), s(1,2)} : Set (Sym2 (Fin 3)))) h := by intro hh have h1 := hh 0 rw [SimpleGraph.fromEdgeSet_adj] at h1 have h2 := hh 2 rw [SimpleGraph.fromEdgeSet_adj] at h2 exact absurd (h.injective ((simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_path_c (h 0) h1.1).trans (simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_path_d (h 2) h2.1).symm)) (by decide)/-- The graph with the single edge 0–1 has no hop (vertex 2 is isolated). -/private lemma simple_graph_completeGraph_three_leap_closed_not_intersection_closed_hop_free_single (h : Equiv.Perm (Fin 3)) : ¬ simple_graph_is_hop (SimpleGraph.fromEdgeSet ({s(0,1)} : Set (Sym2 (Fin 3)))) h := by intro hh have h2 := hh 2 rw [SimpleGraph.fromEdgeSet_adj] at h2 exact simple_graph_completeGraph_three_leap_closed_not_intersection_closed_not_mem_single (h 2) h2.1/-- A hop-free graph has trivial leap group. -/private lemma simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_eq_bot (G : SimpleGraph (Fin 3)) (hG : ∀ h, ¬ simple_graph_is_hop G h) : simple_graph_leap_group G = ⊥ := by rw [simple_graph_leap_group, Subgroup.closure_eq_bot_iff] intro h hh exact absurd hh (hG h)/-- The three edges of `K₃` on `Fin 3` are `{0,1}`, `{0,2}` and `{1,2}`. -/private lemma simple_graph_completeGraph_three_leap_closed_not_intersection_closed_edge_cases (e : Sym2 (Fin 3)) (he : e ∈ (⊤ : SimpleGraph (Fin 3)).edgeSet) : e = s(0,1) ∨ e = s(0,2) ∨ e = s(1,2) := by rw [SimpleGraph.edgeSet_top] at he induction e using Sym2.ind with | h a b => simp only [Set.mem_compl_iff, Sym2.mem_diagSet, Sym2.mk_isDiag_iff] at he fin_cases a <;> fin_cases b <;> simp_all/-- A pair of distinct vertices of `Fin 3` is one of the three edges of `K₃`. -/private lemma simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_three_edges (v w : Fin 3) : s(v, w) ∈ ({s(0,1), s(0,2), s(1,2)} : Set (Sym2 (Fin 3))) ↔ v ≠ w := by fin_cases v <;> fin_cases w <;> simp_all/-- Any edge set containing the three edges of `K₃` gives the complete graph. -/private lemma simple_graph_completeGraph_three_leap_closed_not_intersection_closed_fromEdgeSet_eq_top (S : Set (Sym2 (Fin 3))) (hS : ({s(0,1), s(0,2), s(1,2)} : Set (Sym2 (Fin 3))) ⊆ S) : SimpleGraph.fromEdgeSet S = ⊤ := by ext v w rw [SimpleGraph.fromEdgeSet_adj, SimpleGraph.top_adj] exact ⟨fun h => h.2, fun h => ⟨hS (by rw [simple_graph_completeGraph_three_leap_closed_not_intersection_closed_mem_three_edges]; exact h), h⟩⟩/-- The leap group of `K₃` is nontrivial: the 3-cycle is a hop. -/private lemma simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_top_ne_bot : simple_graph_leap_group (⊤ : SimpleGraph (Fin 3)) ≠ ⊥ := by intro hbot have hmem : finRotate 3 ∈ simple_graph_leap_group (⊤ : SimpleGraph (Fin 3)) := simple_graph_is_hop_mem_leap_group _ _ (by intro v rw [SimpleGraph.top_adj] fin_cases v <;> decide) rw [hbot, Subgroup.mem_bot] at hmem exact absurd hmem (by decide)/-- The two spanning paths `{0,1},{0,2}` and `{0,1},{1,2}` meet in the single edge `{0,1}`. -/private lemma simple_graph_completeGraph_three_leap_closed_not_intersection_closed_inter_eq : (({s(0,1), s(0,2)} : Set (Sym2 (Fin 3))) ∩ {s(0,1), s(1,2)}) = {s(0,1)} := by ext x induction x using Sym2.ind with | h a b => fin_cases a <;> fin_cases b <;> simp_all/-- Leap-closed edge subsets of K₃ are not closed under intersection. -/theorem simple_graph_completeGraph_three_leap_closed_not_intersection_closed : ∃ F₁ F₂ : Set (Sym2 (Fin 3)), simple_graph_is_leap_closed (⊤ : SimpleGraph (Fin 3)) F₁ ∧ simple_graph_is_leap_closed (⊤ : SimpleGraph (Fin 3)) F₂ ∧ ¬ simple_graph_is_leap_closed (⊤ : SimpleGraph (Fin 3)) (F₁ ∩ F₂) := by refine ⟨({s(0,1), s(0,2)} : Set (Sym2 (Fin 3))), ({s(0,1), s(1,2)} : Set (Sym2 (Fin 3))), ?_, ?_, ?_⟩ · refine ⟨?_, ?_⟩ · intro x hx simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hx rcases hx with rfl | rfl <;> rw [SimpleGraph.mem_edgeSet, SimpleGraph.top_adj] <;> decide · intro e he obtain ⟨heE, heF⟩ := he have he12 : e = s(1,2) := by rcases simple_graph_completeGraph_three_leap_closed_not_intersection_closed_edge_cases e heE with h | h | h · rw [h] at heF; simp at heF · rw [h] at heF; simp at heF · exact h rw [simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_eq_bot _ simple_graph_completeGraph_three_leap_closed_not_intersection_closed_hop_free_path_a, he12, bot_lt_iff_ne_bot] have hg : SimpleGraph.fromEdgeSet (insert s(1,2) ({s(0,1), s(0,2)} : Set (Sym2 (Fin 3)))) = ⊤ := simple_graph_completeGraph_three_leap_closed_not_intersection_closed_fromEdgeSet_eq_top _ (by intro x hx; simp at hx ⊢; tauto) rw [hg] exact simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_top_ne_bot · refine ⟨?_, ?_⟩ · intro x hx simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hx rcases hx with rfl | rfl <;> rw [SimpleGraph.mem_edgeSet, SimpleGraph.top_adj] <;> decide · intro e he obtain ⟨heE, heF⟩ := he have he02 : e = s(0,2) := by rcases simple_graph_completeGraph_three_leap_closed_not_intersection_closed_edge_cases e heE with h | h | h · rw [h] at heF; simp at heF · exact h · rw [h] at heF; simp at heF rw [simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_eq_bot _ simple_graph_completeGraph_three_leap_closed_not_intersection_closed_hop_free_path_b, he02, bot_lt_iff_ne_bot] have hg : SimpleGraph.fromEdgeSet (insert s(0,2) ({s(0,1), s(1,2)} : Set (Sym2 (Fin 3)))) = ⊤ := simple_graph_completeGraph_three_leap_closed_not_intersection_closed_fromEdgeSet_eq_top _ (by intro x hx; simp at hx ⊢; tauto) rw [hg] exact simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_top_ne_bot · rw [simple_graph_completeGraph_three_leap_closed_not_intersection_closed_inter_eq] simp only [simple_graph_is_leap_closed] rintro ⟨-, hcond⟩ have hmem : s(0,2) ∈ (⊤ : SimpleGraph (Fin 3)).edgeSet \ ({s(0,1)} : Set (Sym2 (Fin 3))) := by refine ⟨?_, ?_⟩ · rw [SimpleGraph.mem_edgeSet, SimpleGraph.top_adj]; decide · simp have hlt := hcond s(0,2) hmem rw [simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_eq_bot _ simple_graph_completeGraph_three_leap_closed_not_intersection_closed_hop_free_single] at hlt have hg : SimpleGraph.fromEdgeSet (insert s(0,2) ({s(0,1)} : Set (Sym2 (Fin 3)))) = SimpleGraph.fromEdgeSet ({s(0,1), s(0,2)} : Set (Sym2 (Fin 3))) := by congr 1 ext x simp only [Set.mem_insert_iff, Set.mem_singleton_iff] tauto rw [hg, simple_graph_completeGraph_three_leap_closed_not_intersection_closed_leap_group_eq_bot _ simple_graph_completeGraph_three_leap_closed_not_intersection_closed_hop_free_path_a] at hlt exact lt_irrefl ⊥ hlt