AFTD Auto-Formalizing Theoretical Domains

simple_graph_stable_lex_private_triangle_direct_exchange_counterexample

theoremverified

There is a stable graph with a unique minimum triangle edge cover and a maximum packing such that the cover has exactly one edge outside the packing, but every private triangle of that edge intersects at least two packed triangles. Thus no such private triangle can be inserted by replacing only one packed triangle.

Statement

theorem simple_graph_stable_lex_private_triangle_direct_exchange_counterexample :
    ∃ (G : SimpleGraph (Fin 8)) (P : Finset (Finset (Fin 8)))
      (C : Finset (Sym2 (Fin 8))) (e : Sym2 (Fin 8)),
      simple_graph_triangle_packing_number G = 4 ∧
      simple_graph_triangle_cover_number G = 5 ∧
      (∀ g ∈ G.edgeSet,
        simple_graph_triangle_packing_number (G.deleteEdges {g}) =
          simple_graph_triangle_packing_number G) ∧
      (∀ t ∈ P, G.IsNClique 3 t) ∧
      (P : Set (Finset (Fin 8))).Pairwise (fun a b => (a ∩ b).card ≤ 1) ∧
      P.card = simple_graph_triangle_packing_number G ∧
      (∀ g ∈ C, g ∈ G.edgeSet) ∧
      (∀ t : Finset (Fin 8), G.IsNClique 3 t → ∃ g ∈ C, ∀ x ∈ g, x ∈ t) ∧
      C.card = simple_graph_triangle_cover_number G ∧
      (∀ D : Finset (Sym2 (Fin 8)),
        (∀ g ∈ D, g ∈ G.edgeSet) →
        (∀ t : Finset (Fin 8), G.IsNClique 3 t → ∃ g ∈ D, ∀ x ∈ g, x ∈ t) →
        D.card = simple_graph_triangle_cover_number G → D = C) ∧
      C \ (P.image finite_vertex_set_edge_encoding).biUnion id = {e} ∧
      (∀ t : Finset (Fin 8), G.IsNClique 3 t →
        (∀ x ∈ e, x ∈ t) →
        (∀ g ∈ C, (∀ x ∈ g, x ∈ t) → g = e) →
        2 ≤ (P.filter fun s => 2 ≤ (s ∩ t).card).card)
Source
Exact computations 16067–16069; triangle packing and cover definitions from arXiv:2610.15539, Section 1.
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

