simple_graph_unrestricted_singleton_witness_edge_union_counterexample
The unrestricted witness-edge union does not satisfy the proposed sunflower forced-base half-independence statement: the explicitly quantified statement with that formula has a five-vertex counterexample.
Statement
theorem simple_graph_unrestricted_singleton_witness_edge_union_counterexample : ¬ (∀ (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (P : Finset (Finset (Fin n))) (r : Fin n) (F : Finset (Sym2 (Fin n))) (htri : ∀ t ∈ P, G.IsNClique 3 t) (hdisj : (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hmax : P.card = simple_graph_triangle_packing_number G) (hroot : ∀ t ∈ P, r ∈ t) (hgood : ∀ p ∈ P, (finite_vertex_set_edge_encoding p ∩ (((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)).card ≤ 1) (hF : F = ((((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id).filter (fun e => r ∉ e.toFinset))), ∃ Z : Finset (Fin n), Z ⊆ F.biUnion Sym2.toFinset ∧ F.card ≤ Z.card ∧ ∀ u ∈ Z, ∀ v ∈ Z, G.Adj u v → s(u,v) ∈ F)
- Source
- Counterexample to a misformulated sunflower helper in the triangle-packing campaign; experiment 20269.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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).
- simple_graph_triangle_edge_familyThe family of three-edge sets of all triangles of a finite simple graph.
- finite_vertex_set_edge_encodingThe non-diagonal unordered vertex pairs spanned by a finite vertex set.
The proof, explained
The theorem is disproved by constructing an explicit 5-vertex counterexample known as a book graph, consisting of 3 triangles sharing a single common edge {1, 2}. Taking the maximum triangle packing P to consist of the single triangle {0, 1, 2} rooted at vertex 0, all premises of the proposed statement are satisfied. However, the resulting set F of witness edges not containing the root has size 5 but spans only 4 vertices {1, 2, 3, 4}, making it impossible to find any vertex subset Z ⊆ V(F) with |Z| ≥ |F|.
The adjacency relation of the 5-vertex graph is symmetric.
An undirected edge s(u, v) is identical to s(v, u) by Sym2.eq_swap, so adjacency between u and v is symmetric.
uses
Sym2.eq_swapsymm := ⟨fun u v h => ⟨by rw [Sym2.eq_swap]; exact h.1, h.2.symm⟩⟩
The triangles in the 5-vertex graph are precisely {0,1,2}, {1,2,3}, and {1,2,4}. automation
By exhaustive kernel evaluation, the 3-cliques of the graph are exactly the three triangles in in693_book_T, all of which share the edge {1,2}.
lemma in693_book_cliques : ∀ t : Finset (Fin 5), in693_book_G.IsNClique 3 t ↔ t ∈ in693_book_T := by decide +kernel
The triangle packing number of the 5-vertex graph is at least 1, witnessed by P = {{0,1,2}}. automation
We unfold the definition of triangle packing number and express it as a supremum using IsGreatest.csSup_eq. The candidate packing P = {{0,1,2}} is verified by kernel evaluation to consist of a triangle, have pairwise intersections of size at most 1, and have cardinality 1.
uses
IsGreatest.csSup_equnfold simple_graph_triangle_packing_number apply IsGreatest.csSup_eq constructor · refine ⟨in693_book_P, ?_, ?_, ?_⟩ <;> decide +kernel
The triangle packing number of the 5-vertex graph is at most 1, so it equals 1.
Any triangle packing T has all of its triangles in in693_book_T by in693_book_cliques. If T had size greater than 1, it would contain two distinct triangles a, b by Finset.one_lt_card.mp. But kernel evaluation confirms that every pair of distinct triangles in in693_book_T shares at least 2 vertices (the common edge {1,2}), contradicting the packing condition |a ∩ b| ≤ 1.
uses
in693_book_cliques,Finset.one_lt_card.mp· rintro n ⟨T, hT, hpw, rfl⟩ have hsub : T ⊆ in693_book_T := fun t ht => (in693_book_cliques t).1 (hT t ht) by_contra hc have htwo : 1 < T.card := by omega obtain ⟨a, ha, b, hb, hab⟩ := Finset.one_lt_card.mp htwo have hp := hpw ha hb hab have han : a ∈ in693_book_T := hsub ha have hbn : b ∈ in693_book_T := hsub hb have hcontra : ∀ a ∈ in693_book_T, ∀ b ∈ in693_book_T, a ≠ b → ¬ (a ∩ b).card ≤ 1 := by decide +kernel exact hcontra a han b hbn hab hp
The family of triangle edge sets in the graph is the edge encoding of the three triangles in in693_book_T.
Rewriting with the definition of triangle edge family, membership in the image, filtering for 3-cliques via in693_book_cliques, and universal set membership establishes that the triangle edge sets are precisely the edge encodings of the elements of in693_book_T.
uses
Finset.mem_image,Finset.mem_filter,Finset.mem_univ,true_and,in693_book_cliquesclassical ext x simp only [simple_graph_triangle_edge_family, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and, in693_book_cliques]
The packing P = {{0,1,2}} consists of triangles, is pairwise edge-disjoint, and contains the root vertex 0. automation
Kernel computation verifies that {0,1,2} is a 3-clique, that P is pairwise edge-disjoint (vacuously, since |P| = 1), and that the root vertex 0 belongs to {0,1,2}.
lemma in693_book_Pclique : ∀ t ∈ in693_book_P, in693_book_G.IsNClique 3 t := by decide +kernel lemma in693_book_Pdisj : (in693_book_P : Set (Finset (Fin 5))).Pairwise (fun t u => (t ∩ u).card ≤ 1) := by decide +kernel lemma in693_book_root : ∀ t ∈ in693_book_P, (0 : Fin 5) ∈ t := by decide +kernel
Each triangle in P shares at most one edge with the union of witness triangles. automation
Rewriting the triangle edge family via in693_book_family, kernel evaluation confirms that the single triangle in P shares only 1 edge (namely {1,2}) with the witness triangles (those sharing exactly 1 edge with P).
uses
in693_book_familyrw [in693_book_family] decide +kernel
No vertex subset Z contained in the vertices of F has size at least |F|. automation
After rewriting with in693_book_family, kernel evaluation verifies that no subset Z of the vertex span of F satisfies |F| ≤ |Z|, because F contains 5 edges spanning only 4 vertices ({1,2,3,4}).
uses
in693_book_familyrw [in693_book_family] decide +kernel
Assuming the statement for contradiction, define F and verify that P has maximum packing size. automation
We assume the universal statement for contradiction and instantiate F as the set of witness edges not containing 0. Rewriting with in693_book_packing and kernel evaluation verifies that |P| = 1 equals the triangle packing number.
uses
in693_book_packingintro h let F := (((simple_graph_triangle_edge_family in693_book_G).filter (fun t => (t ∩ in693_book_P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id).filter (fun e => (0 : Fin 5) ∉ e.toFinset) have hmax : in693_book_P.card = simple_graph_triangle_packing_number in693_book_G := by rw [in693_book_packing]; decide +kernel
Apply the assumed hypothesis to the counterexample graph and derive a contradiction.
We instantiate the universally quantified hypothesis with n = 5, the book graph, P = {{0,1,2}}, root vertex 0, and F, discharging the premises with in693_book_Pclique, in693_book_Pdisj, hmax, in693_book_root, and in693_book_good. This yields a vertex subset Z ⊆ V(F) with |F| ≤ |Z|, which directly contradicts in693_book_no_Z.
uses
in693_book_Pclique,in693_book_Pdisj,in693_book_root,in693_book_good,in693_book_no_Zobtain ⟨Z, hsub, hcard, _⟩ := h 5 in693_book_G in693_book_P 0 F in693_book_Pclique in693_book_Pdisj hmax in693_book_root in693_book_good rfl exact in693_book_no_Z ⟨Z, hsub, hcard⟩
Finset.one_lt_card.mp- A finite set with cardinality strictly greater than 1 contains at least two distinct elements.
Finset.mem_image- An element belongs to the image of a set under a function if and only if it is the value of the function at some element of the original set.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
IsGreatest.csSup_eq- If an element is the greatest element of a set in a conditionally complete lattice, it equals the supremum of that set.
Sym2.eq_swap- For any elements a and b, the unordered pair s(a, b) equals s(b, a).
in693_book_cliques- The triangles (3-cliques) in the 5-vertex book graph are precisely {0,1,2}, {1,2,3}, and {1,2,4}.
in693_book_packing- The triangle packing number of the 5-vertex book graph is 1.
in693_book_family- The collection of edge sets of triangles in the 5-vertex book graph is the image under edge encoding of the triangle family {{0,1,2}, {1,2,3}, {1,2,4}}.
in693_book_Pclique- Every element of P = {{0,1,2}} is a 3-clique in the 5-vertex book graph.
in693_book_Pdisj- The elements of P pairwise intersect in at most one vertex (they are edge-disjoint).
in693_book_root- Vertex 0 belongs to every triangle in P.
in693_book_good- Each triangle in P shares at most one edge with the union of witness triangles.
in693_book_no_Z- No subset of vertices Z contained in the vertices of F has size at least |F|.
true_and- For any proposition p, the conjunction True ∧ p is equivalent to p.
- Several finite combinatorial properties of the 5-vertex graph—including clique classification, packing feasibility, intersection bounds, and the nonexistence of Z—are proved by exhaustive kernel computation using `decide +kernel`.
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 scoped Sym2open Finsetdef in693_book_E : Finset (Sym2 (Fin 5)) := {s(0,1),s(0,2),s(1,2),s(1,3),s(2,3),s(1,4),s(2,4)}def in693_book_G : SimpleGraph (Fin 5) where Adj u v := s(u,v) ∈ in693_book_E ∧ u ≠ v symm := ⟨fun u v h => ⟨by rw [Sym2.eq_swap]; exact h.1, h.2.symm⟩⟩ loopless := ⟨fun u h => h.2 rfl⟩instance : DecidableRel in693_book_G.Adj := fun _ _ => inferInstanceAs (Decidable (_ ∈ in693_book_E ∧ _ ≠ _))def in693_book_P : Finset (Finset (Fin 5)) := {{0,1,2}}def in693_book_T : Finset (Finset (Fin 5)) := {{0,1,2},{1,2,3},{1,2,4}}lemma in693_book_cliques : ∀ t : Finset (Fin 5), in693_book_G.IsNClique 3 t ↔ t ∈ in693_book_T := by decide +kernellemma in693_book_packing : simple_graph_triangle_packing_number in693_book_G = 1 := by unfold simple_graph_triangle_packing_number apply IsGreatest.csSup_eq constructor · refine ⟨in693_book_P, ?_, ?_, ?_⟩ <;> decide +kernel · rintro n ⟨T, hT, hpw, rfl⟩ have hsub : T ⊆ in693_book_T := fun t ht => (in693_book_cliques t).1 (hT t ht) by_contra hc have htwo : 1 < T.card := by omega obtain ⟨a, ha, b, hb, hab⟩ := Finset.one_lt_card.mp htwo have hp := hpw ha hb hab have han : a ∈ in693_book_T := hsub ha have hbn : b ∈ in693_book_T := hsub hb have hcontra : ∀ a ∈ in693_book_T, ∀ b ∈ in693_book_T, a ≠ b → ¬ (a ∩ b).card ≤ 1 := by decide +kernel exact hcontra a han b hbn hab hplemma in693_book_family : simple_graph_triangle_edge_family in693_book_G = in693_book_T.image finite_vertex_set_edge_encoding := by classical ext x simp only [simple_graph_triangle_edge_family, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and, in693_book_cliques]lemma in693_book_Pclique : ∀ t ∈ in693_book_P, in693_book_G.IsNClique 3 t := by decide +kernellemma in693_book_Pdisj : (in693_book_P : Set (Finset (Fin 5))).Pairwise (fun t u => (t ∩ u).card ≤ 1) := by decide +kernellemma in693_book_root : ∀ t ∈ in693_book_P, (0 : Fin 5) ∈ t := by decide +kernellemma in693_book_good : ∀ p ∈ in693_book_P, (finite_vertex_set_edge_encoding p ∩ (((simple_graph_triangle_edge_family in693_book_G).filter (fun t => (t ∩ in693_book_P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)).card ≤ 1 := by rw [in693_book_family] decide +kernellemma in693_book_no_Z : ¬ ∃ Z : Finset (Fin 5), Z ⊆ (((((simple_graph_triangle_edge_family in693_book_G).filter (fun t => (t ∩ in693_book_P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id).filter (fun e => (0 : Fin 5) ∉ e.toFinset))).biUnion Sym2.toFinset ∧ (((((simple_graph_triangle_edge_family in693_book_G).filter (fun t => (t ∩ in693_book_P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id).filter (fun e => (0 : Fin 5) ∉ e.toFinset))).card ≤ Z.card := by rw [in693_book_family] decide +kerneltheorem simple_graph_unrestricted_singleton_witness_edge_union_counterexample : ¬ (∀ (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (P : Finset (Finset (Fin n))) (r : Fin n) (F : Finset (Sym2 (Fin n))) (htri : ∀ t ∈ P, G.IsNClique 3 t) (hdisj : (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hmax : P.card = simple_graph_triangle_packing_number G) (hroot : ∀ t ∈ P, r ∈ t) (hgood : ∀ p ∈ P, (finite_vertex_set_edge_encoding p ∩ (((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)).card ≤ 1) (hF : F = ((((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id).filter (fun e => r ∉ e.toFinset))), ∃ Z : Finset (Fin n), Z ⊆ F.biUnion Sym2.toFinset ∧ F.card ≤ Z.card ∧ ∀ u ∈ Z, ∀ v ∈ Z, G.Adj u v → s(u,v) ∈ F) := by intro h let F := (((simple_graph_triangle_edge_family in693_book_G).filter (fun t => (t ∩ in693_book_P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id).filter (fun e => (0 : Fin 5) ∉ e.toFinset) have hmax : in693_book_P.card = simple_graph_triangle_packing_number in693_book_G := by rw [in693_book_packing]; decide +kernel obtain ⟨Z, hsub, hcard, _⟩ := h 5 in693_book_G in693_book_P 0 F in693_book_Pclique in693_book_Pdisj hmax in693_book_root in693_book_good rfl exact in693_book_no_Z ⟨Z, hsub, hcard⟩