AFTD Auto-Formalizing Theoretical Domains

simple_graph_stable_two_packing_arbitrary_cover_counterexample

theoremverified

There is a finite edge-deletion-stable graph with triangle packing number two, a maximum packing P, and a four-edge triangle cover C such that C is not contained in the union of the edges of P and any second maximum packing.

Statement

theorem simple_graph_stable_two_packing_arbitrary_cover_counterexample :
    ∃ (G : SimpleGraph (Fin 6)) (P : Finset (Finset (Fin 6)))
      (C : Finset (Sym2 (Fin 6))),
      simple_graph_triangle_packing_number G = 2 ∧
      (∀ e ∈ G.edgeSet,
        simple_graph_triangle_packing_number (G.deleteEdges {e}) =
          simple_graph_triangle_packing_number G) ∧
      (∀ t ∈ P, G.IsNClique 3 t) ∧
      (P : Set (Finset (Fin 6))).Pairwise (fun a b => (a ∩ b).card ≤ 1) ∧
      P.card = simple_graph_triangle_packing_number G ∧
      (∀ e ∈ C, e ∈ G.edgeSet) ∧
      (∀ t : Finset (Fin 6), G.IsNClique 3 t → ∃ e ∈ C, ∀ x ∈ e, x ∈ t) ∧
      C.card = 4 ∧
      ∀ Q : Finset (Finset (Fin 6)),
        (∀ t ∈ Q, G.IsNClique 3 t) →
        (Q : Set (Finset (Fin 6))).Pairwise (fun a b => (a ∩ b).card ≤ 1) →
        Q.card = simple_graph_triangle_packing_number G →
        ¬ C ⊆ (P.image finite_vertex_set_edge_encoding).biUnion id ∪
          (Q.image finite_vertex_set_edge_encoding).biUnion id
Source
Explicit six-vertex wheel, experiment 16018; triangle packing and covering definitions from arXiv:2610.15539, Section 1.
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

