AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_packing_number_le_delete_edge_add_one

theoremverified

Deleting an edge e from G decreases the triangle packing number by at most 1: ν(G) ≤ ν(G \ {e}) + 1.

Statement

theorem simple_graph_triangle_packing_number_le_delete_edge_add_one {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) (e : Sym2 V) (he : e ∈ G.edgeSet) :
    simple_graph_triangle_packing_number G ≤ simple_graph_triangle_packing_number (G.deleteEdges {e}) + 1
Source
step towards simple_graph_triangle_cover_number_le_two_mul_packing_number
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

Let T be a maximum triangle packing in G, so that |T| = ν(G). Because triangles in a packing pairwise share at most one vertex, at most one triangle in T can contain both endpoints of the edge e. Removing this triangle (if present) leaves a subcollection T' of size at least |T| - 1. Every triangle in T' avoids e and therefore remains a 3-clique in G \ {e}, making T' a valid triangle packing in G \ {e} and proving ν(G) ≤ |T'| + 1 ≤ ν(G \ {e}) + 1.

  1. There exists an optimal triangle packing T in G whose size attains ν(G).

    We define P as the set of sizes of all triangle packings in G (families of 3-cliques that pairwise intersect in at most one vertex). Because the vertex set V is finite, the collection of all subsets of V is finite, so P is bounded above by the cardinality of the universe. The empty packing shows that 0 ∈ P, so P is nonempty. By Nat.sSup_mem, the supremum of P belongs to P, giving a triangle packing T such that |T| = sSup P = ν(G).

    lines 5–16

    uses Finset.card_le_univ, Nat.sSup_mem

      classical
      set P : Set ℕ := {n | ∃ T : Finset (Finset V), (∀ t ∈ T, G.IsNClique 3 t) ∧
        (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ T.card = n} with hP
      have hbdd : BddAbove P := by
        refine ⟨(Finset.univ : Finset (Finset V)).card, ?_⟩
        rintro n ⟨T, -, -, rfl⟩
        exact Finset.card_le_univ T
      have hne : P.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩
      obtain ⟨T, hT, hTp, hTc⟩ := Nat.sSup_mem hne hbdd
      have hG_eq : simple_graph_triangle_packing_number G = T.card := by
        change sSup P = T.card
        exact hTc.symm
  2. At most one triangle in T contains the edge e.

    Let p(t) be the property that both endpoints of e lie in t. Since e is an edge of G, it is not a diagonal, so e = s(u, v) with u ≠ v. If two distinct triangles t₁, t₂ ∈ T both contained e, then {u, v} ⊆ t₁ ∩ t₂. Since u ≠ v, this would imply |t₁ ∩ t₂| ≥ |{u, v}| = 2. But distinct triangles in a packing pairwise share at most one vertex (|t₁ ∩ t₂| ≤ 1), a contradiction. Hence at most one triangle in T contains e.

    lines 17–43

    uses Sym2.inductionOn, Sym2.mk_isDiag_iff, Finset.card_le_one_iff, Finset.mem_filter, Finset.mem_insert, Finset.mem_singleton, Finset.card_pair, Finset.card_le_card

      let p : Finset V → Prop := fun t => ∀ x ∈ e, x ∈ t
      have hp_card : (T.filter p).card ≤ 1 := by
        obtain ⟨u, v, huv, rfl⟩ : ∃ u v, u ≠ v ∧ e = s(u, v) := by
          have hdiag := G.not_isDiag_of_mem_edgeSet he
          induction' e using Sym2.inductionOn with u v
          simp only [Sym2.mk_isDiag_iff] at hdiag
          exact ⟨u, v, hdiag, rfl⟩
        rw [Finset.card_le_one_iff]
        intro t1 t2 ht1 ht2
        rw [Finset.mem_filter] at ht1 ht2
        by_contra hne_t
        have hpw := hTp ht1.1 ht2.1 hne_t
        have hu1 : u ∈ t1 := ht1.2 u (by simp)
        have hv1 : v ∈ t1 := ht1.2 v (by simp)
        have hu2 : u ∈ t2 := ht2.2 u (by simp)
        have hv2 : v ∈ t2 := ht2.2 v (by simp)
        have h2 : 2 ≤ (t1 ∩ t2).card := by
          have h_sub : {u, v} ⊆ t1 ∩ t2 := by
            intro x hx
            simp only [Finset.mem_insert, Finset.mem_singleton] at hx
            rcases hx with rfl | rfl
            · simp [hu1, hu2]
            · simp [hv1, hv2]
          have h_card : ({u, v} : Finset V).card = 2 := Finset.card_pair huv
          rw [← h_card]
          exact Finset.card_le_card h_sub
        omega
  3. The subcollection T' of triangles not containing e satisfies |T| ≤ |T'| + 1.

    Let T' be the collection of triangles in T that do not satisfy p. Since T is partitioned into triangles satisfying p and those satisfying ¬p, |T| = |T.filter p| + |T'|. Because |T.filter p| ≤ 1, it follows that |T| ≤ |T'| + 1.

    lines 44–47

    uses Finset.card_filter_add_card_filter_not

      let T' := T.filter (fun t => ¬ p t)
      have hT'_card : T.card ≤ T'.card + 1 := by
        have hsplit : (T.filter p).card + T'.card = T.card := Finset.card_filter_add_card_filter_not p
        omega
  4. Every triangle in T' is a 3-clique in G \ {e}.

    Each t ∈ T' is a 3-clique in G, so |t| = 3. For any two distinct vertices x, y ∈ t, the edge s(x, y) belongs to G. If s(x, y) were equal to e, then both endpoints of e would belong to t, contradicting t ∈ T'. Hence s(x, y) ≠ e, which means the edge survives in G \ {e} by SimpleGraph.deleteEdges_adj.

    lines 48–65

    uses Finset.mem_filter, SimpleGraph.deleteEdges_adj, Set.mem_singleton_iff, Sym2.mem_iff

      have hT'_clique : ∀ t ∈ T', (G.deleteEdges {e}).IsNClique 3 t := by
        intro t ht
        rw [Finset.mem_filter] at ht
        obtain ⟨htT, hnot_p⟩ := ht
        have hclique := hT t htT
        refine ⟨?_, hclique.card_eq⟩
        intro x hx y hy hxy
        rw [SimpleGraph.deleteEdges_adj]
        refine ⟨hclique.isClique hx hy hxy, ?_⟩
        intro heq
        simp only [Set.mem_singleton_iff] at heq
        apply hnot_p
        intro z hz
        rw [← heq] at hz
        simp only [Sym2.mem_iff] at hz
        rcases hz with rfl | rfl
        · exact hx
        · exact hy
  5. The triangles in T' are pairwise edge-disjoint.

    Because T' is a subcollection of T, the property that any two distinct triangles share at most one vertex is directly inherited from T.

    lines 66–70

    uses Finset.mem_coe, Finset.mem_filter

      have hT'_pw : (T' : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) := by
        refine hTp.mono ?_
        intro t ht
        rw [Finset.mem_coe, Finset.mem_filter] at ht
        exact Finset.mem_coe.2 ht.1
  6. The size of T' is at most ν(G \ {e}).

    The triangle packing number ν(G \ {e}) is the supremum of cardinalities of all triangle packings in G \ {e}. Since T' is a valid packing in G \ {e}, its size belongs to this set, which is bounded above. Therefore |T'| ≤ ν(G \ {e}) by le_csSup.

    lines 71–79

    uses Finset.card_le_univ, le_csSup

      have hT'_le : T'.card ≤ simple_graph_triangle_packing_number (G.deleteEdges {e}) := by
        unfold simple_graph_triangle_packing_number
        have hbdd' : BddAbove {n | ∃ T : Finset (Finset V),
            (∀ t ∈ T, (G.deleteEdges {e}).IsNClique 3 t) ∧
            (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ T.card = n} := by
          refine ⟨(Finset.univ : Finset (Finset V)).card, ?_⟩
          rintro n ⟨T'', -, -, rfl⟩
          exact Finset.card_le_univ T''
        exact le_csSup hbdd' ⟨T', hT'_clique, hT'_pw, rfl⟩
  7. ν(G) ≤ ν(G \ {e}) + 1.

    Combining ν(G) = |T|, |T| ≤ |T'| + 1, and |T'| ≤ ν(G \ {e}) via linear arithmetic over ℕ establishes the desired inequality.

    line 80

      omega
