AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_cover_number_delete_edge_le

theoremverified

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

Statement

theorem simple_graph_triangle_cover_number_delete_edge_le {V : Type*} [Fintype V]
    (G : SimpleGraph V) (e : Sym2 V) (he : e ∈ G.edgeSet) :
    simple_graph_triangle_cover_number G ≤ simple_graph_triangle_cover_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
Used by 1

The proof, explained

Let H = G \ {e} be the graph obtained by deleting the edge e, and let F be a minimum triangle cover of H, so that |F| = τ(H). Adjoining the deleted edge e to F produces a set of edges F ∪ {e} of G with size at most |F| + 1. Every triangle in G either contains e (and is therefore covered by e) or does not contain e (in which case it remains a triangle in H and is covered by some edge in F). Thus F ∪ {e} is a valid triangle cover for G, which implies τ(G) ≤ |F ∪ {e}| ≤ τ(H) + 1 = τ(G \ {e}) + 1.

  1. Let H = G \ {e} be the subgraph of G obtained by deleting the edge e.

    We enable classical logic and define the abbreviation H for the graph G.deleteEdges {e} with the edge e removed.

    lines 5–7

      classical
      -- τ(G) is the least cardinality of a triangle cover; take a minimum cover F of G \ {e}.
      set H : SimpleGraph V := G.deleteEdges {e} with hHdef
  2. There exists a minimum triangle cover F of H, whose cardinality is τ(H).

    The family of triangle covers of H is nonempty because the full edge set E(H) covers every triangle of H: for any 3-clique {u, v, w} in H, the edge {u, v} belongs to E(H) and is contained in {u, v, w}. Because this set of cover sizes is a nonempty set of natural numbers, by `Nat.sInf_mem` it contains its infimum τ(H). Let F be a minimum triangle cover witnessing this infimum, so F ⊆ E(H), F covers all 3-cliques of H, and |F| = τ(H).

    lines 8–21

    uses SimpleGraph.mem_edgeFinset, Finset.card_eq_three.mp, SimpleGraph.mem_edgeSet, Sym2.mem_iff, Nat.sInf_mem

      -- The family of cardinalities of triangle covers of H is nonempty: the full edge set works.
      have hSne : {n : ℕ | ∃ F : Finset (Sym2 V), (∀ f ∈ F, f ∈ H.edgeSet) ∧
          (∀ t : Finset V, H.IsNClique 3 t → ∃ f ∈ F, ∀ x ∈ f, x ∈ t) ∧ F.card = n}.Nonempty := by
        refine ⟨_, H.edgeFinset, ?_, ?_, rfl⟩
        · intro f hf; rwa [SimpleGraph.mem_edgeFinset] at hf
        · intro t ht
          obtain ⟨u, v, w, huv, -, -, rfl⟩ := Finset.card_eq_three.mp ht.card_eq
          refine ⟨s(u, v), ?_, ?_⟩
          · rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet]
            exact ht.isClique (by simp) (by simp) huv
          · intro x hx
            rw [Sym2.mem_iff] at hx
            rcases hx with rfl | rfl <;> simp
      obtain ⟨F, hFsub, hFcov, hFcard⟩ := Nat.sInf_mem hSne
  3. Every edge in F is an edge of G.

    Since F is a triangle cover of H = G \ {e}, its edges satisfy F ⊆ E(H) = E(G) \ {e}, so every edge in F is in particular an edge of G.

    lines 22–26

    uses SimpleGraph.edgeSet_deleteEdges

      have hFsubG : ∀ f ∈ F, f ∈ G.edgeSet := by
        intro f hf
        have := hFsub f hf
        rw [hHdef, SimpleGraph.edgeSet_deleteEdges] at this
        exact this.1
  4. The set F ∪ {e} covers every triangle in G.

    Let t be a triangle (3-clique) in G. We split into two cases based on whether the deleted edge e is contained in t: 1. If both endpoints of e lie in t, then e covers t, and e ∈ F ∪ {e}. 2. If e is not contained in t, then no pair of vertices in t forms the edge e. Thus all edges of the clique t remain in H = G \ {e}, meaning t is a 3-clique in H. Since F covers all triangles of H, some edge f ∈ F has both endpoints in t, and f also belongs to F ∪ {e}.

    lines 27–45

    uses Finset.mem_insert_self, SimpleGraph.isClique_iff, SimpleGraph.deleteEdges_adj, Sym2.mem_iff, Finset.mem_insert_of_mem

      -- Adjoining e to F covers every triangle of G.
      have hcoverG : ∀ t : Finset V, G.IsNClique 3 t → ∃ f ∈ insert e F, ∀ x ∈ f, x ∈ t := by
        intro t ht
        by_cases hcase : ∀ x ∈ e, x ∈ t
        · exact ⟨e, Finset.mem_insert_self e F, hcase⟩
        · -- A triangle of G not containing e is a triangle of G \ {e}.
          have hclq : H.IsClique (↑t : Set V) := by
            have hG := ht.isClique
            rw [SimpleGraph.isClique_iff] at hG ⊢
            intro a ha b hb hab
            rw [SimpleGraph.deleteEdges_adj]
            refine ⟨hG ha hb hab, ?_⟩
            intro hmem
            exact hcase fun x hx => by
              rw [← hmem] at hx
              rw [Sym2.mem_iff] at hx
              rcases hx with rfl | rfl <;> assumption
          obtain ⟨f, hfF, hft⟩ := hFcov t ⟨hclq, ht.card_eq⟩
          exact ⟨f, Finset.mem_insert_of_mem hfF, hft⟩
  5. Every edge in F ∪ {e} is an edge of G.

    Any edge in F ∪ {e} is either e (which belongs to E(G) by hypothesis) or belongs to F (which is a subset of E(G) by Step 3).

    lines 46–51

    uses Finset.mem_insert

      have hsubG' : ∀ f ∈ insert e F, f ∈ G.edgeSet := by
        intro f hf
        rw [Finset.mem_insert] at hf
        rcases hf with rfl | hf
        · exact he
        · exact hFsubG f hf
  6. τ(G) ≤ |F ∪ {e}|.

    Because F ∪ {e} consists of edges of G and covers every triangle of G, its cardinality belongs to the set of triangle cover sizes of G. By definition of τ(G) as the infimum of this set, τ(G) ≤ |F ∪ {e}|.

    lines 52–55

    uses Nat.sInf_le

      have hmemG : (insert e F).card ∈ {n : ℕ | ∃ F : Finset (Sym2 V), (∀ f ∈ F, f ∈ G.edgeSet) ∧
          (∀ t : Finset V, G.IsNClique 3 t → ∃ f ∈ F, ∀ x ∈ f, x ∈ t) ∧ F.card = n} :=
        ⟨insert e F, hsubG', hcoverG, rfl⟩
      have h1 : simple_graph_triangle_cover_number G ≤ (insert e F).card := Nat.sInf_le hmemG
  7. |F ∪ {e}| ≤ τ(H) + 1.

    The cover F was chosen with |F| = τ(H). Inserting a single element e into F increases its cardinality by at most 1, giving |F ∪ {e}| ≤ |F| + 1 = τ(H) + 1.

    lines 56–59

    uses Finset.card_insert_le

      have h3 : F.card = simple_graph_triangle_cover_number H := hFcard
      have h2 : (insert e F).card ≤ simple_graph_triangle_cover_number H + 1 := by
        rw [← h3]
        exact Finset.card_insert_le e F
  8. Combining the bounds yields τ(G) ≤ τ(G \ {e}) + 1.

    Rewriting H as G \ {e}, transitivity of the inequalities τ(G) ≤ |F ∪ {e}| and |F ∪ {e}| ≤ τ(G \ {e}) + 1 finishes the proof via linear arithmetic.

    lines 60–61

      rw [hHdef] at h2 ⊢
      omega
