AFTD Auto-Formalizing Theoretical Domains

simple_graph_deficit_two_example_two_edge_drop

theoremverified

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

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.

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

    lines 12–21

    uses SimpleGraph.mem_edgeSet, SimpleGraph.deleteEdges_adj.mpr

      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 +kernel
  2. 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.

    line 23

    theorem in715_dropC_card : in715_dropC.card = 5 := by decide +kernel
  3. 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.

    lines 27–36

    uses SimpleGraph.deleteEdges_le, in715_deficit_cover, in715_deficit_c_edges, Sym2.mk_surjective, Finset.mem_sym2_iff.mp, SimpleGraph.mem_edgeSet

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

    lines 37–46

    uses SimpleGraph.deleteEdges_adj.mp, SimpleGraph.mem_edgeSet

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

    lines 49–55

    uses csSup_le, in701_packing_le_edge_cover, in715_dropC_edges, in715_dropC_cover, in715_dropC_card

      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 h
  6. 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)}.

    line 57

    uses in715_deficit_drop

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

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