in701_packing_le_edge_cover
A triangle packing has at most as many triangles as an edge cover.
Statement
theorem in701_packing_le_edge_cover (G : SimpleGraph (Fin 14)) [DecidableRel G.Adj] (C : Finset (Sym2 (Fin 14))) (hC : ∀ e ∈ C, e ∈ G.edgeSet) (hcover : ∀ t : Finset (Fin 14), G.IsNClique 3 t → ∃ e ∈ C, e ∈ t.sym2) (Q : Finset (Finset (Fin 14))) (hQ : ∀ t ∈ Q, G.IsNClique 3 t) (hpair : (Q : Set (Finset (Fin 14))).Pairwise (fun s t => (s ∩ t).card ≤ 1)) : Q.card ≤ C.card
- Source
- Finite graph and certificates from experiments 20940 and 20968; see state/campaigns/triangle_reductions/outside_induced_kernel_in701.md.
- Verified
- 10 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 2
- in715_deficit_pack_eqFinite certificate for the explicit fourteen-vertex graph.
- simple_graph_deficit_two_example_two_edge_dropDeleting two specified base edges from the explicit 14-vertex local-count counterexample decreases its triangle-packing number from seven…
The proof, explained
The theorem states that in any graph on 14 vertices, the number of triangles in an edge-disjoint triangle packing $Q$ is at most the number of edges in a triangle edge cover $C$. The proof defines a function $f$ that assigns to each triangle in $Q$ an edge from $C$ contained within it, using classical choice. By `Finset.card_le_card_of_injOn`, it suffices to show that $f$ is injective on $Q$. If two distinct triangles shared the same chosen edge, they would share both of its distinct endpoints, giving an intersection of at least two vertices and contradicting the packing condition.
There is a choice function $f$ that assigns to every triangle $t \in Q$ an edge $f(t) \in C$ such that both endpoints of $f(t)$ lie in $t$.
Using classical choice on the covering hypothesis `hcover`, define $f(t)$ to select an edge of $C$ contained in $t$ whenever $t$ is a 3-clique in $G$, and a dummy edge otherwise. Since every $t \in Q$ is a 3-clique by `hQ`, `dif_pos` and `Classical.choose_spec` show that $f(t) \in C$ and $f(t) \in t^{\{2\}}$.
uses
Classical.choose,dif_pos,Classical.choose_specclassical let f (t : Finset (Fin 14)) : Sym2 (Fin 14) := if h : G.IsNClique 3 t then Classical.choose (hcover t h) else s(0,0) have hchosen : ∀ t ∈ Q, f t ∈ C ∧ f t ∈ t.sym2 := by intro t ht simpa only [f, dif_pos (hQ t ht)] using Classical.choose_spec (hcover t (hQ t ht))
To show $|Q| \le |C|$, it suffices to show that $f$ maps $Q$ into $C$ and that $f$ is injective on $Q$.
By `Finset.card_le_card_of_injOn`, the cardinality of a finite set is bounded by that of another if there is an injection from the former into the latter.
uses
Finset.card_le_card_of_injOnapply Finset.card_le_card_of_injOn fThe function $f$ maps $Q$ into $C$.
For every triangle $t \in Q$, the property `hchosen` established during the definition of $f$ directly provides $f(t) \in C$.
uses
Finset.mem_coe.mp· intro t ht exact (hchosen t (Finset.mem_coe.mp ht)).1
If two distinct triangles $s, t \in Q$ were to have $f(s) = f(t)$, then both endpoints of the edge $f(s) = s(u, v)$ would belong to both $s$ and $t$.
Assume for contradiction that $s, t \in Q$ are distinct triangles with $f(s) = f(t)$. By `hchosen`, the edge $f(s)$ is contained in $s$, and $f(t) = f(s)$ is contained in $t$. Writing $f(s)$ as an unordered pair $s(u, v)$ via `Sym2.mk_surjective`, both endpoints $u$ and $v$ belong to both $s$ and $t$ by `Finset.mem_sym2_iff.mp`.
uses
Finset.mem_coe.mp,Sym2.mk_surjective,Finset.mem_sym2_iff.mp· intro s hs t ht heq by_contra hne have hsQ := Finset.mem_coe.mp hs have htQ := Finset.mem_coe.mp ht have hsedge := (hchosen s hsQ).2 have htedge := (hchosen t htQ).2 rw [← heq] at htedge obtain ⟨⟨u,v⟩,huv⟩ := Sym2.mk_surjective (f s) have huv' : s(u,v) = f s := huv rw [← huv'] at hsedge htedge have huvs : ∀ z ∈ s(u,v), z ∈ s := Finset.mem_sym2_iff.mp hsedge have huvt : ∀ z ∈ s(u,v), z ∈ t := Finset.mem_sym2_iff.mp htedge
The vertices $u$ and $v$ are distinct.
The unordered pair $s(u, v) = f(s)$ belongs to $C$, which is a subset of the edge set of $G$ (by `hC`). Therefore, $u$ and $v$ are adjacent in $G$ (`SimpleGraph.mem_edgeSet`), which implies $u \neq v$ since adjacency is irreflexive.
uses
SimpleGraph.mem_edgeSethave hadj : G.Adj u v := (SimpleGraph.mem_edgeSet G).mp (by rw [huv'] exact hC _ (hchosen s hsQ).1) have huv_ne : u ≠ v := hadj.ne
The function $f$ is injective on $Q$, which implies $|Q| \le |C|$.
Because $u$ and $v$ are two distinct vertices both belonging to $s \cap t$, the intersection has cardinality strictly greater than 1 (`Finset.one_lt_card.mpr`). But by the packing hypothesis `hpair`, distinct triangles in $Q$ share at most 1 vertex: $|s \cap t| \le 1$. Linear arithmetic (`omega`) derives a contradiction from $|s \cap t| > 1$ and $|s \cap t| \le 1$, proving injectivity and concluding the theorem.
uses
Finset.one_lt_card.mprhave hi : 1 < (s ∩ t).card := Finset.one_lt_card.mpr ⟨u,by simp [huvs u (by simp), huvt u (by simp)],v,by simp [huvs v (by simp),huvt v (by simp)],huv_ne⟩ have hl := hpair hs ht hne omega
Classical.choose- Given an existential proof `∃ x, P x`, produces a witness `x`.
Classical.choose_spec- For an existential proof `h : ∃ x, P x`, the chosen witness `Classical.choose h` satisfies `P`.
dif_pos- A dependent if-then-else `if h : c then t else e` simplifies to `t h` when `c` is true.
Finset.card_le_card_of_injOn- If a function `f` maps a finite set `s` into a finite set `t` and is injective on `s`, then `|s| ≤ |t|`.
Finset.mem_coe.mp- Membership of an element in the set coercion of a finset `↑s` implies membership in `s`.
Finset.mem_sym2_iff.mp- If an unordered pair belongs to the 2-element subsets of a finset `s` (`t.sym2`), every vertex in that pair belongs to `s`.
Finset.one_lt_card.mpr- A finset has cardinality strictly greater than 1 if it contains two distinct elements.
SimpleGraph.mem_edgeSet- An unordered pair `s(v, w)` belongs to the edge set of a graph `G` if and only if `v` and `w` are adjacent in `G`.
Sym2.mk_surjective- Every element of `Sym2 α` can be represented as an unordered pair `s(u, v)` of elements `u, v : α`.
- The graph's vertex type is fixed to `Fin 14`, although the combinatorial argument is completely general and holds for any graph.
- Graph edges and 2-element subsets are formally represented as unordered pairs using the `Sym2` type.
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 30000000theorem in701_packing_le_edge_cover (G : SimpleGraph (Fin 14)) [DecidableRel G.Adj] (C : Finset (Sym2 (Fin 14))) (hC : ∀ e ∈ C, e ∈ G.edgeSet) (hcover : ∀ t : Finset (Fin 14), G.IsNClique 3 t → ∃ e ∈ C, e ∈ t.sym2) (Q : Finset (Finset (Fin 14))) (hQ : ∀ t ∈ Q, G.IsNClique 3 t) (hpair : (Q : Set (Finset (Fin 14))).Pairwise (fun s t => (s ∩ t).card ≤ 1)) : Q.card ≤ C.card := by classical let f (t : Finset (Fin 14)) : Sym2 (Fin 14) := if h : G.IsNClique 3 t then Classical.choose (hcover t h) else s(0,0) have hchosen : ∀ t ∈ Q, f t ∈ C ∧ f t ∈ t.sym2 := by intro t ht simpa only [f, dif_pos (hQ t ht)] using Classical.choose_spec (hcover t (hQ t ht)) apply Finset.card_le_card_of_injOn f · intro t ht exact (hchosen t (Finset.mem_coe.mp ht)).1 · intro s hs t ht heq by_contra hne have hsQ := Finset.mem_coe.mp hs have htQ := Finset.mem_coe.mp ht have hsedge := (hchosen s hsQ).2 have htedge := (hchosen t htQ).2 rw [← heq] at htedge obtain ⟨⟨u,v⟩,huv⟩ := Sym2.mk_surjective (f s) have huv' : s(u,v) = f s := huv rw [← huv'] at hsedge htedge have huvs : ∀ z ∈ s(u,v), z ∈ s := Finset.mem_sym2_iff.mp hsedge have huvt : ∀ z ∈ s(u,v), z ∈ t := Finset.mem_sym2_iff.mp htedge have hadj : G.Adj u v := (SimpleGraph.mem_edgeSet G).mp (by rw [huv'] exact hC _ (hchosen s hsQ).1) have huv_ne : u ≠ v := hadj.ne have hi : 1 < (s ∩ t).card := Finset.one_lt_card.mpr ⟨u,by simp [huvs u (by simp), huvt u (by simp)],v,by simp [huvs v (by simp),huvt v (by simp)],huv_ne⟩ have hl := hpair hs ht hne omega