AFTD Auto-Formalizing Theoretical Domains

simple_graph_stable_triangle_not_in_maximum_packing_example

theoremverified

There is a finite graph with triangle packing number two in which every edge deletion preserves the packing number, but some triangle belongs to no maximum triangle packing.

Statement

theorem simple_graph_stable_triangle_not_in_maximum_packing_example :
    ∃ G : SimpleGraph (Fin 5),
      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 : Finset (Fin 5), G.IsNClique 3 t ∧
        ∀ P : Finset (Finset (Fin 5)),
          (∀ s ∈ P, G.IsNClique 3 s) →
          (P : Set (Finset (Fin 5))).Pairwise (fun a b => (a ∩ b).card ≤ 1) →
          P.card = simple_graph_triangle_packing_number G → t ∉ P
Source
Explicit five-vertex computation, experiment 15967; triangle packing definition from arXiv:2610.15539, Section 1.
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

The graph G is the complete graph K₅ on vertices {0, 1, 2, 3, 4} minus the single edge {0, 2}. Because any two edge-disjoint triangles on 5 vertices must share at most one vertex and therefore have union of size 3 + 3 - 1 = 5, no 5-vertex graph can contain three edge-disjoint triangles, bounding the triangle packing number ν(G) ≤ 2. The packing number is exactly two and is preserved by every edge deletion because three explicit 2-triangle packings are exhibited such that every edge misses at least one packing. Finally, the triangle t = {1, 3, 4} belongs to no maximum packing because any compatible edge-disjoint triangle would need to contain both remaining vertices 0 and 2, but the edge {0, 2} is missing in G.

  1. Adjacency in G is decidable. automation

    Two vertices u and v in Fin 5 are adjacent if u ≠ v and {u, v} ≠ {0, 2}; decidability is derived automatically via typeclass synthesis.

    lines 6–7

    instance : DecidableRel simple_graph_stable_triangle_not_in_maximum_packing_example_G.Adj := by
      intro u v; dsimp [simple_graph_stable_triangle_not_in_maximum_packing_example_G]; infer_instance
  2. The candidate packings P₀, P₃, and P₄ each consist of two edge-disjoint triangles, and P₀ is a valid triangle packing in G. automation

    Computational reflection (`decide`) verifies for P₀, P₃, and P₄ that triangles pairwise intersect in at most one vertex, that each set has cardinality two, and that the elements of P₀ are 3-cliques in G.

    lines 16–40

    lemma simple_graph_stable_triangle_not_in_maximum_packing_example_P0_pw :
        (simple_graph_stable_triangle_not_in_maximum_packing_example_P0 : Set (Finset (Fin 5))).Pairwise
          (fun a b => (a ∩ b).card ≤ 1) := by decide
    
    lemma simple_graph_stable_triangle_not_in_maximum_packing_example_P3_pw :
        (simple_graph_stable_triangle_not_in_maximum_packing_example_P3 : Set (Finset (Fin 5))).Pairwise
          (fun a b => (a ∩ b).card ≤ 1) := by decide
    
    lemma simple_graph_stable_triangle_not_in_maximum_packing_example_P4_pw :
        (simple_graph_stable_triangle_not_in_maximum_packing_example_P4 : Set (Finset (Fin 5))).Pairwise
          (fun a b => (a ∩ b).card ≤ 1) := by decide
    
    lemma simple_graph_stable_triangle_not_in_maximum_packing_example_P0_card :
        simple_graph_stable_triangle_not_in_maximum_packing_example_P0.card = 2 := by decide
    
    lemma simple_graph_stable_triangle_not_in_maximum_packing_example_P3_card :
        simple_graph_stable_triangle_not_in_maximum_packing_example_P3.card = 2 := by decide
    
    lemma simple_graph_stable_triangle_not_in_maximum_packing_example_P4_card :
        simple_graph_stable_triangle_not_in_maximum_packing_example_P4.card = 2 := by decide
    
    lemma simple_graph_stable_triangle_not_in_maximum_packing_example_P0_clique :
        ∀ t ∈ simple_graph_stable_triangle_not_in_maximum_packing_example_P0,
          simple_graph_stable_triangle_not_in_maximum_packing_example_G.IsNClique 3 t := by decide
    
  3. If a pairwise edge-disjoint collection T of 3-sets has cardinality greater than 2, it contains three distinct elements a, b, c.

    Assuming for contradiction that |T| > 2, we repeatedly extract distinct non-empty elements using `Finset.card_pos.mp` and `Finset.card_erase_of_mem` to obtain three distinct 3-sets a, b, c ∈ T that pairwise intersect in at most one element.

    lines 46–68

    uses Finset.card_pos.mp, Finset.card_erase_of_mem, Finset.mem_erase

      by_contra! h
      have h1 : 0 < T.card := by omega
      obtain ⟨a, ha⟩ := Finset.card_pos.mp h1
      have h2 : 0 < (T.erase a).card := by
        rw [Finset.card_erase_of_mem ha]
        omega
      obtain ⟨b, hb⟩ := Finset.card_pos.mp h2
      have hbe : b ∈ T.erase a := hb
      rw [Finset.mem_erase] at hb
      have h3' : 0 < ((T.erase a).erase b).card := by
        rw [Finset.card_erase_of_mem hbe, Finset.card_erase_of_mem ha]
        omega
      obtain ⟨c, hc⟩ := Finset.card_pos.mp h3'
      rw [Finset.mem_erase, Finset.mem_erase] at hc
      have hab_ne : a ≠ b := hb.1.symm
      have hac_ne : a ≠ c := hc.2.1.symm
      have hbc_ne : b ≠ c := hc.1.symm
      have ha_in : a ∈ T := ha
      have hb_in : b ∈ T := hb.2
      have hc_in : c ∈ T := hc.2.2
      have ha3 : a.card = 3 := h3 a ha_in
      have hb3 : b.card = 3 := h3 b hb_in
      have hc3 : c.card = 3 := h3 c hc_in
  4. The union a ∪ b covers the entire 5-element universe V.

    By inclusion-exclusion (`card_union_add_card_inter`), |a ∪ b| = |a| + |b| - |a ∩ b| = 3 + 3 - |a ∩ b| ≥ 5. Since |V| ≤ 5, the union must have cardinality equal to |V|, and `Finset.eq_univ_of_card` establishes that a ∪ b = Finset.univ.

    lines 69–76

    uses card_union_add_card_inter, Finset.card_le_univ, Finset.eq_univ_of_card

      have hab_pw : (a ∩ b).card ≤ 1 := hpw ha_in hb_in hab_ne
      have hac_pw : (a ∩ c).card ≤ 1 := hpw ha_in hc_in hac_ne
      have hbc_pw : (b ∩ c).card ≤ 1 := hpw hb_in hc_in hbc_ne
      have hub : (a ∪ b).card = a.card + b.card - (a ∩ b).card := card_union_add_card_inter a b ▸ by omega
      have hub_univ_le : (a ∪ b).card ≤ Fintype.card V := Finset.card_le_univ (a ∪ b)
      have hub_univ : a ∪ b = Finset.univ := by
        apply Finset.eq_univ_of_card
        omega
  5. Any pairwise edge-disjoint collection of 3-sets on at most 5 vertices has size at most 2.

    Since a ∪ b is the entire universe, the third 3-set c satisfies c ⊆ a ∪ b, meaning c = (c ∩ a) ∪ (c ∩ b). Its cardinality is thus bounded by |a ∩ c| + |b ∩ c| ≤ 1 + 1 = 2, contradicting |c| = 3. Linear arithmetic (`omega`) closes the goal with False.

    lines 77–87

    uses Finset.subset_univ, inter_union_distrib_left, Finset.inter_eq_left.mpr, Finset.card_union_le, Finset.inter_comm

      have hc_sub : c ⊆ a ∪ b := by
        rw [hub_univ]
        exact Finset.subset_univ c
      have hc_eq : c = (c ∩ a) ∪ (c ∩ b) := by
        rw [← inter_union_distrib_left]
        exact (Finset.inter_eq_left.mpr hc_sub).symm
      have hc_card_le : c.card ≤ (c ∩ a).card + (c ∩ b).card := by
        conv_lhs => rw [hc_eq]
        exact Finset.card_union_le (c ∩ a) (c ∩ b)
      rw [Finset.inter_comm c a, Finset.inter_comm c b] at hc_card_le
      omega
  6. Any graph on 5 vertices containing an edge-disjoint triangle packing of size 2 has triangle packing number 2.

    The triangle packing number is defined as the supremum of packing cardinalities. The packing T₀ achieves size 2, while `simple_graph_stable_triangle_not_in_maximum_packing_example_fin5_packing_card_le_two` bounds any packing size by 2, so 2 is the greatest element and equals the supremum by `IsGreatest.csSup_eq`.

    lines 96–103

    uses IsGreatest.csSup_eq, simple_graph_stable_triangle_not_in_maximum_packing_example_fin5_packing_card_le_two

      unfold simple_graph_triangle_packing_number
      apply IsGreatest.csSup_eq
      constructor
      · exact ⟨T₀, hT₀_clique, hT₀_pw, hT₀_card⟩
      · rintro n ⟨T, hT_clique, hT_pw, rfl⟩
        apply simple_graph_stable_triangle_not_in_maximum_packing_example_fin5_packing_card_le_two
          (by simp) T (fun t ht => (hT_clique t ht).2) hT_pw
    
  7. Deleting any edge e of G leaves all triangles of at least one of P₀, P₃, P₄ intact. automation

    Exhaustive finite computation (`decide`) over all 9 edges of G checks that for each edge e, at least one of P₀, P₃, or P₄ contains no triangle containing e.

    lines 113–122

    lemma simple_graph_stable_triangle_not_in_maximum_packing_example_check_all_edges :
        ∀ e ∈ simple_graph_stable_triangle_not_in_maximum_packing_example_G.edgeFinset,
          (∀ t ∈ simple_graph_stable_triangle_not_in_maximum_packing_example_P0,
            (simple_graph_stable_triangle_not_in_maximum_packing_example_G.deleteEdges {e}).IsNClique 3 t) ∨
          (∀ t ∈ simple_graph_stable_triangle_not_in_maximum_packing_example_P3,
            (simple_graph_stable_triangle_not_in_maximum_packing_example_G.deleteEdges {e}).IsNClique 3 t) ∨
          (∀ t ∈ simple_graph_stable_triangle_not_in_maximum_packing_example_P4,
            (simple_graph_stable_triangle_not_in_maximum_packing_example_G.deleteEdges {e}).IsNClique 3 t) := by
      decide
    
  8. Deleting any edge from G preserves its triangle packing number: ν(G \ {e}) = ν(G) = 2.

    By `simple_graph_stable_triangle_not_in_maximum_packing_example_check_all_edges`, at least one of the 2-element packings P₀, P₃, P₄ survives intact in G \ {e}. Applying `simple_graph_stable_triangle_not_in_maximum_packing_example_packing_number_eq_two` to the surviving packing yields ν(G \ {e}) = 2, which matches ν(G).

    lines 128–142

    uses SimpleGraph.mem_edgeFinset, simple_graph_stable_triangle_not_in_maximum_packing_example_check_all_edges, simple_graph_stable_triangle_not_in_maximum_packing_example_G_packing_number, simple_graph_stable_triangle_not_in_maximum_packing_example_packing_number_eq_two, simple_graph_stable_triangle_not_in_maximum_packing_example_P0_pw, simple_graph_stable_triangle_not_in_maximum_packing_example_P0_card, simple_graph_stable_triangle_not_in_maximum_packing_example_P3_pw, simple_graph_stable_triangle_not_in_maximum_packing_example_P3_card, simple_graph_stable_triangle_not_in_maximum_packing_example_P4_pw, simple_graph_stable_triangle_not_in_maximum_packing_example_P4_card

      have he_fin : e ∈ simple_graph_stable_triangle_not_in_maximum_packing_example_G.edgeFinset := by
        rw [SimpleGraph.mem_edgeFinset]
        exact he
      have h_cases := simple_graph_stable_triangle_not_in_maximum_packing_example_check_all_edges e he_fin
      rw [simple_graph_stable_triangle_not_in_maximum_packing_example_G_packing_number]
      rcases h_cases with h0 | h3 | h4
      · exact simple_graph_stable_triangle_not_in_maximum_packing_example_packing_number_eq_two _ _ h0
          simple_graph_stable_triangle_not_in_maximum_packing_example_P0_pw
          simple_graph_stable_triangle_not_in_maximum_packing_example_P0_card
      · exact simple_graph_stable_triangle_not_in_maximum_packing_example_packing_number_eq_two _ _ h3
          simple_graph_stable_triangle_not_in_maximum_packing_example_P3_pw
          simple_graph_stable_triangle_not_in_maximum_packing_example_P3_card
      · exact simple_graph_stable_triangle_not_in_maximum_packing_example_packing_number_eq_two _ _ h4
          simple_graph_stable_triangle_not_in_maximum_packing_example_P4_pw
          simple_graph_stable_triangle_not_in_maximum_packing_example_P4_card
  9. The set t = {1, 3, 4} is a triangle in G. automation

    Verified by finite evaluation (`decide`), checking that all pairs in {1, 3, 4} are edges of G.

    lines 146–150

    lemma simple_graph_stable_triangle_not_in_maximum_packing_example_t_clique :
        simple_graph_stable_triangle_not_in_maximum_packing_example_G.IsNClique 3
          simple_graph_stable_triangle_not_in_maximum_packing_example_t := by
      decide
    
  10. No 3-element subset sharing at most one vertex with t = {1, 3, 4} is a clique in G. automation

    Verified by computation (`decide`): any 3-element subset that shares at most one vertex with {1, 3, 4} must contain both 0 and 2, but the edge {0, 2} is absent in G.

    lines 151–156

    lemma simple_graph_stable_triangle_not_in_maximum_packing_example_t_no_compatible :
        ∀ s ∈ powersetCard 3 (univ : Finset (Fin 5)),
          (simple_graph_stable_triangle_not_in_maximum_packing_example_t ∩ s).card ≤ 1 →
          ¬ simple_graph_stable_triangle_not_in_maximum_packing_example_G.IsClique (s : Set (Fin 5)) := by
      decide
    
  11. Instantiate the existential witnesses with G, ν(G) = 2, stability under edge deletion, and triangle t.

    The `refine` tactic provides the graph G, along with the proofs that ν(G) = 2, ν(G \ {e}) = ν(G), and that t is a triangle in G, leaving the remaining obligation to prove that t belongs to no maximum packing of G.

    lines 168–172

    uses simple_graph_stable_triangle_not_in_maximum_packing_example_G_packing_number, simple_graph_stable_triangle_not_in_maximum_packing_example_delete_edges_packing_number, simple_graph_stable_triangle_not_in_maximum_packing_example_t_clique

      refine ⟨simple_graph_stable_triangle_not_in_maximum_packing_example_G,
        simple_graph_stable_triangle_not_in_maximum_packing_example_G_packing_number,
        simple_graph_stable_triangle_not_in_maximum_packing_example_delete_edges_packing_number,
        simple_graph_stable_triangle_not_in_maximum_packing_example_t,
        simple_graph_stable_triangle_not_in_maximum_packing_example_t_clique, ?_⟩
  12. The triangle t belongs to no maximum triangle packing of G.

    Suppose for contradiction that t ∈ P for a maximum packing P (so |P| = 2). Erasing t from P leaves a single triangle s ∈ P \ {t} with |t ∩ s| ≤ 1. But by `simple_graph_stable_triangle_not_in_maximum_packing_example_t_no_compatible`, no 3-clique in G shares at most 1 vertex with t, giving a contradiction.

    lines 173–191

    uses simple_graph_stable_triangle_not_in_maximum_packing_example_G_packing_number, Finset.card_erase_of_mem, Finset.card_eq_one.mp, Finset.mem_singleton_self, Finset.mem_erase, mem_powersetCard, subset_univ, Ne.symm, simple_graph_stable_triangle_not_in_maximum_packing_example_t_no_compatible

      intro P hP_clique hP_pw hP_card ht_in
      rw [simple_graph_stable_triangle_not_in_maximum_packing_example_G_packing_number] at hP_card
      have h_erase : (P.erase simple_graph_stable_triangle_not_in_maximum_packing_example_t).card = 1 := by
        rw [Finset.card_erase_of_mem ht_in, hP_card]
      obtain ⟨s, hs⟩ := Finset.card_eq_one.mp h_erase
      have hs_in_erase : s ∈ P.erase simple_graph_stable_triangle_not_in_maximum_packing_example_t :=
        hs ▸ Finset.mem_singleton_self s
      rw [Finset.mem_erase] at hs_in_erase
      have hs_ne : s ≠ simple_graph_stable_triangle_not_in_maximum_packing_example_t := hs_in_erase.1
      have hs_in : s ∈ P := hs_in_erase.2
      have hs_nclique := hP_clique s hs_in
      have hs_mem_powerset : s ∈ powersetCard 3 (univ : Finset (Fin 5)) := by
        rw [mem_powersetCard]
        exact ⟨subset_univ s, hs_nclique.2⟩
      have hs_pw : (simple_graph_stable_triangle_not_in_maximum_packing_example_t ∩ s).card ≤ 1 :=
        hP_pw ht_in hs_in (Ne.symm hs_ne)
      have hs_not_clique :=
        simple_graph_stable_triangle_not_in_maximum_packing_example_t_no_compatible s hs_mem_powerset hs_pw
      exact hs_not_clique hs_nclique.1
