simple_graph_stable_two_packing_arbitrary_cover_counterexample
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
- 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).
- finite_vertex_set_edge_encodingThe non-diagonal unordered vertex pairs spanned by a finite vertex set.
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).
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.
symm := ⟨fun a b h => ⟨by simpa [Sym2.eq_swap] using h.1, h.2.symm⟩⟩ loopless := ⟨fun a => by simp⟩
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.
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
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.
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
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.
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
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.
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
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.
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)
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.
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⟩
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.
rw [finite_vertex_set_edge_encoding, Finset.mem_filter, Finset.mk_mem_sym2_iff, Sym2.mk_isDiag_iff] tauto
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.
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
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.
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
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.
· 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)
- Unresolved check: no step explains line(s) 150 -- every tactic of the proof has to belong to some step
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 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)