Finset.card_eq_three.mp
A finite set has cardinality 3 if and only if it consists of three distinct elements.
Finset.card_insert_le
Inserting an element into a finite set increases its cardinality by at most 1: |{a} ∪ s| ≤ |s| + 1.
Finset.mem_insert
An element belongs to {b} ∪ s if and only if it equals b or belongs to s.
Finset.mem_insert_of_mem
If an element belongs to s, then it also belongs to {b} ∪ s.
Finset.mem_insert_self
An element a belongs to {a} ∪ s.
Nat.sInf_le
The infimum of a set of natural numbers is less than or equal to any element of that set.
Nat.sInf_mem
Any nonempty set of natural numbers contains its infimum (minimum).
SimpleGraph.deleteEdges_adj
Vertices u and v are adjacent in G \ s if and only if they are adjacent in G and the edge between them is not in s.
SimpleGraph.edgeSet_deleteEdges
The edge set of G after deleting a set of edges s is the set difference E(G) \ s.
SimpleGraph.isClique_iff
A set of vertices is a clique in G if and only if every pair of distinct vertices in the set is adjacent in G.
SimpleGraph.mem_edgeFinset
An edge belongs to the finite edge set of a graph if and only if it belongs to its edge set.
SimpleGraph.mem_edgeSet
The unordered pair s(v, w) belongs to the edge set of G if and only if v and w are adjacent in G.
Sym2.mem_iff
A vertex x belongs to the unordered pair s(u, v) if and only if x = u or x = v.

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 cover number by at most 1: τ(G) ≤ τ(G \ {e}) + 1. -/theorem simple_graph_triangle_cover_number_delete_edge_le {V : Type*} [Fintype V]    (G : SimpleGraph V) (e : Sym2 V) (he : e ∈ G.edgeSet) :    simple_graph_triangle_cover_number G ≤ simple_graph_triangle_cover_number (G.deleteEdges {e}) + 1 := by  classical  -- τ(G) is the least cardinality of a triangle cover; take a minimum cover F of G \ {e}.  set H : SimpleGraph V := G.deleteEdges {e} with hHdef  -- The family of cardinalities of triangle covers of H is nonempty: the full edge set works.  have hSne : {n : ℕ | ∃ F : Finset (Sym2 V), (∀ f ∈ F, f ∈ H.edgeSet) ∧      (∀ t : Finset V, H.IsNClique 3 t → ∃ f ∈ F, ∀ x ∈ f, x ∈ t) ∧ F.card = n}.Nonempty := by    refine ⟨_, H.edgeFinset, ?_, ?_, rfl⟩    · intro f hf; rwa [SimpleGraph.mem_edgeFinset] at hf    · intro t ht      obtain ⟨u, v, w, huv, -, -, rfl⟩ := Finset.card_eq_three.mp ht.card_eq      refine ⟨s(u, v), ?_, ?_⟩      · rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet]        exact ht.isClique (by simp) (by simp) huv      · intro x hx        rw [Sym2.mem_iff] at hx        rcases hx with rfl | rfl <;> simp  obtain ⟨F, hFsub, hFcov, hFcard⟩ := Nat.sInf_mem hSne  have hFsubG : ∀ f ∈ F, f ∈ G.edgeSet := by    intro f hf    have := hFsub f hf    rw [hHdef, SimpleGraph.edgeSet_deleteEdges] at this    exact this.1  -- Adjoining e to F covers every triangle of G.  have hcoverG : ∀ t : Finset V, G.IsNClique 3 t → ∃ f ∈ insert e F, ∀ x ∈ f, x ∈ t := by    intro t ht    by_cases hcase : ∀ x ∈ e, x ∈ t    · exact ⟨e, Finset.mem_insert_self e F, hcase⟩    · -- A triangle of G not containing e is a triangle of G \ {e}.      have hclq : H.IsClique (↑t : Set V) := by        have hG := ht.isClique        rw [SimpleGraph.isClique_iff] at hG ⊢        intro a ha b hb hab        rw [SimpleGraph.deleteEdges_adj]        refine ⟨hG ha hb hab, ?_⟩        intro hmem        exact hcase fun x hx => by          rw [← hmem] at hx          rw [Sym2.mem_iff] at hx          rcases hx with rfl | rfl <;> assumption      obtain ⟨f, hfF, hft⟩ := hFcov t ⟨hclq, ht.card_eq⟩      exact ⟨f, Finset.mem_insert_of_mem hfF, hft⟩  have hsubG' : ∀ f ∈ insert e F, f ∈ G.edgeSet := by    intro f hf    rw [Finset.mem_insert] at hf    rcases hf with rfl | hf    · exact he    · exact hFsubG f hf  have hmemG : (insert e F).card ∈ {n : ℕ | ∃ F : Finset (Sym2 V), (∀ f ∈ F, f ∈ G.edgeSet) ∧      (∀ t : Finset V, G.IsNClique 3 t → ∃ f ∈ F, ∀ x ∈ f, x ∈ t) ∧ F.card = n} :=    ⟨insert e F, hsubG', hcoverG, rfl⟩  have h1 : simple_graph_triangle_cover_number G ≤ (insert e F).card := Nat.sInf_le hmemG  have h3 : F.card = simple_graph_triangle_cover_number H := hFcard  have h2 : (insert e F).card ≤ simple_graph_triangle_cover_number H + 1 := by    rw [← h3]    exact Finset.card_insert_le e F  rw [hHdef] at h2 ⊢  omega
See it in the graphDiscuss this resultChallenge it