AFTD Auto-Formalizing Theoretical Domains

simple_graph_unrestricted_singleton_witness_edge_union_counterexample

theoremverified

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

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|.

  1. 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.

    line 7

    uses Sym2.eq_swap

      symm := ⟨fun u v h => ⟨by rw [Sym2.eq_swap]; exact h.1, h.2.symm⟩⟩
  2. 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}.

    line 12

    lemma in693_book_cliques : ∀ t : Finset (Fin 5), in693_book_G.IsNClique 3 t ↔ t ∈ in693_book_T := by decide +kernel
  3. 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.

    lines 14–17

    uses IsGreatest.csSup_eq

      unfold simple_graph_triangle_packing_number
      apply IsGreatest.csSup_eq
      constructor
      · refine ⟨in693_book_P, ?_, ?_, ?_⟩ <;> decide +kernel
  4. 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.

    lines 18–27

    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
  5. 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.

    lines 29–31

    uses Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and, in693_book_cliques

      classical
      ext x
      simp only [simple_graph_triangle_edge_family, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and, in693_book_cliques]
  6. 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}.

    lines 32–34

    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
  7. 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).

    lines 36–37

    uses in693_book_family

      rw [in693_book_family]
      decide +kernel
  8. 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}).

    lines 39–40

    uses in693_book_family

      rw [in693_book_family]
      decide +kernel
  9. 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.

    lines 43–45

    uses in693_book_packing

      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
  10. 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.

    lines 46–47

    uses in693_book_Pclique, in693_book_Pdisj, in693_book_root, in693_book_good, in693_book_no_Z

      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⟩
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.

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 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⟩
See it in the graphDiscuss this resultChallenge it