simple_graph_deficit_two_example_two_edge_drop
Deleting two specified base edges from the explicit 14-vertex local-count counterexample decreases its triangle-packing number from seven to at most five.
Statement
theorem simple_graph_deficit_two_example_two_edge_drop : simple_graph_triangle_packing_number (In701Deficit14.G.deleteEdges {s(0,1),s(0,4)}) ≤ 5- Source
- Two-edge-deletion certificate for the finite local-count example in state/campaigns/triangle_reductions/outside_induced_kernel_in701.md.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- in715_deficit_preciseAn explicit fourteen-vertex graph has a maximum seven-triangle packing, a seven-edge triangle cover, an outside five-cycle link and a…
- in701_packing_le_edge_coverA triangle packing has at most as many triangles as an edge cover.
- 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).
- in715_deficit_c_edgesFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_coverFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_p_sizeFinite certificate for the explicit fourteen-vertex graph.
The proof, explained
Let G' = G \ {{0, 1}, {0, 4}} be the graph obtained by deleting two base edges from the 14-vertex counterexample graph G. In G, every triangle is covered by a 7-edge set C; removing the two deleted edges yields a 5-edge set C'. Any triangle in G' is also a triangle in G and must contain an edge of C; since both endpoints of that edge belong to the triangle in G', the edge survives in G' and cannot be either of the two deleted edges, placing it in C'. Thus C' is a 5-edge triangle cover for G', which by triangle packing-covering duality implies that the triangle packing number of G' is at most 5.
Each of the five edges in in715_dropC is an edge of in715_dropG.
To show that every edge e in the 5-element set in715_dropC = {{1, 2}, {2, 3}, {3, 4}, {0, 11}, {1, 11}} is an edge of in715_dropG = G \ {{0, 1}, {0, 4}}, we perform case analysis on e. By SimpleGraph.deleteEdges_adj.mpr and SimpleGraph.mem_edgeSet, an edge belongs to the subgraph if the endpoints are adjacent in G and the edge is not among the two deleted edges. Both conditions are checked for all five edges by kernel evaluation (decide +kernel).
uses
SimpleGraph.mem_edgeSet,SimpleGraph.deleteEdges_adj.mprintro e he simp only [in715_dropC, Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl | rfl | rfl all_goals apply (SimpleGraph.mem_edgeSet _).mpr apply SimpleGraph.deleteEdges_adj.mpr constructor · decide +kernel · simp only [Set.mem_insert_iff, Set.mem_singleton_iff, not_or] constructor <;> decide +kernel
The candidate edge cover in715_dropC has cardinality 5.
The set in715_dropC is explicitly defined as a 5-element set of unordered pairs, and its cardinality is verified to be 5 by kernel evaluation.
theorem in715_dropC_card : in715_dropC.card = 5 := by decide +kernel
Any triangle in in715_dropG contains an edge {u, v} of the original cover C, and this edge is also an edge of in715_dropG.
Let t be any triangle (3-clique) in in715_dropG. Since in715_dropG is a subgraph of G (SimpleGraph.deleteEdges_le), t is also a triangle in G. By the known cover theorem for G (in715_deficit_cover), t contains some edge e in C, which is an edge of G (in715_deficit_c_edges). Writing e as {u, v} via Sym2.mk_surjective, the endpoints are distinct (u ≠ v) because e is an edge. Since e is in t (Finset.mem_sym2_iff.mp), both u and v belong to t. Because t is a clique in in715_dropG, {u, v} must be an edge of in715_dropG.
uses
SimpleGraph.deleteEdges_le,in715_deficit_cover,in715_deficit_c_edges,Sym2.mk_surjective,Finset.mem_sym2_iff.mp,SimpleGraph.mem_edgeSetintro t ht have htG : In701Deficit14.G.IsNClique 3 t := ht.mono (SimpleGraph.deleteEdges_le _) obtain ⟨e, heC, het⟩ := in715_deficit_cover t htG have heG := in715_deficit_c_edges e heC obtain ⟨⟨u,v⟩, rfl⟩ := Sym2.mk_surjective e have huv : u ≠ v := ((SimpleGraph.mem_edgeSet _).mp heG).ne have huvT := Finset.mem_sym2_iff.mp het have hu : u ∈ t := huvT u (by simp) have hv : v ∈ t := huvT v (by simp) have hd : s(u,v) ∈ in715_dropG.edgeSet := (SimpleGraph.mem_edgeSet _).mpr (ht.isClique hu hv huv)
The covering edge {u, v} belongs to in715_dropC, proving that in715_dropC covers all triangles in in715_dropG.
Since {u, v} is an edge in in715_dropG = G \ {{0, 1}, {0, 4}}, the definition of edge deletion (SimpleGraph.deleteEdges_adj.mp) guarantees that {u, v} ≠ {0, 1} and {u, v} ≠ {0, 4}. The original covering set C consists of the five edges in in715_dropC plus {0, 1} and {0, 4}. Since {u, v} ∈ C and is neither of the deleted edges, it must belong to in715_dropC. Thus {u, v} provides the required edge in in715_dropC covering triangle t.
uses
SimpleGraph.deleteEdges_adj.mp,SimpleGraph.mem_edgeSethave hne1 : s(u,v) ≠ s(0,1) := by intro h have ha := (SimpleGraph.deleteEdges_adj.mp ((SimpleGraph.mem_edgeSet _).mp hd)).2 exact ha (by simp [h]) have hne2 : s(u,v) ≠ s(0,4) := by intro h have ha := (SimpleGraph.deleteEdges_adj.mp ((SimpleGraph.mem_edgeSet _).mp hd)).2 exact ha (by simp [h]) refine ⟨s(u,v), ?_, het⟩ simpa [In701Deficit14.C, in715_dropC, hne1, hne2] using heC
The triangle packing number of in715_dropG is at most 5.
The triangle packing number is defined as the supremum of sizes of collections of pairwise edge-disjoint triangles in in715_dropG. By csSup_le, witnessing non-emptiness with the empty family of triangles, it suffices to show that any triangle packing Q has size at most 5. By in701_packing_le_edge_cover, the size of any triangle packing is at most the cardinality of any edge cover of all triangles. Using the edge cover in715_dropC (proved in in715_dropC_edges and in715_dropC_cover) and its cardinality 5 (in715_dropC_card), we conclude that |Q| ≤ 5.
uses
csSup_le,in701_packing_le_edge_cover,in715_dropC_edges,in715_dropC_cover,in715_dropC_cardclassical unfold simple_graph_triangle_packing_number refine csSup_le ⟨0, ∅, by simp, by simp, rfl⟩ ?_ rintro n ⟨Q, hQ, hpair, rfl⟩ have h := in701_packing_le_edge_cover in715_dropG in715_dropC in715_dropC_edges in715_dropC_cover Q hQ hpair simpa [in715_dropC_card] using h
Deleting {s(0, 1), s(0, 4)} from G results in a graph with triangle packing number at most 5.
This is the main theorem; it follows directly from in715_deficit_drop because in715_dropG is defined as G.deleteEdges {s(0, 1), s(0, 4)}.
uses
in715_deficit_droptheorem simple_graph_deficit_two_example_two_edge_drop : simple_graph_triangle_packing_number (In701Deficit14.G.deleteEdges {s(0,1),s(0,4)}) ≤ 5 := by exact in715_deficit_drop
SimpleGraph.mem_edgeSet- An unordered pair of vertices belongs to the edge set of a simple graph if and only if the two vertices are adjacent.
SimpleGraph.deleteEdges_adj.mpr- If two vertices are adjacent in a graph G and their connecting edge is not in the set of deleted edges s, then they are adjacent in G \ s.
SimpleGraph.deleteEdges_le- Deleting a set of edges from a graph G yields a subgraph of G.
in715_deficit_cover- Every triangle (3-clique) in the 14-vertex deficit graph G contains at least one edge from the 7-element covering set C.
in715_deficit_c_edges- Every element of the covering set C is an edge of the 14-vertex deficit graph G.
Sym2.mk_surjective- Every unordered pair of vertices in Sym²(V) can be written as {u, v} for some vertices u and v.
Finset.mem_sym2_iff.mp- If an unordered pair belongs to the symmetric square of a finite set of vertices t, then both of its endpoints belong to t.
SimpleGraph.deleteEdges_adj.mp- If two vertices are adjacent in G \ s, then they are adjacent in G and their connecting edge is not in s.
csSup_le- For a non-empty subset of a conditionally complete lattice, if every element is bounded above by a, then its supremum is at most a.
in701_packing_le_edge_cover- The cardinality of any collection of pairwise edge-disjoint triangles in G is at most the cardinality of any set of edges that intersects every triangle of G.
in715_dropC_edges- Every element of in715_dropC is an edge of the subgraph in715_dropG.
in715_dropC_cover- Every triangle in in715_dropG contains at least one edge from in715_dropC.
in715_dropC_card- The set in715_dropC contains exactly 5 edges.
in715_deficit_drop- The triangle packing number of in715_dropG is at most 5.
- The verification that the five candidate edges belong to the modified graph (in715_dropC_edges) and that the candidate edge set has cardinality 5 (in715_dropC_card) is discharged by Lean's kernel computation (decide +kernel).
- The triangle packing number is defined via a supremum (csSup) over natural numbers, which requires formally providing the empty packing as a witness that the set of packing sizes is non-empty before bounding the supremum.
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 30000000noncomputable def in715_dropG : SimpleGraph (Fin 14) := In701Deficit14.G.deleteEdges {s(0,1),s(0,4)}def in715_dropC : Finset (Sym2 (Fin 14)) := {s(1,2),s(2,3),s(3,4),s(0,11),s(1,11)}theorem in715_dropC_edges : ∀ e ∈ in715_dropC, e ∈ in715_dropG.edgeSet := by intro e he simp only [in715_dropC, Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl | rfl | rfl all_goals apply (SimpleGraph.mem_edgeSet _).mpr apply SimpleGraph.deleteEdges_adj.mpr constructor · decide +kernel · simp only [Set.mem_insert_iff, Set.mem_singleton_iff, not_or] constructor <;> decide +kerneltheorem in715_dropC_card : in715_dropC.card = 5 := by decide +kerneltheorem in715_dropC_cover : ∀ t : Finset (Fin 14), in715_dropG.IsNClique 3 t → ∃ e ∈ in715_dropC, e ∈ t.sym2 := by intro t ht have htG : In701Deficit14.G.IsNClique 3 t := ht.mono (SimpleGraph.deleteEdges_le _) obtain ⟨e, heC, het⟩ := in715_deficit_cover t htG have heG := in715_deficit_c_edges e heC obtain ⟨⟨u,v⟩, rfl⟩ := Sym2.mk_surjective e have huv : u ≠ v := ((SimpleGraph.mem_edgeSet _).mp heG).ne have huvT := Finset.mem_sym2_iff.mp het have hu : u ∈ t := huvT u (by simp) have hv : v ∈ t := huvT v (by simp) have hd : s(u,v) ∈ in715_dropG.edgeSet := (SimpleGraph.mem_edgeSet _).mpr (ht.isClique hu hv huv) have hne1 : s(u,v) ≠ s(0,1) := by intro h have ha := (SimpleGraph.deleteEdges_adj.mp ((SimpleGraph.mem_edgeSet _).mp hd)).2 exact ha (by simp [h]) have hne2 : s(u,v) ≠ s(0,4) := by intro h have ha := (SimpleGraph.deleteEdges_adj.mp ((SimpleGraph.mem_edgeSet _).mp hd)).2 exact ha (by simp [h]) refine ⟨s(u,v), ?_, het⟩ simpa [In701Deficit14.C, in715_dropC, hne1, hne2] using heCtheorem in715_deficit_drop : simple_graph_triangle_packing_number in715_dropG ≤ 5 := by classical unfold simple_graph_triangle_packing_number refine csSup_le ⟨0, ∅, by simp, by simp, rfl⟩ ?_ rintro n ⟨Q, hQ, hpair, rfl⟩ have h := in701_packing_le_edge_cover in715_dropG in715_dropC in715_dropC_edges in715_dropC_cover Q hQ hpair simpa [in715_dropC_card] using htheorem simple_graph_deficit_two_example_two_edge_drop : simple_graph_triangle_packing_number (In701Deficit14.G.deleteEdges {s(0,1),s(0,4)}) ≤ 5 := by exact in715_deficit_drop