The 5-wheel graph W_5 (a 5-cycle with a central hub vertex 5) has triangle packing number 2 and is edge-deletion stable because removing any edge leaves two disjoint triangles. The four-edge set C covers all five triangles, and P = {{0,1,5}, {2,3,5}} is a maximum packing. Two edges of C are rim edges not in P, and any triangles containing them must both contain the hub 5, forcing them to be {0,4,5} and {3,4,5}; since these two share the spoke edge {4,5}, no packing Q can contain both, so C cannot be covered by E(P) ∪ E(Q).

  1. The wheel graph is well-defined with symmetric and loopless adjacency.

    Symmetry follows from symmetry of unordered pairs, and looplessness because edges connect distinct vertices.

    lines 8–9

      symm := ⟨fun a b h => ⟨by simpa [Sym2.eq_swap] using h.1, h.2.symm⟩⟩
      loopless := ⟨fun a => by simp⟩
  2. Every triangle in the wheel graph contains the hub vertex 5.

    Expanding the definition of a 3-clique and exhausting all triples of adjacent vertices shows that vertex 5 is always in the triangle.

    lines 23–30

      rw [SimpleGraph.is3Clique_iff] at ht
      obtain ⟨a, b, c, hab, hac, hbc, rfl⟩ := ht
      exact (by decide : ∀ a b c : Fin 6,
        simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel.Adj a b →
        simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel.Adj a c →
        simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel.Adj b c →
        (5 : Fin 6) ∈ ({a, b, c} : Finset (Fin 6))) a b c hab hac hbc
    
  3. Any edge-disjoint triangle packing in the wheel (or a subgraph) has size at most 2.

    Since each triangle contains vertex 5, removing 5 from each triangle gives pairwise disjoint pairs of rim vertices. Since there are only 5 rim vertices, at most two disjoint pairs can be chosen, so the packing has size at most 2.

    lines 50–86

      have hcard2 : ∀ t ∈ T, (t.erase 5).card = 2 := by
        intro t ht
        have h3 : t.card = 3 := ((SimpleGraph.isNClique_iff H).mp (hT t ht)).2
        rw [Finset.card_erase_of_mem (h5 t (hT t ht)), h3]
      have hdisj : ∀ t ∈ T, ∀ u ∈ T, t ≠ u → Disjoint (t.erase 5) (u.erase 5) := by
        intro t ht u hu htu
        rw [Finset.disjoint_left]
        intro x hx1 hx2
        have hpw' : (t ∩ u).card ≤ 1 := hpw ht hu htu
        have h5t : (5 : Fin 6) ∈ t := h5 t (hT t ht)
        have h5u : (5 : Fin 6) ∈ u := h5 u (hT u hu)
        have hxne : x ≠ 5 := Finset.ne_of_mem_erase hx1
        have hsub : ({x, 5} : Finset (Fin 6)) ⊆ t ∩ u := by
          intro y hy
          simp only [Finset.mem_insert, Finset.mem_singleton] at hy
          rcases hy with rfl | rfl
          · exact Finset.mem_inter.mpr ⟨Finset.mem_of_mem_erase hx1, Finset.mem_of_mem_erase hx2⟩
          · exact Finset.mem_inter.mpr ⟨h5t, h5u⟩
        have h2 : ({x, 5} : Finset (Fin 6)).card = 2 := by
          rw [Finset.card_insert_of_notMem, Finset.card_singleton]
          simp [hxne]
        have := Finset.card_le_card hsub
        omega
      have hsum : (T.biUnion fun t => t.erase 5).card = T.card * 2 := by
        rw [Finset.card_biUnion]
        · rw [Finset.sum_congr rfl (fun u hu => hcard2 u hu), Finset.sum_const, Nat.nsmul_eq_mul]
        · intro a ha b hb hab
          exact hdisj a ha b hb hab
      have hsub2 : (T.biUnion fun t => t.erase 5) ⊆ (Finset.univ : Finset (Fin 6)).erase 5 := by
        intro x hx
        simp only [Finset.mem_biUnion] at hx
        obtain ⟨t, ht, hxt⟩ := hx
        exact Finset.mem_erase.mpr ⟨Finset.ne_of_mem_erase hxt, Finset.mem_univ x⟩
      have hle : (T.biUnion fun t => t.erase 5).card ≤ 5 := by
        have := Finset.card_le_card hsub2
        simpa using this
      omega
  4. The triangle packing number of any such subgraph is at most 2.

    Taking the supremum over all packings, each bounded by 2, gives an upper bound of 2 on the triangle packing number.

    lines 92–96

      rw [simple_graph_triangle_packing_number]
      refine csSup_le ⟨0, ∅, by simp, by simp, by simp⟩ ?_
      rintro n ⟨T, hT, hpw, rfl⟩
      exact simple_graph_stable_two_packing_arbitrary_cover_counterexample_card_le_two_of_packing
        H h5 T hT hpw
  5. The triangle packing number of the wheel is exactly 2.

    The lower bound of 2 is witnessed by the two edge-disjoint triangles {0,1,5} and {2,3,5}, matching the upper bound of 2.

    lines 106–123

      rw [simple_graph_triangle_packing_number]
      refine le_csSup ⟨2, ?_⟩ ⟨T, hT, hpw, hcard⟩
      rintro b ⟨T', h1, h2, rfl⟩
      exact simple_graph_stable_two_packing_arbitrary_cover_counterexample_card_le_two_of_packing
        H h5 T' h1 h2
    
    lemma simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel_packing_number :
        simple_graph_triangle_packing_number
          simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel = 2 := by
      apply le_antisymm
      · exact simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _
          simple_graph_stable_two_packing_arbitrary_cover_counterexample_three_clique_contains_five
      · refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _
          simple_graph_stable_two_packing_arbitrary_cover_counterexample_three_clique_contains_five
          {{0,1,5},{2,3,5}} ?_ ?_ (by decide)
        · decide
        · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide
    
  6. The edge set of the wheel graph matches the explicit set of 10 edges.

    Unordered pairs in the edge set correspond to the defined edges since none of the specified edges are self-loops.

    lines 127–135

      rw [SimpleGraph.mem_edgeSet]
      constructor
      · intro h; exact h.1
      · intro h
        refine ⟨h, ?_⟩
        intro hab
        exact (by decide : ∀ e ∈ simple_graph_stable_two_packing_arbitrary_cover_counterexample_edges,
          ¬ e.IsDiag) _ h (Sym2.mk_isDiag_iff.mpr hab)
    
  7. The four-edge set C covers all triangles of the wheel graph.

    Exhausting all triangles in the wheel shows that each contains at least one of the four edges in C.

    lines 151–164

    lemma simple_graph_stable_two_packing_arbitrary_cover_counterexample_cover (t : Finset (Fin 6))
        (ht : simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel.IsNClique 3 t) :
        ∃ e ∈ simple_graph_stable_two_packing_arbitrary_cover_counterexample_coverSet,
          ∀ x ∈ e, x ∈ t := by
      rw [SimpleGraph.is3Clique_iff] at ht
      obtain ⟨a, b, c, hab, hac, hbc, rfl⟩ := ht
      rcases simple_graph_stable_two_packing_arbitrary_cover_counterexample_cover_aux a b c hab hac hbc
        with h | h | h | h
      · exact ⟨s(0,4), by decide, h⟩
      · exact ⟨s(3,4), by decide, h⟩
      · exact ⟨s(1,5), by decide, h⟩
      · exact ⟨s(2,5), by decide, h⟩
    
  8. The edge encoding of a vertex set consists of all unordered pairs of distinct vertices in the set.

    Unfolding the definition of finite_vertex_set_edge_encoding and simplifying shows that an edge belongs to the encoding if and only if both endpoints belong to the set and are distinct.

    lines 168–169

      rw [finite_vertex_set_edge_encoding, Finset.mem_filter, Finset.mk_mem_sym2_iff, Sym2.mk_isDiag_iff]
      tauto
  9. The wheel graph is edge-deletion stable with triangle packing number 2.

    For each of the 10 edges, removing that edge still leaves two edge-disjoint triangles, so the packing number remains 2.

    lines 178–260

      have h5del : ∀ (e' : Sym2 (Fin 6)) (t : Finset (Fin 6)),
          (simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel.deleteEdges
            {e'}).IsNClique 3 t → (5 : Fin 6) ∈ t :=
        fun e' t ht => simple_graph_stable_two_packing_arbitrary_cover_counterexample_contains_five_of_le
          (SimpleGraph.deleteEdges_le _) t ht
      induction e using Sym2.ind with
      | _ a b =>
        have he' : s(a,b) ∈ simple_graph_stable_two_packing_arbitrary_cover_counterexample_edges :=
          simple_graph_stable_two_packing_arbitrary_cover_counterexample_mem_edgeSet_iff.mp he
        rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel_packing_number]
        simp only [simple_graph_stable_two_packing_arbitrary_cover_counterexample_edges,
          Finset.mem_insert, Finset.mem_singleton] at he'
        rcases he' with h | h | h | h | h | h | h | h | h | h
        · rw [h]; refine le_antisymm
            (simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _
              (h5del _)) ?_
          refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _
            (h5del _) {{2,3,5},{0,4,5}} ?_ ?_ (by decide)
          · decide
          · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide
        · rw [h]; refine le_antisymm
            (simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _
              (h5del _)) ?_
          refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _
            (h5del _) {{2,3,5},{0,4,5}} ?_ ?_ (by decide)
          · decide
          · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide
        · rw [h]; refine le_antisymm
            (simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _
              (h5del _)) ?_
          refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _
            (h5del _) {{1,2,5},{0,4,5}} ?_ ?_ (by decide)
          · decide
          · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide
        · rw [h]; refine le_antisymm
            (simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _
              (h5del _)) ?_
          refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _
            (h5del _) {{2,3,5},{0,4,5}} ?_ ?_ (by decide)
          · decide
          · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide
        · rw [h]; refine le_antisymm
            (simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _
              (h5del _)) ?_
          refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _
            (h5del _) {{1,2,5},{3,4,5}} ?_ ?_ (by decide)
          · decide
          · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide
        · rw [h]; refine le_antisymm
            (simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _
              (h5del _)) ?_
          refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _
            (h5del _) {{1,2,5},{3,4,5}} ?_ ?_ (by decide)
          · decide
          · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide
        · rw [h]; refine le_antisymm
            (simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _
              (h5del _)) ?_
          refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _
            (h5del _) {{2,3,5},{0,4,5}} ?_ ?_ (by decide)
          · decide
          · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide
        · rw [h]; refine le_antisymm
            (simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _
              (h5del _)) ?_
          refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _
            (h5del _) {{0,1,5},{3,4,5}} ?_ ?_ (by decide)
          · decide
          · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide
        · rw [h]; refine le_antisymm
            (simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _
              (h5del _)) ?_
          refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _
            (h5del _) {{1,2,5},{0,4,5}} ?_ ?_ (by decide)
          · decide
          · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide
        · rw [h]; refine le_antisymm
            (simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _
              (h5del _)) ?_
          refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _
            (h5del _) {{0,1,5},{2,3,5}} ?_ ?_ (by decide)
          · decide
          · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide
  10. The wheel graph G, packing P, and cover C satisfy all graph and cover properties.

    Providing the 5-wheel graph, the 2-packing P = {{0,1,5}, {2,3,5}}, and the 4-edge cover C, we verify that G has packing number 2, is edge-deletion stable, P is a maximum packing, and C is a 4-edge triangle cover.

    lines 281–294

      refine ⟨simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel,
        {{0,1,5},{2,3,5}}, simple_graph_stable_two_packing_arbitrary_cover_counterexample_coverSet,
        ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩
      · exact simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel_packing_number
      · intro e he
        exact simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_delete e he
      · decide
      · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide
      · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel_packing_number]; decide
      · simp only [simple_graph_stable_two_packing_arbitrary_cover_counterexample_mem_edgeSet]
        decide
      · intro t ht
        exact simple_graph_stable_two_packing_arbitrary_cover_counterexample_cover t ht
      · decide
  11. No second maximum packing Q can cover C together with P.

    The two rim edges in C do not belong to P, so any candidate packing Q covering C must contain both. Since all triangles contain 5, the triangles in Q containing these edges must be {0,4,5} and {3,4,5}. But these two triangles share the spoke edge {4,5}, contradicting the packing condition.

    lines 295–353

      · intro Q hQ hpw hcard hsub
        have h04C : s(0,4) ∈ simple_graph_stable_two_packing_arbitrary_cover_counterexample_coverSet :=
          by decide
        have h34C : s(3,4) ∈ simple_graph_stable_two_packing_arbitrary_cover_counterexample_coverSet :=
          by decide
        have h04P : s(0,4) ∉ (({{0,1,5},{2,3,5}} : Finset (Finset (Fin 6))).image
            finite_vertex_set_edge_encoding).biUnion id := by decide
        have h34P : s(3,4) ∉ (({{0,1,5},{2,3,5}} : Finset (Finset (Fin 6))).image
            finite_vertex_set_edge_encoding).biUnion id := by decide
        have h04 := hsub h04C
        rw [Finset.mem_union] at h04
        have h34 := hsub h34C
        rw [Finset.mem_union] at h34
        rcases h04 with h04 | h04
        · exact h04P h04
        · rcases h34 with h34 | h34
          · exact h34P h34
          · obtain ⟨u, hu, h04u⟩ := Finset.mem_biUnion.mp h04
            obtain ⟨t, htQ, rfl⟩ := Finset.mem_image.mp hu
            obtain ⟨u', hu', h34u⟩ := Finset.mem_biUnion.mp h34
            obtain ⟨t', ht'Q, rfl⟩ := Finset.mem_image.mp hu'
            have h04' := simple_graph_stable_two_packing_arbitrary_cover_counterexample_mem_encoding.mp h04u
            have h34' := simple_graph_stable_two_packing_arbitrary_cover_counterexample_mem_encoding.mp h34u
            obtain ⟨h0t, h4t, -⟩ := h04'
            obtain ⟨h3t', h4t', -⟩ := h34'
            have h5t : (5 : Fin 6) ∈ t :=
              simple_graph_stable_two_packing_arbitrary_cover_counterexample_three_clique_contains_five
                t (hQ t htQ)
            have h5t' : (5 : Fin 6) ∈ t' :=
              simple_graph_stable_two_packing_arbitrary_cover_counterexample_three_clique_contains_five
                t' (hQ t' ht'Q)
            have hct : t.card = 3 := ((SimpleGraph.isNClique_iff
              simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel).mp (hQ t htQ)).2
            have hct' : t'.card = 3 := ((SimpleGraph.isNClique_iff
              simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel).mp (hQ t' ht'Q)).2
            have ht_eq : t = {0,4,5} := by
              have hsubst : ({0,4,5} : Finset (Fin 6)) ⊆ t := by
                intro x hx
                simp only [Finset.mem_insert, Finset.mem_singleton] at hx
                rcases hx with rfl | rfl | rfl
                · exact h0t
                · exact h4t
                · exact h5t
              have hc : ({0,4,5} : Finset (Fin 6)).card = 3 := by decide
              exact (Finset.eq_of_subset_of_card_le hsubst (by omega)).symm
            have ht'_eq : t' = {3,4,5} := by
              have hsubst : ({3,4,5} : Finset (Fin 6)) ⊆ t' := by
                intro x hx
                simp only [Finset.mem_insert, Finset.mem_singleton] at hx
                rcases hx with rfl | rfl | rfl
                · exact h3t'
                · exact h4t'
                · exact h5t'
              have hc : ({3,4,5} : Finset (Fin 6)).card = 3 := by decide
              exact (Finset.eq_of_subset_of_card_le hsubst (by omega)).symm
            have hne : t' ≠ t := by rw [ht'_eq, ht_eq]; decide
            have hpw' := hpw ht'Q htQ hne
            rw [ht'_eq, ht_eq] at hpw'
            exact absurd hpw' (by decide)

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 Sym2def simple_graph_stable_two_packing_arbitrary_cover_counterexample_edges : Finset (Sym2 (Fin 6)) :=  {s(0,1), s(1,2), s(2,3), s(3,4), s(0,4), s(0,5), s(1,5), s(2,5), s(3,5), s(4,5)}abbrev simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel : SimpleGraph (Fin 6) where  Adj a b := s(a,b) ∈ simple_graph_stable_two_packing_arbitrary_cover_counterexample_edges ∧ a ≠ b  symm := ⟨fun a b h => ⟨by simpa [Sym2.eq_swap] using h.1, h.2.symm⟩⟩  loopless := ⟨fun a => by simp⟩def simple_graph_stable_two_packing_arbitrary_cover_counterexample_coverSet : Finset (Sym2 (Fin 6)) :=  {s(0,4), s(3,4), s(1,5), s(2,5)}lemma simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff    (T : Finset (Finset (Fin 6))) :    (T : Set (Finset (Fin 6))).Pairwise (fun a b => (a ∩ b).card ≤ 1) ↔    ∀ x ∈ T, ∀ y ∈ T, x ≠ y → (x ∩ y).card ≤ 1 := Iff.rfllemma simple_graph_stable_two_packing_arbitrary_cover_counterexample_three_clique_contains_five    (t : Finset (Fin 6))    (ht : simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel.IsNClique 3 t) :    (5 : Fin 6) ∈ t := by  rw [SimpleGraph.is3Clique_iff] at ht  obtain ⟨a, b, c, hab, hac, hbc, rfl⟩ := ht  exact (by decide : ∀ a b c : Fin 6,    simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel.Adj a b →    simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel.Adj a c →    simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel.Adj b c →    (5 : Fin 6) ∈ ({a, b, c} : Finset (Fin 6))) a b c hab hac hbclemma simple_graph_stable_two_packing_arbitrary_cover_counterexample_isNClique_mono    {G H : SimpleGraph (Fin 6)} (h : G ≤ H) {n : ℕ} {s : Finset (Fin 6)}    (hs : G.IsNClique n s) : H.IsNClique n s :=  ⟨SimpleGraph.IsClique.mono h hs.1, hs.2⟩lemma simple_graph_stable_two_packing_arbitrary_cover_counterexample_contains_five_of_le    {H : SimpleGraph (Fin 6)}    (h : H ≤ simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel)    (t : Finset (Fin 6)) (ht : H.IsNClique 3 t) : (5 : Fin 6) ∈ t :=  simple_graph_stable_two_packing_arbitrary_cover_counterexample_three_clique_contains_five t    (simple_graph_stable_two_packing_arbitrary_cover_counterexample_isNClique_mono h ht)lemma simple_graph_stable_two_packing_arbitrary_cover_counterexample_card_le_two_of_packing    (H : SimpleGraph (Fin 6))    (h5 : ∀ t, H.IsNClique 3 t → (5 : Fin 6) ∈ t)    (T : Finset (Finset (Fin 6)))    (hT : ∀ t ∈ T, H.IsNClique 3 t)    (hpw : (T : Set (Finset (Fin 6))).Pairwise (fun a b => (a ∩ b).card ≤ 1)) :    T.card ≤ 2 := by  have hcard2 : ∀ t ∈ T, (t.erase 5).card = 2 := by    intro t ht    have h3 : t.card = 3 := ((SimpleGraph.isNClique_iff H).mp (hT t ht)).2    rw [Finset.card_erase_of_mem (h5 t (hT t ht)), h3]  have hdisj : ∀ t ∈ T, ∀ u ∈ T, t ≠ u → Disjoint (t.erase 5) (u.erase 5) := by    intro t ht u hu htu    rw [Finset.disjoint_left]    intro x hx1 hx2    have hpw' : (t ∩ u).card ≤ 1 := hpw ht hu htu    have h5t : (5 : Fin 6) ∈ t := h5 t (hT t ht)    have h5u : (5 : Fin 6) ∈ u := h5 u (hT u hu)    have hxne : x ≠ 5 := Finset.ne_of_mem_erase hx1    have hsub : ({x, 5} : Finset (Fin 6)) ⊆ t ∩ u := by      intro y hy      simp only [Finset.mem_insert, Finset.mem_singleton] at hy      rcases hy with rfl | rfl      · exact Finset.mem_inter.mpr ⟨Finset.mem_of_mem_erase hx1, Finset.mem_of_mem_erase hx2⟩      · exact Finset.mem_inter.mpr ⟨h5t, h5u⟩    have h2 : ({x, 5} : Finset (Fin 6)).card = 2 := by      rw [Finset.card_insert_of_notMem, Finset.card_singleton]      simp [hxne]    have := Finset.card_le_card hsub    omega  have hsum : (T.biUnion fun t => t.erase 5).card = T.card * 2 := by    rw [Finset.card_biUnion]    · rw [Finset.sum_congr rfl (fun u hu => hcard2 u hu), Finset.sum_const, Nat.nsmul_eq_mul]    · intro a ha b hb hab      exact hdisj a ha b hb hab  have hsub2 : (T.biUnion fun t => t.erase 5) ⊆ (Finset.univ : Finset (Fin 6)).erase 5 := by    intro x hx    simp only [Finset.mem_biUnion] at hx    obtain ⟨t, ht, hxt⟩ := hx    exact Finset.mem_erase.mpr ⟨Finset.ne_of_mem_erase hxt, Finset.mem_univ x⟩  have hle : (T.biUnion fun t => t.erase 5).card ≤ 5 := by    have := Finset.card_le_card hsub2    simpa using this  omegalemma simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two    (H : SimpleGraph (Fin 6))    (h5 : ∀ t, H.IsNClique 3 t → (5 : Fin 6) ∈ t) :    simple_graph_triangle_packing_number H ≤ 2 := by  rw [simple_graph_triangle_packing_number]  refine csSup_le ⟨0, ∅, by simp, by simp, by simp⟩ ?_  rintro n ⟨T, hT, hpw, rfl⟩  exact simple_graph_stable_two_packing_arbitrary_cover_counterexample_card_le_two_of_packing    H h5 T hT hpwlemma simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two    (H : SimpleGraph (Fin 6))    (h5 : ∀ t, H.IsNClique 3 t → (5 : Fin 6) ∈ t)    (T : Finset (Finset (Fin 6)))    (hT : ∀ t ∈ T, H.IsNClique 3 t)    (hpw : (T : Set (Finset (Fin 6))).Pairwise (fun a b => (a ∩ b).card ≤ 1))    (hcard : T.card = 2) :    2 ≤ simple_graph_triangle_packing_number H := by  rw [simple_graph_triangle_packing_number]  refine le_csSup ⟨2, ?_⟩ ⟨T, hT, hpw, hcard⟩  rintro b ⟨T', h1, h2, rfl⟩  exact simple_graph_stable_two_packing_arbitrary_cover_counterexample_card_le_two_of_packing    H h5 T' h1 h2lemma simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel_packing_number :    simple_graph_triangle_packing_number      simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel = 2 := by  apply le_antisymm  · exact simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _      simple_graph_stable_two_packing_arbitrary_cover_counterexample_three_clique_contains_five  · refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _      simple_graph_stable_two_packing_arbitrary_cover_counterexample_three_clique_contains_five      {{0,1,5},{2,3,5}} ?_ ?_ (by decide)    · decide    · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decidelemma simple_graph_stable_two_packing_arbitrary_cover_counterexample_mem_edgeSet_iff {a b : Fin 6} :    s(a,b) ∈ simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel.edgeSet ↔      s(a,b) ∈ simple_graph_stable_two_packing_arbitrary_cover_counterexample_edges := by  rw [SimpleGraph.mem_edgeSet]  constructor  · intro h; exact h.1  · intro h    refine ⟨h, ?_⟩    intro hab    exact (by decide : ∀ e ∈ simple_graph_stable_two_packing_arbitrary_cover_counterexample_edges,      ¬ e.IsDiag) _ h (Sym2.mk_isDiag_iff.mpr hab)lemma simple_graph_stable_two_packing_arbitrary_cover_counterexample_mem_edgeSet (e : Sym2 (Fin 6)) :    e ∈ simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel.edgeSet ↔      e ∈ simple_graph_stable_two_packing_arbitrary_cover_counterexample_edges :=  Sym2.ind (fun a b =>    simple_graph_stable_two_packing_arbitrary_cover_counterexample_mem_edgeSet_iff (a := a) (b := b)) elemma simple_graph_stable_two_packing_arbitrary_cover_counterexample_cover_aux :    ∀ a b c : Fin 6,      simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel.Adj a b →      simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel.Adj a c →      simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel.Adj b c →    (∀ x ∈ s(0,4), x ∈ ({a, b, c} : Finset (Fin 6))) ∨    (∀ x ∈ s(3,4), x ∈ ({a, b, c} : Finset (Fin 6))) ∨    (∀ x ∈ s(1,5), x ∈ ({a, b, c} : Finset (Fin 6))) ∨    (∀ x ∈ s(2,5), x ∈ ({a, b, c} : Finset (Fin 6))) := by decidelemma simple_graph_stable_two_packing_arbitrary_cover_counterexample_cover (t : Finset (Fin 6))    (ht : simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel.IsNClique 3 t) :    ∃ e ∈ simple_graph_stable_two_packing_arbitrary_cover_counterexample_coverSet,      ∀ x ∈ e, x ∈ t := by  rw [SimpleGraph.is3Clique_iff] at ht  obtain ⟨a, b, c, hab, hac, hbc, rfl⟩ := ht  rcases simple_graph_stable_two_packing_arbitrary_cover_counterexample_cover_aux a b c hab hac hbc    with h | h | h | h  · exact ⟨s(0,4), by decide, h⟩  · exact ⟨s(3,4), by decide, h⟩  · exact ⟨s(1,5), by decide, h⟩  · exact ⟨s(2,5), by decide, h⟩lemma simple_graph_stable_two_packing_arbitrary_cover_counterexample_mem_encoding    {t : Finset (Fin 6)} {a b : Fin 6} :    s(a,b) ∈ finite_vertex_set_edge_encoding t ↔ a ∈ t ∧ b ∈ t ∧ a ≠ b := by  rw [finite_vertex_set_edge_encoding, Finset.mem_filter, Finset.mk_mem_sym2_iff, Sym2.mk_isDiag_iff]  tautolemma simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_delete    (e : Sym2 (Fin 6))    (he : e ∈ simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel.edgeSet) :    simple_graph_triangle_packing_number        (simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel.deleteEdges {e}) =      simple_graph_triangle_packing_number        simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel := by  have h5del : ∀ (e' : Sym2 (Fin 6)) (t : Finset (Fin 6)),      (simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel.deleteEdges        {e'}).IsNClique 3 t → (5 : Fin 6) ∈ t :=    fun e' t ht => simple_graph_stable_two_packing_arbitrary_cover_counterexample_contains_five_of_le      (SimpleGraph.deleteEdges_le _) t ht  induction e using Sym2.ind with  | _ a b =>    have he' : s(a,b) ∈ simple_graph_stable_two_packing_arbitrary_cover_counterexample_edges :=      simple_graph_stable_two_packing_arbitrary_cover_counterexample_mem_edgeSet_iff.mp he    rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel_packing_number]    simp only [simple_graph_stable_two_packing_arbitrary_cover_counterexample_edges,      Finset.mem_insert, Finset.mem_singleton] at he'    rcases he' with h | h | h | h | h | h | h | h | h | h    · rw [h]; refine le_antisymm        (simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _          (h5del _)) ?_      refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _        (h5del _) {{2,3,5},{0,4,5}} ?_ ?_ (by decide)      · decide      · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide    · rw [h]; refine le_antisymm        (simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _          (h5del _)) ?_      refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _        (h5del _) {{2,3,5},{0,4,5}} ?_ ?_ (by decide)      · decide      · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide    · rw [h]; refine le_antisymm        (simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _          (h5del _)) ?_      refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _        (h5del _) {{1,2,5},{0,4,5}} ?_ ?_ (by decide)      · decide      · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide    · rw [h]; refine le_antisymm        (simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _          (h5del _)) ?_      refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _        (h5del _) {{2,3,5},{0,4,5}} ?_ ?_ (by decide)      · decide      · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide    · rw [h]; refine le_antisymm        (simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _          (h5del _)) ?_      refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _        (h5del _) {{1,2,5},{3,4,5}} ?_ ?_ (by decide)      · decide      · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide    · rw [h]; refine le_antisymm        (simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _          (h5del _)) ?_      refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _        (h5del _) {{1,2,5},{3,4,5}} ?_ ?_ (by decide)      · decide      · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide    · rw [h]; refine le_antisymm        (simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _          (h5del _)) ?_      refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _        (h5del _) {{2,3,5},{0,4,5}} ?_ ?_ (by decide)      · decide      · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide    · rw [h]; refine le_antisymm        (simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _          (h5del _)) ?_      refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _        (h5del _) {{0,1,5},{3,4,5}} ?_ ?_ (by decide)      · decide      · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide    · rw [h]; refine le_antisymm        (simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _          (h5del _)) ?_      refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _        (h5del _) {{1,2,5},{0,4,5}} ?_ ?_ (by decide)      · decide      · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide    · rw [h]; refine le_antisymm        (simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_le_two _          (h5del _)) ?_      refine simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_ge_two _        (h5del _) {{0,1,5},{2,3,5}} ?_ ?_ (by decide)      · decide      · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decidetheorem simple_graph_stable_two_packing_arbitrary_cover_counterexample :    ∃ (G : SimpleGraph (Fin 6)) (P : Finset (Finset (Fin 6)))      (C : Finset (Sym2 (Fin 6))),      simple_graph_triangle_packing_number G = 2 ∧      (∀ e ∈ G.edgeSet,        simple_graph_triangle_packing_number (G.deleteEdges {e}) =          simple_graph_triangle_packing_number G) ∧      (∀ t ∈ P, G.IsNClique 3 t) ∧      (P : Set (Finset (Fin 6))).Pairwise (fun a b => (a ∩ b).card ≤ 1) ∧      P.card = simple_graph_triangle_packing_number G ∧      (∀ e ∈ C, e ∈ G.edgeSet) ∧      (∀ t : Finset (Fin 6), G.IsNClique 3 t → ∃ e ∈ C, ∀ x ∈ e, x ∈ t) ∧      C.card = 4 ∧      ∀ Q : Finset (Finset (Fin 6)),        (∀ t ∈ Q, G.IsNClique 3 t) →        (Q : Set (Finset (Fin 6))).Pairwise (fun a b => (a ∩ b).card ≤ 1) →        Q.card = simple_graph_triangle_packing_number G →        ¬ C ⊆ (P.image finite_vertex_set_edge_encoding).biUnion id ∪          (Q.image finite_vertex_set_edge_encoding).biUnion id := by  refine ⟨simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel,    {{0,1,5},{2,3,5}}, simple_graph_stable_two_packing_arbitrary_cover_counterexample_coverSet,    ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩  · exact simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel_packing_number  · intro e he    exact simple_graph_stable_two_packing_arbitrary_cover_counterexample_packing_number_delete e he  · decide  · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_set_pairwise_iff]; decide  · rw [simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel_packing_number]; decide  · simp only [simple_graph_stable_two_packing_arbitrary_cover_counterexample_mem_edgeSet]    decide  · intro t ht    exact simple_graph_stable_two_packing_arbitrary_cover_counterexample_cover t ht  · decide  · intro Q hQ hpw hcard hsub    have h04C : s(0,4) ∈ simple_graph_stable_two_packing_arbitrary_cover_counterexample_coverSet :=      by decide    have h34C : s(3,4) ∈ simple_graph_stable_two_packing_arbitrary_cover_counterexample_coverSet :=      by decide    have h04P : s(0,4) ∉ (({{0,1,5},{2,3,5}} : Finset (Finset (Fin 6))).image        finite_vertex_set_edge_encoding).biUnion id := by decide    have h34P : s(3,4) ∉ (({{0,1,5},{2,3,5}} : Finset (Finset (Fin 6))).image        finite_vertex_set_edge_encoding).biUnion id := by decide    have h04 := hsub h04C    rw [Finset.mem_union] at h04    have h34 := hsub h34C    rw [Finset.mem_union] at h34    rcases h04 with h04 | h04    · exact h04P h04    · rcases h34 with h34 | h34      · exact h34P h34      · obtain ⟨u, hu, h04u⟩ := Finset.mem_biUnion.mp h04        obtain ⟨t, htQ, rfl⟩ := Finset.mem_image.mp hu        obtain ⟨u', hu', h34u⟩ := Finset.mem_biUnion.mp h34        obtain ⟨t', ht'Q, rfl⟩ := Finset.mem_image.mp hu'        have h04' := simple_graph_stable_two_packing_arbitrary_cover_counterexample_mem_encoding.mp h04u        have h34' := simple_graph_stable_two_packing_arbitrary_cover_counterexample_mem_encoding.mp h34u        obtain ⟨h0t, h4t, -⟩ := h04'        obtain ⟨h3t', h4t', -⟩ := h34'        have h5t : (5 : Fin 6) ∈ t :=          simple_graph_stable_two_packing_arbitrary_cover_counterexample_three_clique_contains_five            t (hQ t htQ)        have h5t' : (5 : Fin 6) ∈ t' :=          simple_graph_stable_two_packing_arbitrary_cover_counterexample_three_clique_contains_five            t' (hQ t' ht'Q)        have hct : t.card = 3 := ((SimpleGraph.isNClique_iff          simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel).mp (hQ t htQ)).2        have hct' : t'.card = 3 := ((SimpleGraph.isNClique_iff          simple_graph_stable_two_packing_arbitrary_cover_counterexample_wheel).mp (hQ t' ht'Q)).2        have ht_eq : t = {0,4,5} := by          have hsubst : ({0,4,5} : Finset (Fin 6)) ⊆ t := by            intro x hx            simp only [Finset.mem_insert, Finset.mem_singleton] at hx            rcases hx with rfl | rfl | rfl            · exact h0t            · exact h4t            · exact h5t          have hc : ({0,4,5} : Finset (Fin 6)).card = 3 := by decide          exact (Finset.eq_of_subset_of_card_le hsubst (by omega)).symm        have ht'_eq : t' = {3,4,5} := by          have hsubst : ({3,4,5} : Finset (Fin 6)) ⊆ t' := by            intro x hx            simp only [Finset.mem_insert, Finset.mem_singleton] at hx            rcases hx with rfl | rfl | rfl            · exact h3t'            · exact h4t'            · exact h5t'          have hc : ({3,4,5} : Finset (Fin 6)).card = 3 := by decide          exact (Finset.eq_of_subset_of_card_le hsubst (by omega)).symm        have hne : t' ≠ t := by rw [ht'_eq, ht_eq]; decide        have hpw' := hpw ht'Q htQ hne        rw [ht'_eq, ht_eq] at hpw'        exact absurd hpw' (by decide)
See it in the graphDiscuss this resultChallenge it