simple_graph_completeGraph_three_hop_closed_not_intersection_closed
The collection of hop-closed edge subsets of the complete graph K₃ on 3 vertices is not closed under intersection.
Statement
theorem simple_graph_completeGraph_three_hop_closed_not_intersection_closed :
∃ F₁ F₂ : Set (Sym2 (Fin 3)),
simple_graph_is_hop_closed (⊤ : SimpleGraph (Fin 3)) F₁ ∧
simple_graph_is_hop_closed (⊤ : SimpleGraph (Fin 3)) F₂ ∧
¬ simple_graph_is_hop_closed (⊤ : SimpleGraph (Fin 3)) (F₁ ∩ F₂)- Source
- arXiv:2610.18463 Question 5.9
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- simple_graph_is_hop_closedAn edge subset F of a finite simple graph G is hop-closed (hop-maximal) if F is a subset of the edge set of G and for every edge e in E(G)…
- 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 edge subsets $F_1, F_2 \subseteq \operatorname{Sym2}(\operatorname{Fin} 3)$ such that both $F_1$ and $F_2$ are hop-closed with respect to the complete graph $\top$ on $\operatorname{Fin} 3$, but their intersection $F_1 \cap F_2$ is not hop-closed with respect to $\top$. Here, a set of edges $F$ is defined to be hop-closed in a simple graph $G$ on a finite vertex type $V$ if: 1. $F \subseteq G.\operatorname{edgeSet}$, and 2. for every edge $e \in G.\operatorname{edgeSet} \setminus F$, the number (cardinality) of permutations $h \in \operatorname{Perm}(V)$ such that each vertex $v$ is adjacent to $h(v)$ in the graph induced by $F$ is strictly less than the number of such permutations in the graph induced by $F \cup \{e\}$.
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
To show that the collection of hop-closed edge subsets of the complete graph K₃ on 3 vertices is not closed under intersection, the proof exhibits two explicit edge subsets s₁ = {e₀₁, e₁₂} and s₂ = {e₁₂, e₀₂}. In K₃, a hop (a permutation mapping every vertex to an adjacent vertex) must be a 3-cycle derangement, which requires all three edges of K₃. Both s₁ and s₂ have 2 edges and admit 0 hops, but adding their unique missing edge forms the complete graph with 2 hops; since 0 < 2, both subsets are hop-closed. Their intersection s₁ ∩ s₂ = {e₁₂} has only 1 edge and 0 hops, and adding the missing edge e₀₁ yields 2 edges which still admit 0 hops; since 0 < 0 is false, the intersection is not hop-closed.
For any graph on 3 vertices with decidable adjacency, the hop predicate on permutations is decidable
Unfolding the definition of a hop (`simple_graph_is_hop G h`), the condition asserts that every vertex v satisfies G.Adj v (h v). Since Fin 3 is finite and adjacency is decidable, universal quantification over Fin 3 is decidable by typeclass synthesis (`infer_instance`).
fun h => by unfold simple_graph_is_hop; infer_instance
The edge set of K₃ consists precisely of the three edges e₀₁, e₀₂, and e₁₂
By extensionality, an unordered pair e is an edge of the complete graph ⊤ on Fin 3 if and only if its two endpoints a and b are distinct. Induction on e via `Sym2.ind` reduces this to checking pairs s(a, b). Exhausting all 9 pairs of vertices in Fin 3 via `fin_cases` and applying the symmetry of unordered pairs (`Sym2.eq_swap`) confirms that a ≠ b holds exactly when s(a, b) is one of s(0, 1), s(0, 2), or s(1, 2).
uses
Sym2.ind,edgeSet_top,Sym2.mem_diagSet,Sym2.mk_isDiag_iff,Set.mem_compl_iff,Set.mem_insert_iff,Set.mem_singleton_iff,Sym2.eq_swapext e induction e using Sym2.ind with | _ a b => simp only [edgeSet_top, Sym2.mem_diagSet, Sym2.mk_isDiag_iff, Set.mem_compl_iff, Set.mem_insert_iff, Set.mem_singleton_iff, simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e01, simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e02, simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e12] fin_cases a <;> fin_cases b <;> simp [Sym2.eq_swap]
The set difference of K₃'s edge set and s₁ is the singleton {e₀₂}
Rewriting the edge set of K₃ with the previous lemma, an edge belongs to the complement of s₁ = {e₀₁, e₁₂} if and only if it is in {e₀₁, e₀₂, e₁₂} but not in s₁. In the forward direction, e = e₀₁ and e = e₁₂ immediately contradict non-membership in s₁, leaving e = e₀₂. In the reverse direction, e₀₂ is in the edge set and distinct from both e₀₁ and e₁₂, which is verified by `decide`.
uses
simple_graph_completeGraph_three_hop_closed_not_intersection_closed_edgeSet_top,Finset.coe_insert,Finset.coe_singleton,Set.mem_sdiff,Set.mem_insert_iff,Set.mem_singleton_iff,Or.inl,Or.inrrw [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_edgeSet_top] ext e simp only [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1, Finset.coe_insert, Finset.coe_singleton, Set.mem_sdiff, Set.mem_insert_iff, Set.mem_singleton_iff] constructor · rintro ⟨h1 | h1 | h1, h2⟩ · exfalso; exact h2 (Or.inl h1) · exact h1 · exfalso; exact h2 (Or.inr h1) · rintro rfl refine ⟨Or.inr (Or.inl rfl), ?_⟩ intro h rcases h with h | h <;> revert h <;> decide
The set difference of K₃'s edge set and s₂ is the singleton {e₀₁}
Rewriting the edge set of K₃, an edge is in the complement of s₂ = {e₁₂, e₀₂} if and only if it is in {e₀₁, e₀₂, e₁₂} but not in s₂. Ruling out the edges in s₂ leaves only e₀₁. In reverse, e₀₁ is in K₃'s edge set and distinct from both e₁₂ and e₀₂ by `decide`.
uses
simple_graph_completeGraph_three_hop_closed_not_intersection_closed_edgeSet_top,Finset.coe_insert,Finset.coe_singleton,Set.mem_sdiff,Set.mem_insert_iff,Set.mem_singleton_iff,Or.inl,Or.inrrw [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_edgeSet_top] ext e simp only [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2, Finset.coe_insert, Finset.coe_singleton, Set.mem_sdiff, Set.mem_insert_iff, Set.mem_singleton_iff] constructor · rintro ⟨h1 | h1 | h1, h2⟩ · exact h1 · exfalso; exact h2 (Or.inr h1) · exfalso; exact h2 (Or.inl h1) · rintro rfl refine ⟨Or.inl rfl, ?_⟩ intro h rcases h with h | h <;> revert h <;> decide
The edge set s₁ is hop-closed in K₃
Unfolding `simple_graph_is_hop_closed`, there are two requirements: first, s₁ ⊆ ⊤.edgeSet, which holds since both e₀₁ and e₁₂ belong to K₃'s edge set. Second, for every edge in ⊤.edgeSet \ s₁ (which is solely e₀₂), adding that edge must strictly increase the hop count. Converting the cardinalities of permutations to finite type card computations via `Nat.card_eq_fintype_card`, `decide` evaluates that the graph on s₁ (having 2 edges) has 0 hops, whereas adding e₀₂ forms the full K₃ which has 2 hops. Since 0 < 2, the inequality holds.
uses
simple_graph_completeGraph_three_hop_closed_not_intersection_closed_edgeSet_top,Finset.coe_insert,Finset.coe_singleton,Set.mem_insert_iff,Set.mem_singleton_iff,simple_graph_completeGraph_three_hop_closed_not_intersection_closed_diff_s1,Nat.card_eq_fintype_cardunfold simple_graph_is_hop_closed refine ⟨?_, ?_⟩ · rw [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_edgeSet_top] intro x hx simp only [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1, Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff, Set.mem_singleton_iff] at hx rcases hx with rfl | rfl <;> simp · intro e he rw [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_diff_s1, Set.mem_singleton_iff] at he subst he have h_card1 : Nat.card {h : Equiv.Perm (Fin 3) // simple_graph_is_hop (SimpleGraph.fromEdgeSet (simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1 : Set (Sym2 (Fin 3)))) h} = 0 := by rw [Nat.card_eq_fintype_card]; decide have h_card2 : Nat.card {h : Equiv.Perm (Fin 3) // simple_graph_is_hop (SimpleGraph.fromEdgeSet (insert simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e02 (simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1 : Set (Sym2 (Fin 3))))) h} = 2 := by rw [← Finset.coe_insert, Nat.card_eq_fintype_card]; decide rw [h_card1, h_card2] decide
The edge set s₂ is hop-closed in K₃
Analogously, s₂ ⊆ ⊤.edgeSet holds directly, and the only edge missing from s₂ is e₀₁. Using `Nat.card_eq_fintype_card`, `decide` computes that s₂ has 0 hops while s₂ ∪ {e₀₁} has 2 hops. The strict inequality 0 < 2 establishes that s₂ is hop-closed.
uses
simple_graph_completeGraph_three_hop_closed_not_intersection_closed_edgeSet_top,Finset.coe_insert,Finset.coe_singleton,Set.mem_insert_iff,Set.mem_singleton_iff,simple_graph_completeGraph_three_hop_closed_not_intersection_closed_diff_s2,Nat.card_eq_fintype_cardunfold simple_graph_is_hop_closed refine ⟨?_, ?_⟩ · rw [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_edgeSet_top] intro x hx simp only [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2, Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff, Set.mem_singleton_iff] at hx rcases hx with rfl | rfl <;> simp · intro e he rw [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_diff_s2, Set.mem_singleton_iff] at he subst he have h_card1 : Nat.card {h : Equiv.Perm (Fin 3) // simple_graph_is_hop (SimpleGraph.fromEdgeSet (simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2 : Set (Sym2 (Fin 3)))) h} = 0 := by rw [Nat.card_eq_fintype_card]; decide have h_card2 : Nat.card {h : Equiv.Perm (Fin 3) // simple_graph_is_hop (SimpleGraph.fromEdgeSet (insert simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e01 (simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2 : Set (Sym2 (Fin 3))))) h} = 2 := by rw [← Finset.coe_insert, Nat.card_eq_fintype_card]; decide rw [h_card1, h_card2] decide
The intersection s₁ ∩ s₂ is not hop-closed in K₃
Assume for contradiction that s₁ ∩ s₂ is hop-closed. The edge e₀₁ belongs to ⊤.edgeSet \ (s₁ ∩ s₂) since s₁ ∩ s₂ = {e₁₂}. Specializing the hop-closure condition to e₀₁ implies that the hop count of s₁ ∩ s₂ must be strictly less than that of (s₁ ∩ s₂) ∪ {e₀₁}. However, using `Nat.card_eq_fintype_card`, `decide` evaluates that both graphs have 0 hops, because neither 1 edge nor 2 edges can support a 3-cycle derangement on 3 vertices. This yields 0 < 0, which contradicts `Nat.lt_irrefl 0`.
uses
simple_graph_completeGraph_three_hop_closed_not_intersection_closed_edgeSet_top,Finset.coe_insert,Finset.coe_singleton,Set.mem_inter_iff,Set.mem_insert_iff,Set.mem_singleton_iff,Finset.coe_inter,Nat.card_eq_fintype_card,Nat.lt_irreflintro h unfold simple_graph_is_hop_closed at h rcases h with ⟨-, h2⟩ have he : simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e01 ∈ (⊤ : SimpleGraph (Fin 3)).edgeSet \ ((simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1 : Set (Sym2 (Fin 3))) ∩ simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2) := by rw [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_edgeSet_top] refine ⟨by simp, ?_⟩ simp only [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1, simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2, Finset.coe_insert, Finset.coe_singleton, Set.mem_inter_iff, Set.mem_insert_iff, Set.mem_singleton_iff] rintro ⟨-, h | h⟩ <;> revert h <;> decide specialize h2 simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e01 he have h_card1 : Nat.card {h : Equiv.Perm (Fin 3) // simple_graph_is_hop (SimpleGraph.fromEdgeSet ((simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1 : Set (Sym2 (Fin 3))) ∩ simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2)) h} = 0 := by rw [← Finset.coe_inter, Nat.card_eq_fintype_card]; decide have h_card2 : Nat.card {h : Equiv.Perm (Fin 3) // simple_graph_is_hop (SimpleGraph.fromEdgeSet (insert simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e01 ((simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1 : Set (Sym2 (Fin 3))) ∩ simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2))) h} = 0 := by rw [← Finset.coe_inter, ← Finset.coe_insert, Nat.card_eq_fintype_card]; decide rw [h_card1, h_card2] at h2 exact Nat.lt_irrefl 0 h2
The collection of hop-closed edge subsets of K₃ is not closed under intersection
The existential statement is proved by supplying s₁ and s₂ as witnesses, together with the lemmas establishing that s₁ is hop-closed, s₂ is hop-closed, and their intersection s₁ ∩ s₂ is not hop-closed.
uses
simple_graph_completeGraph_three_hop_closed_not_intersection_closed_hop_closed_s1,simple_graph_completeGraph_three_hop_closed_not_intersection_closed_hop_closed_s2,simple_graph_completeGraph_three_hop_closed_not_intersection_closed_not_hop_closed_interexact ⟨simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1, simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2, simple_graph_completeGraph_three_hop_closed_not_intersection_closed_hop_closed_s1, simple_graph_completeGraph_three_hop_closed_not_intersection_closed_hop_closed_s2, simple_graph_completeGraph_three_hop_closed_not_intersection_closed_not_hop_closed_inter⟩
Sym2.ind- Every unordered pair in Sym²(α) is of the form s(x, y) for some x, y : α.
edgeSet_top- The edge set of the complete graph ⊤ consists of all pairs of distinct vertices (the complement of the diagonal set).
Sym2.mem_diagSet- An unordered pair belongs to the diagonal set if and only if it is diagonal (both endpoints are equal).
Sym2.mk_isDiag_iff- The pair s(x, y) is diagonal if and only if x = y.
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 is in insert a s if and only if it equals a or belongs to s.
Set.mem_singleton_iff- An element is in the singleton {b} if and only if it equals b.
Sym2.eq_swap- The unordered pair s(a, b) equals s(b, a).
simple_graph_completeGraph_three_hop_closed_not_intersection_closed_edgeSet_top- The edge set of the complete graph K₃ on Fin 3 consists of the three edges e₀₁, e₀₂, and e₁₂.
Finset.coe_insert- The coercion to a set of inserting an element into a finite set equals set insertion on the coerced set.
Finset.coe_singleton- The coercion to a set of a singleton finite set {a} is the singleton set {a}.
Set.mem_sdiff- An element is in the set difference s \ t if and only if it is in s and not in t.
Or.inl- Given a proof of A, constructs a proof of A ∨ B.
Or.inr- Given a proof of B, constructs a proof of A ∨ B.
simple_graph_completeGraph_three_hop_closed_not_intersection_closed_diff_s1- The set difference of K₃'s edge set and s₁ = {e₀₁, e₁₂} is the singleton {e₀₂}.
Nat.card_eq_fintype_card- For any finite type, its cardinality as a natural number (Nat.card) equals the cardinality given by its Fintype instance.
simple_graph_completeGraph_three_hop_closed_not_intersection_closed_diff_s2- The set difference of K₃'s edge set and s₂ = {e₁₂, e₀₂} is the singleton {e₀₁}.
Set.mem_inter_iff- An element is in the intersection a ∩ b if and only if it belongs to both a and b.
Finset.coe_inter- The coercion of the intersection of two finite sets equals the intersection of their set coercions.
Nat.lt_irrefl- Strict inequality on natural numbers is irreflexive: no natural number is strictly less than itself (n < n is false).
simple_graph_completeGraph_three_hop_closed_not_intersection_closed_hop_closed_s1- The edge subset s₁ = {e₀₁, e₁₂} is hop-closed in K₃.
simple_graph_completeGraph_three_hop_closed_not_intersection_closed_hop_closed_s2- The edge subset s₂ = {e₁₂, e₀₂} is hop-closed in K₃.
simple_graph_completeGraph_three_hop_closed_not_intersection_closed_not_hop_closed_inter- The intersection s₁ ∩ s₂ = {e₁₂} is not hop-closed in K₃.
- The hop counts (showing that graphs with 1 or 2 edges admit 0 hops while K₃ admits 2 hops) are established by Lean's `decide` tactic via exhaustive computation over all 6 permutations of Fin 3, rather than by a general graph-theoretic argument.
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 SimpleGraphprivate def simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e01 : Sym2 (Fin 3) := s(0, 1)private def simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e02 : Sym2 (Fin 3) := s(0, 2)private def simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e12 : Sym2 (Fin 3) := s(1, 2)private def simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1 : Finset (Sym2 (Fin 3)) := {simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e01, simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e12}private def simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2 : Finset (Sym2 (Fin 3)) := {simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e12, simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e02}private instance (G : SimpleGraph (Fin 3)) [DecidableRel G.Adj] : DecidablePred (simple_graph_is_hop G) := fun h => by unfold simple_graph_is_hop; infer_instanceprivate lemma simple_graph_completeGraph_three_hop_closed_not_intersection_closed_edgeSet_top : (⊤ : SimpleGraph (Fin 3)).edgeSet = {simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e01, simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e02, simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e12} := by ext e induction e using Sym2.ind with | _ a b => simp only [edgeSet_top, Sym2.mem_diagSet, Sym2.mk_isDiag_iff, Set.mem_compl_iff, Set.mem_insert_iff, Set.mem_singleton_iff, simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e01, simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e02, simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e12] fin_cases a <;> fin_cases b <;> simp [Sym2.eq_swap]private lemma simple_graph_completeGraph_three_hop_closed_not_intersection_closed_diff_s1 : (⊤ : SimpleGraph (Fin 3)).edgeSet \ (simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1 : Set (Sym2 (Fin 3))) = {simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e02} := by rw [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_edgeSet_top] ext e simp only [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1, Finset.coe_insert, Finset.coe_singleton, Set.mem_sdiff, Set.mem_insert_iff, Set.mem_singleton_iff] constructor · rintro ⟨h1 | h1 | h1, h2⟩ · exfalso; exact h2 (Or.inl h1) · exact h1 · exfalso; exact h2 (Or.inr h1) · rintro rfl refine ⟨Or.inr (Or.inl rfl), ?_⟩ intro h rcases h with h | h <;> revert h <;> decideprivate lemma simple_graph_completeGraph_three_hop_closed_not_intersection_closed_diff_s2 : (⊤ : SimpleGraph (Fin 3)).edgeSet \ (simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2 : Set (Sym2 (Fin 3))) = {simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e01} := by rw [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_edgeSet_top] ext e simp only [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2, Finset.coe_insert, Finset.coe_singleton, Set.mem_sdiff, Set.mem_insert_iff, Set.mem_singleton_iff] constructor · rintro ⟨h1 | h1 | h1, h2⟩ · exact h1 · exfalso; exact h2 (Or.inr h1) · exfalso; exact h2 (Or.inl h1) · rintro rfl refine ⟨Or.inl rfl, ?_⟩ intro h rcases h with h | h <;> revert h <;> decideprivate lemma simple_graph_completeGraph_three_hop_closed_not_intersection_closed_hop_closed_s1 : simple_graph_is_hop_closed (⊤ : SimpleGraph (Fin 3)) (simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1 : Set (Sym2 (Fin 3))) := by unfold simple_graph_is_hop_closed refine ⟨?_, ?_⟩ · rw [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_edgeSet_top] intro x hx simp only [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1, Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff, Set.mem_singleton_iff] at hx rcases hx with rfl | rfl <;> simp · intro e he rw [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_diff_s1, Set.mem_singleton_iff] at he subst he have h_card1 : Nat.card {h : Equiv.Perm (Fin 3) // simple_graph_is_hop (SimpleGraph.fromEdgeSet (simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1 : Set (Sym2 (Fin 3)))) h} = 0 := by rw [Nat.card_eq_fintype_card]; decide have h_card2 : Nat.card {h : Equiv.Perm (Fin 3) // simple_graph_is_hop (SimpleGraph.fromEdgeSet (insert simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e02 (simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1 : Set (Sym2 (Fin 3))))) h} = 2 := by rw [← Finset.coe_insert, Nat.card_eq_fintype_card]; decide rw [h_card1, h_card2] decideprivate lemma simple_graph_completeGraph_three_hop_closed_not_intersection_closed_hop_closed_s2 : simple_graph_is_hop_closed (⊤ : SimpleGraph (Fin 3)) (simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2 : Set (Sym2 (Fin 3))) := by unfold simple_graph_is_hop_closed refine ⟨?_, ?_⟩ · rw [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_edgeSet_top] intro x hx simp only [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2, Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff, Set.mem_singleton_iff] at hx rcases hx with rfl | rfl <;> simp · intro e he rw [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_diff_s2, Set.mem_singleton_iff] at he subst he have h_card1 : Nat.card {h : Equiv.Perm (Fin 3) // simple_graph_is_hop (SimpleGraph.fromEdgeSet (simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2 : Set (Sym2 (Fin 3)))) h} = 0 := by rw [Nat.card_eq_fintype_card]; decide have h_card2 : Nat.card {h : Equiv.Perm (Fin 3) // simple_graph_is_hop (SimpleGraph.fromEdgeSet (insert simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e01 (simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2 : Set (Sym2 (Fin 3))))) h} = 2 := by rw [← Finset.coe_insert, Nat.card_eq_fintype_card]; decide rw [h_card1, h_card2] decideprivate lemma simple_graph_completeGraph_three_hop_closed_not_intersection_closed_not_hop_closed_inter : ¬ simple_graph_is_hop_closed (⊤ : SimpleGraph (Fin 3)) ((simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1 : Set (Sym2 (Fin 3))) ∩ simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2) := by intro h unfold simple_graph_is_hop_closed at h rcases h with ⟨-, h2⟩ have he : simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e01 ∈ (⊤ : SimpleGraph (Fin 3)).edgeSet \ ((simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1 : Set (Sym2 (Fin 3))) ∩ simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2) := by rw [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_edgeSet_top] refine ⟨by simp, ?_⟩ simp only [simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1, simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2, Finset.coe_insert, Finset.coe_singleton, Set.mem_inter_iff, Set.mem_insert_iff, Set.mem_singleton_iff] rintro ⟨-, h | h⟩ <;> revert h <;> decide specialize h2 simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e01 he have h_card1 : Nat.card {h : Equiv.Perm (Fin 3) // simple_graph_is_hop (SimpleGraph.fromEdgeSet ((simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1 : Set (Sym2 (Fin 3))) ∩ simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2)) h} = 0 := by rw [← Finset.coe_inter, Nat.card_eq_fintype_card]; decide have h_card2 : Nat.card {h : Equiv.Perm (Fin 3) // simple_graph_is_hop (SimpleGraph.fromEdgeSet (insert simple_graph_completeGraph_three_hop_closed_not_intersection_closed_e01 ((simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1 : Set (Sym2 (Fin 3))) ∩ simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2))) h} = 0 := by rw [← Finset.coe_inter, ← Finset.coe_insert, Nat.card_eq_fintype_card]; decide rw [h_card1, h_card2] at h2 exact Nat.lt_irrefl 0 h2/-- Hop-closed edge subsets of K₃ are not closed under intersection. -/theorem simple_graph_completeGraph_three_hop_closed_not_intersection_closed : ∃ F₁ F₂ : Set (Sym2 (Fin 3)), simple_graph_is_hop_closed (⊤ : SimpleGraph (Fin 3)) F₁ ∧ simple_graph_is_hop_closed (⊤ : SimpleGraph (Fin 3)) F₂ ∧ ¬ simple_graph_is_hop_closed (⊤ : SimpleGraph (Fin 3)) (F₁ ∩ F₂) := by exact ⟨simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s1, simple_graph_completeGraph_three_hop_closed_not_intersection_closed_s2, simple_graph_completeGraph_three_hop_closed_not_intersection_closed_hop_closed_s1, simple_graph_completeGraph_three_hop_closed_not_intersection_closed_hop_closed_s2, simple_graph_completeGraph_three_hop_closed_not_intersection_closed_not_hop_closed_inter⟩