simple_graph_stable_triangle_not_in_maximum_packing_example
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
- simple_graph_triangle_packing_numberν(G): the maximum number of pairwise edge-disjoint triangles of G (two triangles are edge-disjoint when they share at most one vertex).
- Used by 1
- simple_graph_lex_cover_private_triangle_not_extendable_exampleThere is a stable graph with triangle packing number two, a maximum packing P, and a minimum triangle cover C minimizing its edges outside…
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.
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.
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
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.
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
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.
uses
Finset.card_pos.mp,Finset.card_erase_of_mem,Finset.mem_eraseby_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
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.
uses
card_union_add_card_inter,Finset.card_le_univ,Finset.eq_univ_of_cardhave 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
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.
uses
Finset.subset_univ,inter_union_distrib_left,Finset.inter_eq_left.mpr,Finset.card_union_le,Finset.inter_commhave 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
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`.
uses
IsGreatest.csSup_eq,simple_graph_stable_triangle_not_in_maximum_packing_example_fin5_packing_card_le_twounfold 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
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.
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
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).
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_cardhave 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
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.
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
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.
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
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.
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_cliquerefine ⟨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, ?_⟩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.
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_compatibleintro 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.
- Several helper lemmas (confirming that edge deletions preserve packings and that no triangle disjoint from t exists) are verified by computational reflection (`decide`), which checks all cases over the finite graph on 5 vertices.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open 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