Finset.card_le_univ
The cardinality of any finset in a finite type is at most the cardinality of the universe.
Nat.sSup_mem
A nonempty set of natural numbers bounded above contains its supremum.
Sym2.inductionOn
To prove a property for all unordered pairs, it suffices to prove it for pairs of the form s(x, y).
Sym2.mk_isDiag_iff
An unordered pair s(x, y) is a diagonal (a self-loop) if and only if x = y.
Finset.card_le_one_iff
A finset has cardinality at most 1 if and only if any two of its elements are equal.
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_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the singleton {a} if and only if it equals a.
Finset.card_pair
The pair {a, b} has cardinality 2 if a ≠ b.
Finset.card_le_card
If s ⊆ t for finsets s and t, then |s| ≤ |t|.
Finset.card_filter_add_card_filter_not
For any predicate p on a finset s, the number of elements satisfying p plus the number satisfying ¬p equals |s|.
SimpleGraph.deleteEdges_adj
Vertices v and w are adjacent in G.deleteEdges s if and only if they are adjacent in G and the edge s(v, w) is not in s.
Set.mem_singleton_iff
An element belongs to the singleton set {b} if and only if it equals b.
Sym2.mem_iff
An element a belongs to the unordered pair s(b, c) if and only if a = b or a = c.
Finset.mem_coe
Membership in a coerced finset is equivalent to membership in the finset itself.
le_csSup
In a conditionally complete lattice, any element of a set bounded above is at most the supremum of that set.

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