card_union_add_card_inter
For finite sets s and t, |s ∪ t| + |s ∩ t| = |s| + |t|.
Finset.card_erase_of_mem
Removing an element of a finite set decreases its cardinality by one.
Finset.card_eq_one.mp
A finite set has cardinality 1 if and only if it is a singleton {a}.
Finset.card_le_univ
A finite set has cardinality at most the cardinality of the full universe.
Finset.card_pos.mp
A finite set has strictly positive cardinality if and only if it is nonempty.
Finset.card_union_le
The cardinality of a union is at most the sum of cardinalities: |s ∪ t| ≤ |s| + |t|.
Finset.eq_univ_of_card
A subset of a finite type whose cardinality equals the cardinality of the type is the full universe.
Finset.inter_comm
Set intersection is commutative: s ∩ t = t ∩ s.
Finset.inter_eq_left.mpr
If s ⊆ t, then s ∩ t = s.
Finset.mem_erase
An element belongs to s \ {b} if and only if it belongs to s and is distinct from b.
Finset.mem_singleton_self
An element belongs to its own singleton set: a ∈ {a}.
Finset.subset_univ
Every subset of a finite type is contained in the universal set.
inter_union_distrib_left
Intersection distributes over union: s ∩ (t ∪ u) = (s ∩ t) ∪ (s ∩ u).
IsGreatest.csSup_eq
If an element is the greatest element of a set, it is the supremum of that set.
mem_powersetCard
A subset belongs to the collection of subsets of size n if and only if it is a subset and has cardinality n.
Ne.symm
Inequality is symmetric: if a ≠ b then b ≠ a.
SimpleGraph.mem_edgeFinset
An edge belongs to the edge finset of a simple graph if and only if it belongs to the edge set.
simple_graph_stable_triangle_not_in_maximum_packing_example_check_all_edges
For every edge e of G, all triangles in at least one of the three candidate packings P₀, P₃, P₄ survive in G \ {e}.
simple_graph_stable_triangle_not_in_maximum_packing_example_delete_edges_packing_number
Deleting any edge from G leaves the triangle packing number unchanged at 2.
simple_graph_stable_triangle_not_in_maximum_packing_example_fin5_packing_card_le_two
Any pairwise edge-disjoint collection of 3-element subsets of a set with at most 5 elements has cardinality at most 2.
simple_graph_stable_triangle_not_in_maximum_packing_example_G_packing_number
The triangle packing number of G is 2.
simple_graph_stable_triangle_not_in_maximum_packing_example_packing_number_eq_two
If a 5-vertex graph contains an edge-disjoint triangle packing of size 2, its triangle packing number is 2.
simple_graph_stable_triangle_not_in_maximum_packing_example_P0_card
The triangles in candidate packing P₀ pairwise share at most one vertex.
simple_graph_stable_triangle_not_in_maximum_packing_example_P0_pw
The candidate packing P₀ contains exactly 2 triangles.
simple_graph_stable_triangle_not_in_maximum_packing_example_P3_card
The candidate packing P₃ contains exactly 2 triangles.
simple_graph_stable_triangle_not_in_maximum_packing_example_P3_pw
The triangles in candidate packing P₃ pairwise share at most one vertex.
simple_graph_stable_triangle_not_in_maximum_packing_example_P4_card
The candidate packing P₄ contains exactly 2 triangles.
simple_graph_stable_triangle_not_in_maximum_packing_example_P4_pw
The triangles in candidate packing P₄ pairwise share at most one vertex.
simple_graph_stable_triangle_not_in_maximum_packing_example_t_clique
The set t = {1, 3, 4} forms a 3-clique (triangle) in G.
simple_graph_stable_triangle_not_in_maximum_packing_example_t_no_compatible
No 3-element subset sharing at most one vertex with t = {1, 3, 4} forms a clique in G.
subset_univ
Every set is a subset of the universal set univ.

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 Finsetdef simple_graph_stable_triangle_not_in_maximum_packing_example_G : SimpleGraph (Fin 5) where  Adj u v := u ≠ v ∧ ¬((u = 0 ∧ v = 2) ∨ (u = 2 ∧ v = 0))instance : DecidableRel simple_graph_stable_triangle_not_in_maximum_packing_example_G.Adj := by  intro u v; dsimp [simple_graph_stable_triangle_not_in_maximum_packing_example_G]; infer_instancedef simple_graph_stable_triangle_not_in_maximum_packing_example_P0 : Finset (Finset (Fin 5)) :=  { {0, 1, 3}, {1, 2, 4} }def simple_graph_stable_triangle_not_in_maximum_packing_example_P3 : Finset (Finset (Fin 5)) :=  { {0, 1, 4}, {2, 3, 4} }def simple_graph_stable_triangle_not_in_maximum_packing_example_P4 : Finset (Finset (Fin 5)) :=  { {0, 3, 4}, {1, 2, 3} }lemma simple_graph_stable_triangle_not_in_maximum_packing_example_P0_pw :    (simple_graph_stable_triangle_not_in_maximum_packing_example_P0 : Set (Finset (Fin 5))).Pairwise      (fun a b => (a ∩ b).card ≤ 1) := by decidelemma simple_graph_stable_triangle_not_in_maximum_packing_example_P3_pw :    (simple_graph_stable_triangle_not_in_maximum_packing_example_P3 : Set (Finset (Fin 5))).Pairwise      (fun a b => (a ∩ b).card ≤ 1) := by decidelemma simple_graph_stable_triangle_not_in_maximum_packing_example_P4_pw :    (simple_graph_stable_triangle_not_in_maximum_packing_example_P4 : Set (Finset (Fin 5))).Pairwise      (fun a b => (a ∩ b).card ≤ 1) := by decidelemma simple_graph_stable_triangle_not_in_maximum_packing_example_P0_card :    simple_graph_stable_triangle_not_in_maximum_packing_example_P0.card = 2 := by decidelemma simple_graph_stable_triangle_not_in_maximum_packing_example_P3_card :    simple_graph_stable_triangle_not_in_maximum_packing_example_P3.card = 2 := by decidelemma simple_graph_stable_triangle_not_in_maximum_packing_example_P4_card :    simple_graph_stable_triangle_not_in_maximum_packing_example_P4.card = 2 := by decidelemma simple_graph_stable_triangle_not_in_maximum_packing_example_P0_clique :    ∀ t ∈ simple_graph_stable_triangle_not_in_maximum_packing_example_P0,      simple_graph_stable_triangle_not_in_maximum_packing_example_G.IsNClique 3 t := by decidetheorem simple_graph_stable_triangle_not_in_maximum_packing_example_fin5_packing_card_le_two    {V : Type*} [Fintype V] [DecidableEq V] (hV : Fintype.card V ≤ 5)    (T : Finset (Finset V)) (h3 : ∀ t ∈ T, t.card = 3)    (hpw : (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1)) :    T.card ≤ 2 := by  by_contra! h  have h1 : 0 < T.card := by omega  obtain ⟨a, ha⟩ := Finset.card_pos.mp h1  have h2 : 0 < (T.erase a).card := by    rw [Finset.card_erase_of_mem ha]    omega  obtain ⟨b, hb⟩ := Finset.card_pos.mp h2  have hbe : b ∈ T.erase a := hb  rw [Finset.mem_erase] at hb  have h3' : 0 < ((T.erase a).erase b).card := by    rw [Finset.card_erase_of_mem hbe, Finset.card_erase_of_mem ha]    omega  obtain ⟨c, hc⟩ := Finset.card_pos.mp h3'  rw [Finset.mem_erase, Finset.mem_erase] at hc  have hab_ne : a ≠ b := hb.1.symm  have hac_ne : a ≠ c := hc.2.1.symm  have hbc_ne : b ≠ c := hc.1.symm  have ha_in : a ∈ T := ha  have hb_in : b ∈ T := hb.2  have hc_in : c ∈ T := hc.2.2  have ha3 : a.card = 3 := h3 a ha_in  have hb3 : b.card = 3 := h3 b hb_in  have hc3 : c.card = 3 := h3 c hc_in  have hab_pw : (a ∩ b).card ≤ 1 := hpw ha_in hb_in hab_ne  have hac_pw : (a ∩ c).card ≤ 1 := hpw ha_in hc_in hac_ne  have hbc_pw : (b ∩ c).card ≤ 1 := hpw hb_in hc_in hbc_ne  have hub : (a ∪ b).card = a.card + b.card - (a ∩ b).card := card_union_add_card_inter a b ▸ by omega  have hub_univ_le : (a ∪ b).card ≤ Fintype.card V := Finset.card_le_univ (a ∪ b)  have hub_univ : a ∪ b = Finset.univ := by    apply Finset.eq_univ_of_card    omega  have hc_sub : c ⊆ a ∪ b := by    rw [hub_univ]    exact Finset.subset_univ c  have hc_eq : c = (c ∩ a) ∪ (c ∩ b) := by    rw [← inter_union_distrib_left]    exact (Finset.inter_eq_left.mpr hc_sub).symm  have hc_card_le : c.card ≤ (c ∩ a).card + (c ∩ b).card := by    conv_lhs => rw [hc_eq]    exact Finset.card_union_le (c ∩ a) (c ∩ b)  rw [Finset.inter_comm c a, Finset.inter_comm c b] at hc_card_le  omegatheorem simple_graph_stable_triangle_not_in_maximum_packing_example_packing_number_eq_two    (H : SimpleGraph (Fin 5))    (T₀ : Finset (Finset (Fin 5)))    (hT₀_clique : ∀ t ∈ T₀, H.IsNClique 3 t)    (hT₀_pw : (T₀ : Set (Finset (Fin 5))).Pairwise (fun s t => (s ∩ t).card ≤ 1))    (hT₀_card : T₀.card = 2) :    simple_graph_triangle_packing_number H = 2 := by  unfold simple_graph_triangle_packing_number  apply IsGreatest.csSup_eq  constructor  · exact ⟨T₀, hT₀_clique, hT₀_pw, hT₀_card⟩  · rintro n ⟨T, hT_clique, hT_pw, rfl⟩    apply simple_graph_stable_triangle_not_in_maximum_packing_example_fin5_packing_card_le_two      (by simp) T (fun t ht => (hT_clique t ht).2) hT_pwlemma simple_graph_stable_triangle_not_in_maximum_packing_example_G_packing_number :    simple_graph_triangle_packing_number simple_graph_stable_triangle_not_in_maximum_packing_example_G = 2 :=  simple_graph_stable_triangle_not_in_maximum_packing_example_packing_number_eq_two    simple_graph_stable_triangle_not_in_maximum_packing_example_G    simple_graph_stable_triangle_not_in_maximum_packing_example_P0    simple_graph_stable_triangle_not_in_maximum_packing_example_P0_clique    simple_graph_stable_triangle_not_in_maximum_packing_example_P0_pw    simple_graph_stable_triangle_not_in_maximum_packing_example_P0_cardlemma simple_graph_stable_triangle_not_in_maximum_packing_example_check_all_edges :    ∀ e ∈ simple_graph_stable_triangle_not_in_maximum_packing_example_G.edgeFinset,      (∀ t ∈ simple_graph_stable_triangle_not_in_maximum_packing_example_P0,        (simple_graph_stable_triangle_not_in_maximum_packing_example_G.deleteEdges {e}).IsNClique 3 t) ∨      (∀ t ∈ simple_graph_stable_triangle_not_in_maximum_packing_example_P3,        (simple_graph_stable_triangle_not_in_maximum_packing_example_G.deleteEdges {e}).IsNClique 3 t) ∨      (∀ t ∈ simple_graph_stable_triangle_not_in_maximum_packing_example_P4,        (simple_graph_stable_triangle_not_in_maximum_packing_example_G.deleteEdges {e}).IsNClique 3 t) := by  decidelemma simple_graph_stable_triangle_not_in_maximum_packing_example_delete_edges_packing_number    (e : Sym2 (Fin 5)) (he : e ∈ simple_graph_stable_triangle_not_in_maximum_packing_example_G.edgeSet) :    simple_graph_triangle_packing_number      (simple_graph_stable_triangle_not_in_maximum_packing_example_G.deleteEdges {e}) =      simple_graph_triangle_packing_number simple_graph_stable_triangle_not_in_maximum_packing_example_G := by  have he_fin : e ∈ simple_graph_stable_triangle_not_in_maximum_packing_example_G.edgeFinset := by    rw [SimpleGraph.mem_edgeFinset]    exact he  have h_cases := simple_graph_stable_triangle_not_in_maximum_packing_example_check_all_edges e he_fin  rw [simple_graph_stable_triangle_not_in_maximum_packing_example_G_packing_number]  rcases h_cases with h0 | h3 | h4  · exact simple_graph_stable_triangle_not_in_maximum_packing_example_packing_number_eq_two _ _ h0      simple_graph_stable_triangle_not_in_maximum_packing_example_P0_pw      simple_graph_stable_triangle_not_in_maximum_packing_example_P0_card  · exact simple_graph_stable_triangle_not_in_maximum_packing_example_packing_number_eq_two _ _ h3      simple_graph_stable_triangle_not_in_maximum_packing_example_P3_pw      simple_graph_stable_triangle_not_in_maximum_packing_example_P3_card  · exact simple_graph_stable_triangle_not_in_maximum_packing_example_packing_number_eq_two _ _ h4      simple_graph_stable_triangle_not_in_maximum_packing_example_P4_pw      simple_graph_stable_triangle_not_in_maximum_packing_example_P4_carddef simple_graph_stable_triangle_not_in_maximum_packing_example_t : Finset (Fin 5) := {1, 3, 4}lemma simple_graph_stable_triangle_not_in_maximum_packing_example_t_clique :    simple_graph_stable_triangle_not_in_maximum_packing_example_G.IsNClique 3      simple_graph_stable_triangle_not_in_maximum_packing_example_t := by  decidelemma simple_graph_stable_triangle_not_in_maximum_packing_example_t_no_compatible :    ∀ s ∈ powersetCard 3 (univ : Finset (Fin 5)),      (simple_graph_stable_triangle_not_in_maximum_packing_example_t ∩ s).card ≤ 1 →      ¬ simple_graph_stable_triangle_not_in_maximum_packing_example_G.IsClique (s : Set (Fin 5)) := by  decidetheorem simple_graph_stable_triangle_not_in_maximum_packing_example :    ∃ G : SimpleGraph (Fin 5),      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 : Finset (Fin 5), G.IsNClique 3 t ∧        ∀ P : Finset (Finset (Fin 5)),          (∀ s ∈ P, G.IsNClique 3 s) →          (P : Set (Finset (Fin 5))).Pairwise (fun a b => (a ∩ b).card ≤ 1) →          P.card = simple_graph_triangle_packing_number G → t ∉ P := by  refine ⟨simple_graph_stable_triangle_not_in_maximum_packing_example_G,    simple_graph_stable_triangle_not_in_maximum_packing_example_G_packing_number,    simple_graph_stable_triangle_not_in_maximum_packing_example_delete_edges_packing_number,    simple_graph_stable_triangle_not_in_maximum_packing_example_t,    simple_graph_stable_triangle_not_in_maximum_packing_example_t_clique, ?_⟩  intro P hP_clique hP_pw hP_card ht_in  rw [simple_graph_stable_triangle_not_in_maximum_packing_example_G_packing_number] at hP_card  have h_erase : (P.erase simple_graph_stable_triangle_not_in_maximum_packing_example_t).card = 1 := by    rw [Finset.card_erase_of_mem ht_in, hP_card]  obtain ⟨s, hs⟩ := Finset.card_eq_one.mp h_erase  have hs_in_erase : s ∈ P.erase simple_graph_stable_triangle_not_in_maximum_packing_example_t :=    hs ▸ Finset.mem_singleton_self s  rw [Finset.mem_erase] at hs_in_erase  have hs_ne : s ≠ simple_graph_stable_triangle_not_in_maximum_packing_example_t := hs_in_erase.1  have hs_in : s ∈ P := hs_in_erase.2  have hs_nclique := hP_clique s hs_in  have hs_mem_powerset : s ∈ powersetCard 3 (univ : Finset (Fin 5)) := by    rw [mem_powersetCard]    exact ⟨subset_univ s, hs_nclique.2⟩  have hs_pw : (simple_graph_stable_triangle_not_in_maximum_packing_example_t ∩ s).card ≤ 1 :=    hP_pw ht_in hs_in (Ne.symm hs_ne)  have hs_not_clique :=    simple_graph_stable_triangle_not_in_maximum_packing_example_t_no_compatible s hs_mem_powerset hs_pw  exact hs_not_clique hs_nclique.1
See it in the graphDiscuss this resultChallenge it