simple_graph_maximum_packing_fixed_two_budget_counterexample
A nine-vertex graph has a maximum triangle packing with at most one singleton-forced edge per packed triangle, but no triangle cover formed by choosing exactly two edges from each packed triangle. It nevertheless has a six-edge cover supported by that packing.
Statement
theorem simple_graph_maximum_packing_fixed_two_budget_counterexample : (∀ t ∈ In701Budget.P, In701Budget.G.IsNClique 3 t) ∧ (In701Budget.P : Set (Finset (Fin 9))).Pairwise (fun a b => (a ∩ b).card ≤ 1) ∧ In701Budget.P.card = simple_graph_triangle_packing_number In701Budget.G ∧ (∀ p ∈ In701Budget.P, (finite_vertex_set_edge_encoding p ∩ (((simple_graph_triangle_edge_family In701Budget.G).filter (fun t => (t ∩ In701Budget.P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)).card ≤ 1) ∧ (∀ i : Fin 4, In701Budget.PI i ∈ In701Budget.P) ∧ Function.Injective In701Budget.PI ∧ (∀ i : Fin 4, ∀ j : Fin 3, (In701Budget.Choice i j).card = 2 ∧ In701Budget.Choice i j ⊆ finite_vertex_set_edge_encoding (In701Budget.PI i)) ∧ (∀ i : Fin 4, Function.Injective (In701Budget.Choice i)) ∧ (∀ f : Fin 4 → Fin 3, ∃ t : Finset (Fin 9), In701Budget.G.IsNClique 3 t ∧ Disjoint (finite_vertex_set_edge_encoding t) (In701Budget.Picks f)) ∧ (In701Budget.SmallCover.card = 6 ∧ In701Budget.SmallCover ⊆ In701Budget.P.biUnion finite_vertex_set_edge_encoding ∧ ∀ t : Finset (Fin 9), In701Budget.G.IsNClique 3 t → ¬ Disjoint (finite_vertex_set_edge_encoding t) In701Budget.SmallCover)
- Source
- Three four-cliques in a vertex cycle, extracted in experiments 20948 and 20962; see state/campaigns/triangle_reductions/k4_pivot_cover_in701.md. Related forced-triangle and packing-cover structure is in https://arxiv.org/abs/2001.00257, Section 3. Literature checked 2026-11-10.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- simple_graph_in693_ten_seed_packing_numberThe concrete ten-vertex five-link seed has triangle packing number eight.
- 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.
- 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).
The proof, explained
The theorem constructs an explicit 9-vertex, 18-edge graph G showing that a maximum triangle packing P of size ν(G) = 4 cannot always yield a triangle cover by picking two edges from each packed triangle, even when each packed triangle has at most one singleton-forced edge. Exhaustive kernel evaluation (decide +kernel) characterizes the 13 triangles of G, establishes ν(G) = 4 via a compatibility search, and shows that all 3⁴ = 81 selections of two edges per packed triangle leave some triangle uncovered. Finally, an explicit 6-edge triangle cover supported entirely on the edges of P is verified to intersect every triangle in G.
The graph G on 9 vertices is a well-defined simple graph with symmetric adjacency.
The graph G is defined with vertices {0, ..., 8} and edges from the 18-element list EL. Adjacency requires s(u, v) ∈ E and u ≠ v. Symmetry is proved by swapping the unordered pair (Sym2.eq_swap), and looplessness is immediate from u ≠ v.
uses
Sym2.eq_swapdef G : SimpleGraph (Fin 9) where Adj u v := s(u,v) ∈ 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 G.Adj := fun _ _ => inferInstanceAs (Decidable (_ ∈ E ∧ _ ≠ _))
The 3-cliques of G are precisely the 13 triples in T. automation
The kernel checks by exhaustive evaluation (decide +kernel) that every 3-clique in G is listed in T (tri_complete) and that every element of T is a 3-clique (T_clique). Lemma clique_mem packages that any 3-clique of G belongs to T.
theorem tri_complete : ∀ t ∈ (Finset.univ : Finset (Fin 9)).powersetCard 3, G.IsNClique 3 t → t ∈ T := by decide +kernel theorem T_clique : ∀ t ∈ T, G.IsNClique 3 t := by decide +kernel lemma clique_mem {t : Finset (Fin 9)} (h : G.IsNClique 3 t) : t ∈ T := tri_complete t (Finset.mem_powersetCard.mpr ⟨Finset.subset_univ _, h.card_eq⟩) h
Every edge-disjoint triangle packing in G has size at most 4. automation
Two triangles are edge-disjoint if and only if they share at most one vertex (compat). The kernel evaluates the compatibility search in693_maxC on T, finding maximum size 4 (maxC_eq). By in693_maxC_bound, any edge-disjoint triangle packing in G has size at most 4 (nu_le).
uses
in693_maxC_bound,maxC_eqdef compat (s t : Finset (Fin 9)) : Bool := decide ((s ∩ t).card ≤ 1) theorem maxC_eq : in693_maxC compat T.length T = 4 := by decide +kernel lemma nu_le (U : Finset (Finset (Fin 9))) (hU : ∀ t ∈ U, G.IsNClique 3 t) (hP : (U : Set (Finset (Fin 9))).Pairwise (fun a b => (a ∩ b).card ≤ 1)) : U.card ≤ 4 := calc U.card ≤ in693_maxC compat T.length T := in693_maxC_bound compat _ T le_rfl U (fun a ha => clique_mem (hU a ha)) (fun a ha b hb hab => decide_eq_true (hP (Finset.mem_coe.mpr ha) (Finset.mem_coe.mpr hb) hab)) _ = 4 := maxC_eq
P is an edge-disjoint triangle packing of size 4. automation
The kernel verifies (decide +kernel) that the 4 triples in P are 3-cliques (P_clique), pairwise share at most one vertex (P_pw), and that |P| = 4 (P_card).
theorem P_clique : ∀ t ∈ P, G.IsNClique 3 t := by decide +kernel theorem P_pw : (P : Set (Finset (Fin 9))).Pairwise (fun a b => (a ∩ b).card ≤ 1) := by decide +kernel theorem P_card : P.card = 4 := by decide +kernel
The maximum triangle packing number of G is 4.
The packing number is defined as the supremum of sizes of edge-disjoint triangle packings. Since P achieves size 4 and every packing has size at most 4 by nu_le, 4 is the maximum of the set of packing sizes, hence equals its supremum via IsGreatest.csSup_eq.
uses
IsGreatest.csSup_eq,P_clique,P_pw,P_card,nu_letheorem pack_eq : simple_graph_triangle_packing_number G = 4 := by unfold simple_graph_triangle_packing_number refine IsGreatest.csSup_eq ⟨⟨P, P_clique, P_pw, P_card⟩, ?_⟩ rintro n ⟨U, h1, h2, rfl⟩ exact nu_le U h1 h2
The triangle edge family of G equals the edge encodings of the triangles in T.
By set extensionality and unfolding simple_graph_triangle_edge_family, an edge triple belongs to the family if and only if it encodes a 3-clique in G. This matches the edge encodings of T because all 3-cliques belong to T (clique_mem) and every element of T is a 3-clique (T_clique).
uses
clique_mem,T_cliquetheorem family : simple_graph_triangle_edge_family G = T.toFinset.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, List.mem_toFinset] constructor · rintro ⟨t, ht, rfl⟩; exact ⟨t, clique_mem ht, rfl⟩ · rintro ⟨t, ht, rfl⟩; exact ⟨t, T_clique t ht, rfl⟩
Each packed triangle in P contains at most one singleton-forced edge. automation
Rewriting with family expresses the triangle edge family in terms of T. The kernel then verifies (decide +kernel) that for each p ∈ P, at most one edge belongs to triangles that share only that single edge with the packing P.
uses
familytheorem forced_le : ∀ 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 := by rw [family] decide +kernel
The indexing and choices of two edges per packed triangle are well-defined. automation
The kernel verifies (decide +kernel) that PI indexes the 4 triangles of P injectively, and that Choice specifies 3 distinct pairs of edges from each packed triangle.
theorem choices_ok : (∀ i : Fin 4, PI i ∈ P) ∧ Function.Injective PI ∧ (∀ i : Fin 4, ∀ j : Fin 3, (Choice i j).card = 2 ∧ Choice i j ⊆ finite_vertex_set_edge_encoding (PI i)) ∧ (∀ i : Fin 4, Function.Injective (Choice i)) := by decide +kernel
No selection of two edges per packed triangle forms a triangle cover. automation
The kernel checks all 3⁴ = 81 selection functions f (decide +kernel), finding for each selection some triangle t ∈ T whose edges are completely disjoint from the chosen edges Picks f.
theorem no_selection : ∀ f : Fin 4 → Fin 3, ∃ t ∈ T, Disjoint (finite_vertex_set_edge_encoding t) (Picks f) := by decide +kernel
SmallCover is a 6-edge triangle cover supported entirely on P. automation
The kernel verifies (decide +kernel) that SmallCover has size 6, uses only edges of P, and intersects every triangle in T.
theorem small_cover : SmallCover.card = 6 ∧ SmallCover ⊆ P.biUnion finite_vertex_set_edge_encoding ∧ ∀ t ∈ T, ¬ Disjoint (finite_vertex_set_edge_encoding t) SmallCover := by decide +kernel end In701Budget
P is a maximum packing with at most one singleton-forced edge per triangle, and |P| = ν(G).
The main theorem decomposes into conjuncts. P_clique, P_pw, forced_le, and choices_ok provide the packing properties, singleton-forced edge bound, and choice validity. Rewriting with P_card and pack_eq shows |P| = ν(G) = 4.
uses
In701Budget.P_clique,In701Budget.P_pw,In701Budget.forced_le,In701Budget.choices_ok,In701Budget.P_card,In701Budget.pack_eqtheorem simple_graph_maximum_packing_fixed_two_budget_counterexample : (∀ t ∈ In701Budget.P, In701Budget.G.IsNClique 3 t) ∧ (In701Budget.P : Set (Finset (Fin 9))).Pairwise (fun a b => (a ∩ b).card ≤ 1) ∧ In701Budget.P.card = simple_graph_triangle_packing_number In701Budget.G ∧ (∀ p ∈ In701Budget.P, (finite_vertex_set_edge_encoding p ∩ (((simple_graph_triangle_edge_family In701Budget.G).filter (fun t => (t ∩ In701Budget.P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)).card ≤ 1) ∧ (∀ i : Fin 4, In701Budget.PI i ∈ In701Budget.P) ∧ Function.Injective In701Budget.PI ∧ (∀ i : Fin 4, ∀ j : Fin 3, (In701Budget.Choice i j).card = 2 ∧ In701Budget.Choice i j ⊆ finite_vertex_set_edge_encoding (In701Budget.PI i)) ∧ (∀ i : Fin 4, Function.Injective (In701Budget.Choice i)) ∧ (∀ f : Fin 4 → Fin 3, ∃ t : Finset (Fin 9), In701Budget.G.IsNClique 3 t ∧ Disjoint (finite_vertex_set_edge_encoding t) (In701Budget.Picks f)) ∧ (In701Budget.SmallCover.card = 6 ∧ In701Budget.SmallCover ⊆ In701Budget.P.biUnion finite_vertex_set_edge_encoding ∧ ∀ t : Finset (Fin 9), In701Budget.G.IsNClique 3 t → ¬ Disjoint (finite_vertex_set_edge_encoding t) In701Budget.SmallCover) := by refine ⟨In701Budget.P_clique,In701Budget.P_pw,?_,In701Budget.forced_le,In701Budget.choices_ok.1,In701Budget.choices_ok.2.1,In701Budget.choices_ok.2.2.1,In701Budget.choices_ok.2.2.2,?_,?_⟩ · rw [In701Budget.P_card,In701Budget.pack_eq]
Every selection of two edges per packed triangle leaves some triangle in G uncovered.
Given a selection f, no_selection yields an uncovered triangle t ∈ T. Since t is a 3-clique in G by T_clique, this witnesses that the selection fails to cover all 3-cliques.
uses
In701Budget.no_selection,In701Budget.T_clique· intro f obtain ⟨t,ht,hd⟩ := In701Budget.no_selection f exact ⟨t,In701Budget.T_clique t ht,hd⟩
SmallCover is a 6-edge triangle cover of G supported on P.
The cardinality 6 and support on P follow from small_cover. Any 3-clique t of G belongs to T by clique_mem, so small_cover guarantees that SmallCover shares an edge with t.
uses
In701Budget.small_cover,In701Budget.clique_mem· refine ⟨In701Budget.small_cover.1,In701Budget.small_cover.2.1,?_⟩ intro t ht exact In701Budget.small_cover.2.2 t (In701Budget.clique_mem ht)
Sym2.eq_swap- An unordered pair s(a, b) is equal to s(b, a).
clique_mem- Every 3-clique in G belongs to the list of triangles T.
family- The triangle edge family of G is the set of edge encodings of the triples in T.
in693_maxC_bound- If a list l has length at most n, any pairwise c-compatible sub-collection of l has size at most in693_maxC c n l.
IsGreatest.csSup_eq- If an element a is the greatest element of a set s, then sSup s = a.
maxC_eq- The compatibility search algorithm certifies that the maximum number of pairwise edge-disjoint triangles in T is 4.
nu_le- Any collection of pairwise edge-disjoint 3-cliques in G has cardinality at most 4.
P_card- The packing P has cardinality 4.
P_clique- Every triple in P spans a 3-clique in G.
P_pw- The triangles in P are pairwise edge-disjoint (sharing at most one vertex).
T_clique- Every element of T spans a 3-clique in G.
In701Budget.choices_ok- The choices of two edges per packed triangle are well-defined and distinct.
In701Budget.clique_mem- Any 3-clique of G belongs to T.
In701Budget.forced_le- Each triangle in P contains at most one singleton-forced edge.
In701Budget.no_selection- For any choice of two edges per packed triangle, some triangle in T remains uncovered.
In701Budget.P_card- The packing P contains 4 triangles.
In701Budget.P_clique- Every triple in P is a 3-clique in G.
In701Budget.P_pw- The triangles in P pairwise share at most one vertex.
In701Budget.pack_eq- The maximum triangle packing number of G is 4.
In701Budget.small_cover- SmallCover has size 6, uses only edges of P, and intersects every triangle in T.
In701Budget.T_clique- Every triple in T is a 3-clique in G.
- The proof relies extensively on the Lean kernel decision procedure (decide +kernel) to computationally verify finite properties: that the 13 triples in T are all the triangles of G, that the compatibility algorithm in693_maxC bounds packing size to 4, that P is an edge-disjoint packing of size 4, that each packed triangle has at most one singleton-forced edge, that all 81 two-edge selections fail to cover all triangles, and that SmallCover is a valid 6-edge cover.
- The graph G is formalized on the finite vertex set Fin 9, with edges represented as unordered pairs in Sym2 (Fin 9).
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 Sym2set_option maxRecDepth 100000set_option maxHeartbeats 30000000namespace In701Budgetdef EL : List (Sym2 (Fin 9)) := [s(0,1), s(0,2), s(0,3), s(1,2), s(1,3), s(2,3), s(2,5), s(2,7), s(2,8), s(3,4), s(3,5), s(3,6), s(4,5), s(4,6), s(5,6), s(5,7), s(5,8), s(7,8)]def T : List (Finset (Fin 9)) := [{0,1,2}, {0,1,3}, {0,2,3}, {1,2,3}, {2,3,5}, {2,5,7}, {2,5,8}, {2,7,8}, {3,4,5}, {3,4,6}, {3,5,6}, {4,5,6}, {5,7,8}]def P : Finset (Finset (Fin 9)) := {{0,1,2}, {3,4,6}, {2,3,5}, {2,7,8}}def E : Finset (Sym2 (Fin 9)) := EL.toFinsetdef G : SimpleGraph (Fin 9) where Adj u v := s(u,v) ∈ 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 G.Adj := fun _ _ => inferInstanceAs (Decidable (_ ∈ E ∧ _ ≠ _))def PI : Fin 4 → Finset (Fin 9) := ![{0,1,2}, {3,4,6}, {2,3,5}, {2,7,8}]def Choice : Fin 4 → Fin 3 → Finset (Sym2 (Fin 9)) := ![![{s(0,1), s(0,2)}, {s(0,1), s(1,2)}, {s(0,2), s(1,2)}], ![{s(3,4), s(3,6)}, {s(3,4), s(4,6)}, {s(3,6), s(4,6)}], ![{s(2,3), s(2,5)}, {s(2,3), s(3,5)}, {s(2,5), s(3,5)}], ![{s(2,7), s(2,8)}, {s(2,7), s(7,8)}, {s(2,8), s(7,8)}]]def SmallCover : Finset (Sym2 (Fin 9)) := {s(0,1), s(2,3), s(2,5), s(3,5), s(4,6), s(7,8)}def Picks (f : Fin 4 → Fin 3) : Finset (Sym2 (Fin 9)) := (Finset.univ : Finset (Fin 4)).biUnion (fun i => Choice i (f i))theorem tri_complete : ∀ t ∈ (Finset.univ : Finset (Fin 9)).powersetCard 3, G.IsNClique 3 t → t ∈ T := by decide +kerneltheorem T_clique : ∀ t ∈ T, G.IsNClique 3 t := by decide +kernellemma clique_mem {t : Finset (Fin 9)} (h : G.IsNClique 3 t) : t ∈ T := tri_complete t (Finset.mem_powersetCard.mpr ⟨Finset.subset_univ _, h.card_eq⟩) hdef compat (s t : Finset (Fin 9)) : Bool := decide ((s ∩ t).card ≤ 1)theorem maxC_eq : in693_maxC compat T.length T = 4 := by decide +kernellemma nu_le (U : Finset (Finset (Fin 9))) (hU : ∀ t ∈ U, G.IsNClique 3 t) (hP : (U : Set (Finset (Fin 9))).Pairwise (fun a b => (a ∩ b).card ≤ 1)) : U.card ≤ 4 := calc U.card ≤ in693_maxC compat T.length T := in693_maxC_bound compat _ T le_rfl U (fun a ha => clique_mem (hU a ha)) (fun a ha b hb hab => decide_eq_true (hP (Finset.mem_coe.mpr ha) (Finset.mem_coe.mpr hb) hab)) _ = 4 := maxC_eqtheorem P_clique : ∀ t ∈ P, G.IsNClique 3 t := by decide +kerneltheorem P_pw : (P : Set (Finset (Fin 9))).Pairwise (fun a b => (a ∩ b).card ≤ 1) := by decide +kerneltheorem P_card : P.card = 4 := by decide +kerneltheorem pack_eq : simple_graph_triangle_packing_number G = 4 := by unfold simple_graph_triangle_packing_number refine IsGreatest.csSup_eq ⟨⟨P, P_clique, P_pw, P_card⟩, ?_⟩ rintro n ⟨U, h1, h2, rfl⟩ exact nu_le U h1 h2theorem family : simple_graph_triangle_edge_family G = T.toFinset.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, List.mem_toFinset] constructor · rintro ⟨t, ht, rfl⟩; exact ⟨t, clique_mem ht, rfl⟩ · rintro ⟨t, ht, rfl⟩; exact ⟨t, T_clique t ht, rfl⟩theorem forced_le : ∀ 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 := by rw [family] decide +kerneltheorem choices_ok : (∀ i : Fin 4, PI i ∈ P) ∧ Function.Injective PI ∧ (∀ i : Fin 4, ∀ j : Fin 3, (Choice i j).card = 2 ∧ Choice i j ⊆ finite_vertex_set_edge_encoding (PI i)) ∧ (∀ i : Fin 4, Function.Injective (Choice i)) := by decide +kerneltheorem no_selection : ∀ f : Fin 4 → Fin 3, ∃ t ∈ T, Disjoint (finite_vertex_set_edge_encoding t) (Picks f) := by decide +kerneltheorem small_cover : SmallCover.card = 6 ∧ SmallCover ⊆ P.biUnion finite_vertex_set_edge_encoding ∧ ∀ t ∈ T, ¬ Disjoint (finite_vertex_set_edge_encoding t) SmallCover := by decide +kernelend In701Budgettheorem simple_graph_maximum_packing_fixed_two_budget_counterexample : (∀ t ∈ In701Budget.P, In701Budget.G.IsNClique 3 t) ∧ (In701Budget.P : Set (Finset (Fin 9))).Pairwise (fun a b => (a ∩ b).card ≤ 1) ∧ In701Budget.P.card = simple_graph_triangle_packing_number In701Budget.G ∧ (∀ p ∈ In701Budget.P, (finite_vertex_set_edge_encoding p ∩ (((simple_graph_triangle_edge_family In701Budget.G).filter (fun t => (t ∩ In701Budget.P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)).card ≤ 1) ∧ (∀ i : Fin 4, In701Budget.PI i ∈ In701Budget.P) ∧ Function.Injective In701Budget.PI ∧ (∀ i : Fin 4, ∀ j : Fin 3, (In701Budget.Choice i j).card = 2 ∧ In701Budget.Choice i j ⊆ finite_vertex_set_edge_encoding (In701Budget.PI i)) ∧ (∀ i : Fin 4, Function.Injective (In701Budget.Choice i)) ∧ (∀ f : Fin 4 → Fin 3, ∃ t : Finset (Fin 9), In701Budget.G.IsNClique 3 t ∧ Disjoint (finite_vertex_set_edge_encoding t) (In701Budget.Picks f)) ∧ (In701Budget.SmallCover.card = 6 ∧ In701Budget.SmallCover ⊆ In701Budget.P.biUnion finite_vertex_set_edge_encoding ∧ ∀ t : Finset (Fin 9), In701Budget.G.IsNClique 3 t → ¬ Disjoint (finite_vertex_set_edge_encoding t) In701Budget.SmallCover) := by refine ⟨In701Budget.P_clique,In701Budget.P_pw,?_,In701Budget.forced_le,In701Budget.choices_ok.1,In701Budget.choices_ok.2.1,In701Budget.choices_ok.2.2.1,In701Budget.choices_ok.2.2.2,?_,?_⟩ · rw [In701Budget.P_card,In701Budget.pack_eq] · intro f obtain ⟨t,ht,hd⟩ := In701Budget.no_selection f exact ⟨t,In701Budget.T_clique t ht,hd⟩ · refine ⟨In701Budget.small_cover.1,In701Budget.small_cover.2.1,?_⟩ intro t ht exact In701Budget.small_cover.2.2 t (In701Budget.clique_mem ht)