/-- Deleting an edge e from G decreases the triangle packing number by at most 1: ν(G) ≤ ν(G \ {e}) + 1. -/theorem simple_graph_triangle_packing_number_le_delete_edge_add_one {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) (e : Sym2 V) (he : e ∈ G.edgeSet) :    simple_graph_triangle_packing_number G ≤ simple_graph_triangle_packing_number (G.deleteEdges {e}) + 1 := by  classical  set P : Set ℕ := {n | ∃ T : Finset (Finset V), (∀ t ∈ T, G.IsNClique 3 t) ∧    (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ T.card = n} with hP  have hbdd : BddAbove P := by    refine ⟨(Finset.univ : Finset (Finset V)).card, ?_⟩    rintro n ⟨T, -, -, rfl⟩    exact Finset.card_le_univ T  have hne : P.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩  obtain ⟨T, hT, hTp, hTc⟩ := Nat.sSup_mem hne hbdd  have hG_eq : simple_graph_triangle_packing_number G = T.card := by    change sSup P = T.card    exact hTc.symm  let p : Finset V → Prop := fun t => ∀ x ∈ e, x ∈ t  have hp_card : (T.filter p).card ≤ 1 := by    obtain ⟨u, v, huv, rfl⟩ : ∃ u v, u ≠ v ∧ e = s(u, v) := by      have hdiag := G.not_isDiag_of_mem_edgeSet he      induction' e using Sym2.inductionOn with u v      simp only [Sym2.mk_isDiag_iff] at hdiag      exact ⟨u, v, hdiag, rfl⟩    rw [Finset.card_le_one_iff]    intro t1 t2 ht1 ht2    rw [Finset.mem_filter] at ht1 ht2    by_contra hne_t    have hpw := hTp ht1.1 ht2.1 hne_t    have hu1 : u ∈ t1 := ht1.2 u (by simp)    have hv1 : v ∈ t1 := ht1.2 v (by simp)    have hu2 : u ∈ t2 := ht2.2 u (by simp)    have hv2 : v ∈ t2 := ht2.2 v (by simp)    have h2 : 2 ≤ (t1 ∩ t2).card := by      have h_sub : {u, v} ⊆ t1 ∩ t2 := by        intro x hx        simp only [Finset.mem_insert, Finset.mem_singleton] at hx        rcases hx with rfl | rfl        · simp [hu1, hu2]        · simp [hv1, hv2]      have h_card : ({u, v} : Finset V).card = 2 := Finset.card_pair huv      rw [← h_card]      exact Finset.card_le_card h_sub    omega  let T' := T.filter (fun t => ¬ p t)  have hT'_card : T.card ≤ T'.card + 1 := by    have hsplit : (T.filter p).card + T'.card = T.card := Finset.card_filter_add_card_filter_not p    omega  have hT'_clique : ∀ t ∈ T', (G.deleteEdges {e}).IsNClique 3 t := by    intro t ht    rw [Finset.mem_filter] at ht    obtain ⟨htT, hnot_p⟩ := ht    have hclique := hT t htT    refine ⟨?_, hclique.card_eq⟩    intro x hx y hy hxy    rw [SimpleGraph.deleteEdges_adj]    refine ⟨hclique.isClique hx hy hxy, ?_⟩    intro heq    simp only [Set.mem_singleton_iff] at heq    apply hnot_p    intro z hz    rw [← heq] at hz    simp only [Sym2.mem_iff] at hz    rcases hz with rfl | rfl    · exact hx    · exact hy  have hT'_pw : (T' : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) := by    refine hTp.mono ?_    intro t ht    rw [Finset.mem_coe, Finset.mem_filter] at ht    exact Finset.mem_coe.2 ht.1  have hT'_le : T'.card ≤ simple_graph_triangle_packing_number (G.deleteEdges {e}) := by    unfold simple_graph_triangle_packing_number    have hbdd' : BddAbove {n | ∃ T : Finset (Finset V),        (∀ t ∈ T, (G.deleteEdges {e}).IsNClique 3 t) ∧        (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ T.card = n} := by      refine ⟨(Finset.univ : Finset (Finset V)).card, ?_⟩      rintro n ⟨T'', -, -, rfl⟩      exact Finset.card_le_univ T''    exact le_csSup hbdd' ⟨T', hT'_clique, hT'_pw, rfl⟩  omega
See it in the graphDiscuss this resultChallenge it