The theorem is proved by constructing an explicit 8-vertex graph sx_G with 18 edges and 16 triangles. Using branch-and-bound search and hitting set enumeration, its packing number is verified to be 4 and its covering number is 5 with unique minimum cover sx_C. For every edge, an explicit packing of 4 triangles disjoint from that edge witnesses stability, while sx_C contains a unique edge outside the packing sx_P whose private triangles all share edges with at least two packed triangles.

  1. sgx_maxC bounds the size of any pairwise compatible subset in the base case n = 0.

    When the recursion depth bound is 0, the list must be empty, forcing the subset S to be empty, so its cardinality is 0.

    lines 12–19

      intro n
      induction n with
      | zero =>
        intro l hl S hS _
        have hl0 : l = [] := List.length_eq_zero_iff.mp (by omega)
        subst hl0
        have : S = ∅ := Finset.eq_empty_of_forall_notMem (fun a ha => by simpa using hS a ha)
        simp [this, sgx_maxC]
  2. sgx_maxC bounds the size of any pairwise compatible subset in the inductive step.

    We branch on whether the head element t is in S. If t is in S, the remaining elements of S belong to the filtered sublist of compatible elements, and by the induction hypothesis their count is bounded. If t is not in S, all of S lies in the tail. Both cases are bounded by the maximum in the recursive definition.

    lines 20–54

      | succ n ih =>
        intro l hl S hS hc
        match l, hl, hS with
        | [], _, hS =>
          have : S = ∅ := Finset.eq_empty_of_forall_notMem (fun a ha => by simpa using hS a ha)
          simp [this, sgx_maxC]
        | t :: l, hl, hS =>
          rw [sgx_maxC]
          by_cases ht : t ∈ S
          · refine le_trans ?_ (le_max_right _ _)
            have hsub : ∀ a ∈ S.erase t, a ∈ l.filter (c t) := by
              intro a ha
              have hne : a ≠ t := (Finset.mem_erase.mp ha).1
              have haS : a ∈ S := (Finset.mem_erase.mp ha).2
              have ha' : a ∈ t :: l := hS a haS
              have hal : a ∈ l := by
                rcases List.mem_cons.mp ha' with h | h
                · exact absurd h hne
                · exact h
              exact List.mem_filter.mpr ⟨hal, hc t ht a haS (Ne.symm hne)⟩
            have hlen : (l.filter (c t)).length ≤ n := by
              have := List.length_filter_le (c t) l
              simp only [List.length_cons] at hl
              omega
            have := ih (l.filter (c t)) hlen (S.erase t) hsub
              (fun a ha b hb hab => hc a (Finset.mem_erase.mp ha).2 b (Finset.mem_erase.mp hb).2 hab)
            have hcard := Finset.card_erase_add_one ht
            omega
          · refine le_trans ?_ (le_max_left _ _)
            have hlen : l.length ≤ n := by simpa using hl
            refine ih l hlen S ?_ hc
            intro a ha
            rcases List.mem_cons.mp (hS a ha) with h | h
            · exact absurd (h ▸ ha) ht
            · exact h
  3. sgx_enum is complete for k = 0.

    When k = 0, an empty list of hyperedges has the empty hitting set. If the list is nonempty, any hitting set must be nonempty, contradicting cardinality at most 0.

    lines 64–73

      intro k
      induction k with
      | zero =>
        intro F D hD hc
        match F, hD with
        | [], _ => exact ⟨[], by simp [sgx_enum], by simp⟩
        | l :: F, hD =>
          obtain ⟨e, he, _⟩ := hD l (by simp)
          have : D = ∅ := Finset.card_eq_zero.mp (by omega)
          simp [this] at he
  4. sgx_enum is complete for k + 1.

    Any hitting set D must contain some element e from the first hyperedge l. Then D without e is a hitting set of size at most k for the remaining unhit hyperedges, so by induction a subset is enumerated, and prepending e gives a valid hitting set in sgx_enum.

    lines 74–99

      | succ k ih =>
        intro F D hD hc
        match F, hD with
        | [], _ => exact ⟨[], by simp [sgx_enum], by simp⟩
        | l :: F, hD =>
          obtain ⟨e, he, hel⟩ := hD l (by simp)
          have hD' : ∀ l' ∈ F.filter (fun l' => decide (e ∉ l')), ∃ e' ∈ D.erase e, e' ∈ l' := by
            intro l' hl'
            have hmem := List.mem_filter.mp hl'
            obtain ⟨e', he', hel'⟩ := hD l' (List.mem_cons_of_mem _ hmem.1)
            refine ⟨e', Finset.mem_erase.mpr ⟨?_, he'⟩, hel'⟩
            rintro rfl
            have : e' ∉ l' := by simpa using hmem.2
            exact this hel'
          have hcard : (D.erase e).card ≤ k := by
            have := Finset.card_erase_add_one he
            omega
          obtain ⟨s, hs, hsD⟩ := ih _ _ hD' hcard
          refine ⟨e :: s, ?_, ?_⟩
          · simp only [sgx_enum, List.mem_flatMap, List.mem_map]
            exact ⟨e, hel, s, hs, rfl⟩
          · intro x hx
            simp only [List.toFinset_cons, Finset.mem_insert] at hx
            rcases hx with rfl | hx
            · exact he
            · exact (Finset.mem_erase.mp (hsD hx)).2
  5. The triangles of sx_G are precisely the 16 elements of sx_T. automation

    Decided by kernel computation by checking all 3-vertex subsets.

    lines 121–124

    set_option maxRecDepth 100000 in
    theorem sx_T_clique : ∀ t ∈ sx_T, sx_G.IsNClique 3 t := by decide +kernel
    
  6. Every edge in sx_G is in the edge list sx_EL.

    Unfolding the definition of sx_G edges shows they belong to sx_EL.

    lines 128–133

    lemma sx_edge_mem {g : Sym2 (Fin 8)} (h : g ∈ sx_G.edgeSet) : g ∈ sx_EL := by
      induction g using Sym2.ind with
      | _ a b =>
        have h1 := ((SimpleGraph.mem_edgeSet sx_G).mp h).1
        exact List.mem_toFinset.mp h1
    
  7. The maximum triangle packing number of sx_G is 4. automation

    Branch-and-bound evaluation computes an upper bound of 4 on the size of any triangle packing, while the explicit 4-triangle packing sx_P matches this bound.

    lines 138–160

    lemma sx_nu_le (T : Finset (Finset (Fin 8))) (hT : ∀ t ∈ T, sx_G.IsNClique 3 t)
        (hP : (T : Set (Finset (Fin 8))).Pairwise (fun a b => (a ∩ b).card ≤ 1)) : T.card ≤ 4 :=
      calc T.card ≤ sgx_maxC sx_compat sx_T.length sx_T :=
            sgx_maxC_bound sx_compat _ sx_T le_rfl T (fun a ha => sx_clique_mem (hT a ha))
              (fun a ha b hb hab => decide_eq_true (hP (Finset.mem_coe.mpr ha) (Finset.mem_coe.mpr hb) hab))
        _ = 4 := sx_maxC_eq
    
    theorem sx_P_clique : ∀ t ∈ sx_P, sx_G.IsNClique 3 t := by decide +kernel
    
    theorem sx_P_pw' : ∀ a ∈ sx_P, ∀ b ∈ sx_P, a ≠ b → (a ∩ b).card ≤ 1 := by decide +kernel
    
    lemma sx_P_pw : (sx_P : Set (Finset (Fin 8))).Pairwise (fun a b => (a ∩ b).card ≤ 1) :=
      fun a ha b hb hab => sx_P_pw' a (Finset.mem_coe.mp ha) b (Finset.mem_coe.mp hb) hab
    
    theorem sx_P_card : sx_P.card = 4 := by decide +kernel
    
    theorem sx_pack_eq : simple_graph_triangle_packing_number sx_G = 4 := by
      unfold simple_graph_triangle_packing_number
      refine IsGreatest.csSup_eq ⟨⟨sx_P, sx_P_clique, sx_P_pw, sx_P_card⟩, ?_⟩
      rintro n ⟨T, h1, h2, rfl⟩
      exact sx_nu_le T h1 h2
    
  8. Witness packings avoid deleted edges and remain valid cliques.

    Kernel computation checks that sx_W provides valid 4-triangle packings avoiding each edge, and sx_del_clique verifies that triangles avoiding an edge remain cliques in the graph with that edge deleted.

    lines 162–182

    theorem sx_W_cover : ∀ g ∈ sx_EL, ∃ q ∈ sx_W, q.1 = g := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem sx_W_ok : ∀ q ∈ sx_W, q.2.toFinset.card = 4 ∧
        (∀ t ∈ q.2, t ∈ sx_T ∧ ¬ ∀ x ∈ q.1, x ∈ t) ∧
        (∀ a ∈ q.2, ∀ b ∈ q.2, a ≠ b → (a ∩ b).card ≤ 1) := by decide +kernel
    
    lemma sx_del_clique {t : Finset (Fin 8)} {g : Sym2 (Fin 8)} (h : sx_G.IsNClique 3 t)
        (hg : ¬ ∀ x ∈ g, x ∈ t) : (sx_G.deleteEdges {g}).IsNClique 3 t := by
      refine ⟨?_, h.card_eq⟩
      intro a ha b hb hab
      refine (SimpleGraph.deleteEdges_adj).mpr ⟨h.isClique ha hb hab, ?_⟩
      intro hmem
      have hgeq : s(a,b) = g := Set.mem_singleton_iff.mp hmem
      apply hg
      rw [← hgeq]
      intro x hx
      rcases Sym2.mem_iff.mp hx with rfl | rfl
      · exact ha
      · exact hb
    
  9. sx_G is stable: deleting any edge leaves the triangle packing number equal to 4.

    For any edge g, the witness packing in sx_W avoids g and provides 4 edge-disjoint triangles in sx_G - g, while deleting edges cannot increase the packing number.

    lines 183–198

    theorem sx_stable : ∀ g ∈ sx_G.edgeSet,
        simple_graph_triangle_packing_number (sx_G.deleteEdges {g}) = simple_graph_triangle_packing_number sx_G := by
      intro g hg
      rw [sx_pack_eq]
      obtain ⟨q, hq, rfl⟩ := sx_W_cover g (sx_edge_mem hg)
      obtain ⟨h1, h2, h3⟩ := sx_W_ok q hq
      unfold simple_graph_triangle_packing_number
      refine IsGreatest.csSup_eq ⟨⟨q.2.toFinset, ?_, ?_, h1⟩, ?_⟩
      · intro t ht
        have ht' := List.mem_toFinset.mp ht
        exact sx_del_clique (sx_T_clique t (h2 t ht').1) (h2 t ht').2
      · intro a ha b hb hab
        exact h3 a (List.mem_toFinset.mp (Finset.mem_coe.mp ha)) b (List.mem_toFinset.mp (Finset.mem_coe.mp hb)) hab
      · rintro n ⟨T, hT, hP, rfl⟩
        exact sx_nu_le T (fun t ht => (hT t ht).mono (SimpleGraph.deleteEdges_le _)) hP
    
  10. Properties of the candidate cover sx_C and hypergraph hitting sets.

    Kernel computation checks that no hitting set of size at most 4 exists, every hitting set of size 5 is sx_C, sx_C has 5 valid edges, and covers all triangles in sx_T. Also, any edge cover of sx_G hits every list in sx_F.

    lines 203–226

    uses sx_hit

    theorem sx_enum_small : sgx_enum (5 - 1) sx_F = [] := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem sx_enum_exact : ∀ s ∈ sgx_enum 5 sx_F, s.toFinset = sx_C := by decide +kernel
    
    theorem sx_C_mem : ∀ g ∈ sx_C, g ∈ sx_E ∧ ¬ g.IsDiag := by decide +kernel
    
    lemma sx_C_edge : ∀ g ∈ sx_C, g ∈ sx_G.edgeSet := by
      intro g hg
      obtain ⟨h1, h2⟩ := sx_C_mem g hg
      induction g using Sym2.ind with
      | _ a b => exact (SimpleGraph.mem_edgeSet sx_G).mpr ⟨h1, fun h => h2 (Sym2.mk_isDiag_iff.mpr h)⟩
    
    theorem sx_C_cover : ∀ t ∈ sx_T, ∃ g ∈ sx_C, ∀ x ∈ g, x ∈ t := by decide +kernel
    theorem sx_C_card : sx_C.card = 5 := by decide +kernel
    
    lemma sx_hit (D : Finset (Sym2 (Fin 8))) (hE : ∀ g ∈ D, g ∈ sx_G.edgeSet)
        (hC : ∀ t : Finset (Fin 8), sx_G.IsNClique 3 t → ∃ g ∈ D, ∀ x ∈ g, x ∈ t) :
        ∀ l ∈ sx_F, ∃ e ∈ D, e ∈ l := by
      intro l hl
      obtain ⟨t, ht, rfl⟩ := List.mem_map.mp hl
      obtain ⟨g, hg, hgt⟩ := hC t (sx_T_clique t ht)
      exact ⟨g, hg, List.mem_filter.mpr ⟨sx_edge_mem (hE g hg), decide_eq_true hgt⟩⟩
    
  11. The minimum triangle cover number of sx_G is 5, and sx_C is the unique minimum cover.

    Since sx_C is a cover of size 5 and no cover of size at most 4 exists, tau is 5. Any cover of size 5 must contain a hitting set found by sgx_enum 5, which must be sx_C, so by cardinality it equals sx_C.

    lines 227–244

    theorem sx_tau_eq : simple_graph_triangle_cover_number sx_G = 5 := by
      unfold simple_graph_triangle_cover_number
      refine IsLeast.csInf_eq ⟨⟨sx_C, sx_C_edge, ?_, sx_C_card⟩, ?_⟩
      · intro t ht
        exact sx_C_cover t (sx_clique_mem ht)
      · rintro n ⟨D, hE, hC, rfl⟩
        by_contra hlt
        obtain ⟨s, hs, _⟩ := sgx_enum_complete (5 - 1) sx_F D (sx_hit D hE hC) (by omega)
        rw [sx_enum_small] at hs
        simp at hs
    
    lemma sx_unique (D : Finset (Sym2 (Fin 8))) (hE : ∀ g ∈ D, g ∈ sx_G.edgeSet)
        (hC : ∀ t : Finset (Fin 8), sx_G.IsNClique 3 t → ∃ g ∈ D, ∀ x ∈ g, x ∈ t)
        (hcard : D.card = 5) : D = sx_C := by
      obtain ⟨s, hs, hsub⟩ := sgx_enum_complete 5 sx_F D (sx_hit D hE hC) (by omega)
      rw [sx_enum_exact s hs] at hsub
      exact (Finset.eq_of_subset_of_card_le hsub (by rw [hcard, sx_C_card])).symm
    
  12. Private triangle and direct exchange counterexample properties. automation

    Kernel computation verifies that sx_C has exactly one edge, s(1,4), outside the packing sx_P, and every private triangle of s(1,4) intersects at least two triangles of sx_P.

    lines 246–251

    theorem sx_outside : sx_C \ (sx_P.image finite_vertex_set_edge_encoding).biUnion id = {s(1,4)} := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem sx_last : ∀ t ∈ sx_T, (∀ x ∈ (s(1,4) : Sym2 (Fin 8)), x ∈ t) →
        (∀ g ∈ sx_C, (∀ x ∈ g, x ∈ t) → g = s(1,4)) →
        2 ≤ (sx_P.filter fun s => 2 ≤ (s ∩ t).card).card := by decide +kernel
  13. There exists a stable graph satisfying all counterexample conditions.

    We provide sx_G, sx_P, sx_C, and edge s(1,4), discharging all 12 properties using the established lemmas.

    lines 276–284

      refine ⟨sx_G, sx_P, sx_C, s(1,4), sx_pack_eq, sx_tau_eq, sx_stable, sx_P_clique, sx_P_pw, ?_,
        sx_C_edge, fun t ht => sx_C_cover t (sx_clique_mem ht), ?_, ?_, sx_outside, ?_⟩
      · rw [sx_P_card, sx_pack_eq]
      · rw [sx_C_card, sx_tau_eq]
      · intro D hE hC hcard
        rw [sx_tau_eq] at hcard
        exact sx_unique D hE hC hcard
      · intro t ht
        exact sx_last t (sx_clique_mem ht)
sx_hit
An edge cover of all triangles in sx_G hits every triangle edge list in sx_F.

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

open scoped Sym2def sgx_maxC {α : Type} (c : α → α → Bool) : ℕ → List α → ℕ  | 0, _ => 0  | _ + 1, [] => 0  | n + 1, t :: l => max (sgx_maxC c n l) (1 + sgx_maxC c n (l.filter (c t)))theorem sgx_maxC_bound {α : Type} [DecidableEq α] (c : α → α → Bool) :    ∀ (n : ℕ) (l : List α), l.length ≤ n → ∀ S : Finset α, (∀ a ∈ S, a ∈ l) →      (∀ a ∈ S, ∀ b ∈ S, a ≠ b → c a b = true) → S.card ≤ sgx_maxC c n l := by  intro n  induction n with  | zero =>    intro l hl S hS _    have hl0 : l = [] := List.length_eq_zero_iff.mp (by omega)    subst hl0    have : S = ∅ := Finset.eq_empty_of_forall_notMem (fun a ha => by simpa using hS a ha)    simp [this, sgx_maxC]  | succ n ih =>    intro l hl S hS hc    match l, hl, hS with    | [], _, hS =>      have : S = ∅ := Finset.eq_empty_of_forall_notMem (fun a ha => by simpa using hS a ha)      simp [this, sgx_maxC]    | t :: l, hl, hS =>      rw [sgx_maxC]      by_cases ht : t ∈ S      · refine le_trans ?_ (le_max_right _ _)        have hsub : ∀ a ∈ S.erase t, a ∈ l.filter (c t) := by          intro a ha          have hne : a ≠ t := (Finset.mem_erase.mp ha).1          have haS : a ∈ S := (Finset.mem_erase.mp ha).2          have ha' : a ∈ t :: l := hS a haS          have hal : a ∈ l := by            rcases List.mem_cons.mp ha' with h | h            · exact absurd h hne            · exact h          exact List.mem_filter.mpr ⟨hal, hc t ht a haS (Ne.symm hne)⟩        have hlen : (l.filter (c t)).length ≤ n := by          have := List.length_filter_le (c t) l          simp only [List.length_cons] at hl          omega        have := ih (l.filter (c t)) hlen (S.erase t) hsub          (fun a ha b hb hab => hc a (Finset.mem_erase.mp ha).2 b (Finset.mem_erase.mp hb).2 hab)        have hcard := Finset.card_erase_add_one ht        omega      · refine le_trans ?_ (le_max_left _ _)        have hlen : l.length ≤ n := by simpa using hl        refine ih l hlen S ?_ hc        intro a ha        rcases List.mem_cons.mp (hS a ha) with h | h        · exact absurd (h ▸ ha) ht        · exact hdef sgx_enum {E : Type} [DecidableEq E] : ℕ → List (List E) → List (List E)  | _, [] => [[]]  | 0, _ :: _ => []  | k + 1, l :: F => l.flatMap fun e => (sgx_enum k (F.filter fun l' => decide (e ∉ l'))).map (e :: ·)theorem sgx_enum_complete {E : Type} [DecidableEq E] :    ∀ (k : ℕ) (F : List (List E)) (D : Finset E), (∀ l ∈ F, ∃ e ∈ D, e ∈ l) → D.card ≤ k →      ∃ s ∈ sgx_enum k F, s.toFinset ⊆ D := by  intro k  induction k with  | zero =>    intro F D hD hc    match F, hD with    | [], _ => exact ⟨[], by simp [sgx_enum], by simp⟩    | l :: F, hD =>      obtain ⟨e, he, _⟩ := hD l (by simp)      have : D = ∅ := Finset.card_eq_zero.mp (by omega)      simp [this] at he  | succ k ih =>    intro F D hD hc    match F, hD with    | [], _ => exact ⟨[], by simp [sgx_enum], by simp⟩    | l :: F, hD =>      obtain ⟨e, he, hel⟩ := hD l (by simp)      have hD' : ∀ l' ∈ F.filter (fun l' => decide (e ∉ l')), ∃ e' ∈ D.erase e, e' ∈ l' := by        intro l' hl'        have hmem := List.mem_filter.mp hl'        obtain ⟨e', he', hel'⟩ := hD l' (List.mem_cons_of_mem _ hmem.1)        refine ⟨e', Finset.mem_erase.mpr ⟨?_, he'⟩, hel'⟩        rintro rfl        have : e' ∉ l' := by simpa using hmem.2        exact this hel'      have hcard : (D.erase e).card ≤ k := by        have := Finset.card_erase_add_one he        omega      obtain ⟨s, hs, hsD⟩ := ih _ _ hD' hcard      refine ⟨e :: s, ?_, ?_⟩      · simp only [sgx_enum, List.mem_flatMap, List.mem_map]        exact ⟨e, hel, s, hs, rfl⟩      · intro x hx        simp only [List.toFinset_cons, Finset.mem_insert] at hx        rcases hx with rfl | hx        · exact he        · exact (Finset.mem_erase.mp (hsD hx)).2def sx_EL : List (Sym2 (Fin 8)) :=  [s(0,4), s(0,5), s(0,7), s(1,4), s(1,6), s(1,7), s(2,5), s(2,6), s(2,7), s(3,5), s(3,6), s(3,7), s(4,5), s(4,6), s(4,7), s(5,6), s(5,7), s(6,7)]def sx_T : List (Finset (Fin 8)) := [{0,4,5}, {0,4,7}, {0,5,7}, {1,4,6}, {1,4,7}, {1,6,7}, {2,5,6}, {2,5,7}, {2,6,7}, {3,5,6}, {3,5,7}, {3,6,7}, {4,5,6}, {4,5,7}, {4,6,7}, {5,6,7}]def sx_W : List (Sym2 (Fin 8) × List (Finset (Fin 8))) := [(s(0,4), [{0,5,7}, {1,4,6}, {2,5,6}, {3,6,7}]), (s(0,5), [{0,4,7}, {1,4,6}, {2,5,6}, {3,5,7}]), (s(0,7), [{0,4,5}, {1,4,6}, {2,5,6}, {3,5,7}]), (s(1,4), [{0,4,5}, {1,6,7}, {2,5,6}, {3,5,7}]), (s(1,6), [{0,4,5}, {1,4,7}, {2,5,6}, {3,5,7}]), (s(1,7), [{0,4,5}, {1,4,6}, {2,5,6}, {3,5,7}]), (s(2,5), [{0,4,5}, {1,4,6}, {2,6,7}, {3,5,6}]), (s(2,6), [{0,4,5}, {1,4,6}, {2,5,7}, {3,5,6}]), (s(2,7), [{0,4,5}, {1,4,6}, {2,5,6}, {3,5,7}]), (s(3,5), [{0,4,5}, {1,4,6}, {2,5,6}, {3,6,7}]), (s(3,6), [{0,4,5}, {1,4,6}, {2,5,6}, {3,5,7}]), (s(3,7), [{0,4,5}, {1,4,6}, {2,5,7}, {3,5,6}]), (s(4,5), [{0,4,7}, {1,4,6}, {2,5,6}, {3,5,7}]), (s(4,6), [{0,4,5}, {1,4,7}, {2,5,6}, {3,5,7}]), (s(4,7), [{0,4,5}, {1,4,6}, {2,5,6}, {3,5,7}]), (s(5,6), [{0,4,5}, {1,4,6}, {2,5,7}, {3,6,7}]), (s(5,7), [{0,4,5}, {1,4,6}, {2,5,6}, {3,6,7}]), (s(6,7), [{0,4,5}, {1,4,6}, {2,5,6}, {3,5,7}])]def sx_P : Finset (Finset (Fin 8)) := {{0,4,7},{4,5,6},{1,6,7},{3,5,7}}def sx_C : Finset (Sym2 (Fin 8)) := {s(0,4), s(1,4), s(5,6), s(5,7), s(6,7)}def sx_E : Finset (Sym2 (Fin 8)) := sx_EL.toFinsetdef sx_G : SimpleGraph (Fin 8) where  Adj u v := s(u,v) ∈ sx_E ∧ u ≠ v  symm := Std.Symm.mk (fun u v h => ⟨by rw [Sym2.eq_swap]; exact h.1, h.2.symm⟩)  loopless := Std.Irrefl.mk (fun u h => h.2 rfl)instance sx_dec : DecidableRel sx_G.Adj :=  fun u v => decidable_of_decidable_of_iff (p := s(u,v) ∈ sx_E ∧ u ≠ v) (q := sx_G.Adj u v) Iff.rflset_option maxRecDepth 100000 intheorem sx_tri_complete : ∀ t ∈ (Finset.univ : Finset (Fin 8)).powersetCard 3,    sx_G.IsNClique 3 t → t ∈ sx_T := by decide +kernelset_option maxRecDepth 100000 intheorem sx_T_clique : ∀ t ∈ sx_T, sx_G.IsNClique 3 t := by decide +kernellemma sx_clique_mem {t : Finset (Fin 8)} (h : sx_G.IsNClique 3 t) : t ∈ sx_T :=  sx_tri_complete t (Finset.mem_powersetCard.mpr ⟨Finset.subset_univ _, h.card_eq⟩) hlemma sx_edge_mem {g : Sym2 (Fin 8)} (h : g ∈ sx_G.edgeSet) : g ∈ sx_EL := by  induction g using Sym2.ind with  | _ a b =>    have h1 := ((SimpleGraph.mem_edgeSet sx_G).mp h).1    exact List.mem_toFinset.mp h1def sx_compat (s t : Finset (Fin 8)) : Bool := decide ((s ∩ t).card ≤ 1)set_option maxRecDepth 100000 intheorem sx_maxC_eq : sgx_maxC sx_compat sx_T.length sx_T = 4 := by decide +kernellemma sx_nu_le (T : Finset (Finset (Fin 8))) (hT : ∀ t ∈ T, sx_G.IsNClique 3 t)    (hP : (T : Set (Finset (Fin 8))).Pairwise (fun a b => (a ∩ b).card ≤ 1)) : T.card ≤ 4 :=  calc T.card ≤ sgx_maxC sx_compat sx_T.length sx_T :=        sgx_maxC_bound sx_compat _ sx_T le_rfl T (fun a ha => sx_clique_mem (hT a ha))          (fun a ha b hb hab => decide_eq_true (hP (Finset.mem_coe.mpr ha) (Finset.mem_coe.mpr hb) hab))    _ = 4 := sx_maxC_eqtheorem sx_P_clique : ∀ t ∈ sx_P, sx_G.IsNClique 3 t := by decide +kerneltheorem sx_P_pw' : ∀ a ∈ sx_P, ∀ b ∈ sx_P, a ≠ b → (a ∩ b).card ≤ 1 := by decide +kernellemma sx_P_pw : (sx_P : Set (Finset (Fin 8))).Pairwise (fun a b => (a ∩ b).card ≤ 1) :=  fun a ha b hb hab => sx_P_pw' a (Finset.mem_coe.mp ha) b (Finset.mem_coe.mp hb) habtheorem sx_P_card : sx_P.card = 4 := by decide +kerneltheorem sx_pack_eq : simple_graph_triangle_packing_number sx_G = 4 := by  unfold simple_graph_triangle_packing_number  refine IsGreatest.csSup_eq ⟨⟨sx_P, sx_P_clique, sx_P_pw, sx_P_card⟩, ?_⟩  rintro n ⟨T, h1, h2, rfl⟩  exact sx_nu_le T h1 h2set_option maxRecDepth 100000 intheorem sx_W_cover : ∀ g ∈ sx_EL, ∃ q ∈ sx_W, q.1 = g := by decide +kernelset_option maxRecDepth 100000 intheorem sx_W_ok : ∀ q ∈ sx_W, q.2.toFinset.card = 4 ∧    (∀ t ∈ q.2, t ∈ sx_T ∧ ¬ ∀ x ∈ q.1, x ∈ t) ∧    (∀ a ∈ q.2, ∀ b ∈ q.2, a ≠ b → (a ∩ b).card ≤ 1) := by decide +kernellemma sx_del_clique {t : Finset (Fin 8)} {g : Sym2 (Fin 8)} (h : sx_G.IsNClique 3 t)    (hg : ¬ ∀ x ∈ g, x ∈ t) : (sx_G.deleteEdges {g}).IsNClique 3 t := by  refine ⟨?_, h.card_eq⟩  intro a ha b hb hab  refine (SimpleGraph.deleteEdges_adj).mpr ⟨h.isClique ha hb hab, ?_⟩  intro hmem  have hgeq : s(a,b) = g := Set.mem_singleton_iff.mp hmem  apply hg  rw [← hgeq]  intro x hx  rcases Sym2.mem_iff.mp hx with rfl | rfl  · exact ha  · exact hbtheorem sx_stable : ∀ g ∈ sx_G.edgeSet,    simple_graph_triangle_packing_number (sx_G.deleteEdges {g}) = simple_graph_triangle_packing_number sx_G := by  intro g hg  rw [sx_pack_eq]  obtain ⟨q, hq, rfl⟩ := sx_W_cover g (sx_edge_mem hg)  obtain ⟨h1, h2, h3⟩ := sx_W_ok q hq  unfold simple_graph_triangle_packing_number  refine IsGreatest.csSup_eq ⟨⟨q.2.toFinset, ?_, ?_, h1⟩, ?_⟩  · intro t ht    have ht' := List.mem_toFinset.mp ht    exact sx_del_clique (sx_T_clique t (h2 t ht').1) (h2 t ht').2  · intro a ha b hb hab    exact h3 a (List.mem_toFinset.mp (Finset.mem_coe.mp ha)) b (List.mem_toFinset.mp (Finset.mem_coe.mp hb)) hab  · rintro n ⟨T, hT, hP, rfl⟩    exact sx_nu_le T (fun t ht => (hT t ht).mono (SimpleGraph.deleteEdges_le _)) hPdef sx_F : List (List (Sym2 (Fin 8))) :=  sx_T.map fun t => sx_EL.filter (fun g => decide (∀ x ∈ g, x ∈ t))set_option maxRecDepth 100000 intheorem sx_enum_small : sgx_enum (5 - 1) sx_F = [] := by decide +kernelset_option maxRecDepth 100000 intheorem sx_enum_exact : ∀ s ∈ sgx_enum 5 sx_F, s.toFinset = sx_C := by decide +kerneltheorem sx_C_mem : ∀ g ∈ sx_C, g ∈ sx_E ∧ ¬ g.IsDiag := by decide +kernellemma sx_C_edge : ∀ g ∈ sx_C, g ∈ sx_G.edgeSet := by  intro g hg  obtain ⟨h1, h2⟩ := sx_C_mem g hg  induction g using Sym2.ind with  | _ a b => exact (SimpleGraph.mem_edgeSet sx_G).mpr ⟨h1, fun h => h2 (Sym2.mk_isDiag_iff.mpr h)⟩theorem sx_C_cover : ∀ t ∈ sx_T, ∃ g ∈ sx_C, ∀ x ∈ g, x ∈ t := by decide +kerneltheorem sx_C_card : sx_C.card = 5 := by decide +kernellemma sx_hit (D : Finset (Sym2 (Fin 8))) (hE : ∀ g ∈ D, g ∈ sx_G.edgeSet)    (hC : ∀ t : Finset (Fin 8), sx_G.IsNClique 3 t → ∃ g ∈ D, ∀ x ∈ g, x ∈ t) :    ∀ l ∈ sx_F, ∃ e ∈ D, e ∈ l := by  intro l hl  obtain ⟨t, ht, rfl⟩ := List.mem_map.mp hl  obtain ⟨g, hg, hgt⟩ := hC t (sx_T_clique t ht)  exact ⟨g, hg, List.mem_filter.mpr ⟨sx_edge_mem (hE g hg), decide_eq_true hgt⟩⟩theorem sx_tau_eq : simple_graph_triangle_cover_number sx_G = 5 := by  unfold simple_graph_triangle_cover_number  refine IsLeast.csInf_eq ⟨⟨sx_C, sx_C_edge, ?_, sx_C_card⟩, ?_⟩  · intro t ht    exact sx_C_cover t (sx_clique_mem ht)  · rintro n ⟨D, hE, hC, rfl⟩    by_contra hlt    obtain ⟨s, hs, _⟩ := sgx_enum_complete (5 - 1) sx_F D (sx_hit D hE hC) (by omega)    rw [sx_enum_small] at hs    simp at hslemma sx_unique (D : Finset (Sym2 (Fin 8))) (hE : ∀ g ∈ D, g ∈ sx_G.edgeSet)    (hC : ∀ t : Finset (Fin 8), sx_G.IsNClique 3 t → ∃ g ∈ D, ∀ x ∈ g, x ∈ t)    (hcard : D.card = 5) : D = sx_C := by  obtain ⟨s, hs, hsub⟩ := sgx_enum_complete 5 sx_F D (sx_hit D hE hC) (by omega)  rw [sx_enum_exact s hs] at hsub  exact (Finset.eq_of_subset_of_card_le hsub (by rw [hcard, sx_C_card])).symmset_option maxRecDepth 100000 intheorem sx_outside : sx_C \ (sx_P.image finite_vertex_set_edge_encoding).biUnion id = {s(1,4)} := by decide +kernelset_option maxRecDepth 100000 intheorem sx_last : ∀ t ∈ sx_T, (∀ x ∈ (s(1,4) : Sym2 (Fin 8)), x ∈ t) →    (∀ g ∈ sx_C, (∀ x ∈ g, x ∈ t) → g = s(1,4)) →    2 ≤ (sx_P.filter fun s => 2 ≤ (s ∩ t).card).card := by decide +kerneltheorem simple_graph_stable_lex_private_triangle_direct_exchange_counterexample :    ∃ (G : SimpleGraph (Fin 8)) (P : Finset (Finset (Fin 8)))      (C : Finset (Sym2 (Fin 8))) (e : Sym2 (Fin 8)),      simple_graph_triangle_packing_number G = 4 ∧      simple_graph_triangle_cover_number G = 5 ∧      (∀ g ∈ G.edgeSet,        simple_graph_triangle_packing_number (G.deleteEdges {g}) =          simple_graph_triangle_packing_number G) ∧      (∀ t ∈ P, G.IsNClique 3 t) ∧      (P : Set (Finset (Fin 8))).Pairwise (fun a b => (a ∩ b).card ≤ 1) ∧      P.card = simple_graph_triangle_packing_number G ∧      (∀ g ∈ C, g ∈ G.edgeSet) ∧      (∀ t : Finset (Fin 8), G.IsNClique 3 t → ∃ g ∈ C, ∀ x ∈ g, x ∈ t) ∧      C.card = simple_graph_triangle_cover_number G ∧      (∀ D : Finset (Sym2 (Fin 8)),        (∀ g ∈ D, g ∈ G.edgeSet) →        (∀ t : Finset (Fin 8), G.IsNClique 3 t → ∃ g ∈ D, ∀ x ∈ g, x ∈ t) →        D.card = simple_graph_triangle_cover_number G → D = C) ∧      C \ (P.image finite_vertex_set_edge_encoding).biUnion id = {e} ∧      (∀ t : Finset (Fin 8), G.IsNClique 3 t →        (∀ x ∈ e, x ∈ t) →        (∀ g ∈ C, (∀ x ∈ g, x ∈ t) → g = e) →        2 ≤ (P.filter fun s => 2 ≤ (s ∩ t).card).card) := by  refine ⟨sx_G, sx_P, sx_C, s(1,4), sx_pack_eq, sx_tau_eq, sx_stable, sx_P_clique, sx_P_pw, ?_,    sx_C_edge, fun t ht => sx_C_cover t (sx_clique_mem ht), ?_, ?_, sx_outside, ?_⟩  · rw [sx_P_card, sx_pack_eq]  · rw [sx_C_card, sx_tau_eq]  · intro D hE hC hcard    rw [sx_tau_eq] at hcard    exact sx_unique D hE hC hcard  · intro t ht    exact sx_last t (sx_clique_mem ht)
See it in the graphDiscuss this resultChallenge it