AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_packing_number_delete_edge_lt_or_eq

theoremverified

For every finite graph G, either some single-edge deletion strictly decreases the triangle packing number, or every single-edge deletion preserves it.

Statement

theorem simple_graph_triangle_packing_number_delete_edge_lt_or_eq {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) :
    (∃ e ∈ G.edgeSet,
      simple_graph_triangle_packing_number (G.deleteEdges {e}) <
        simple_graph_triangle_packing_number G) ∨
    (∀ e ∈ G.edgeSet,
      simple_graph_triangle_packing_number (G.deleteEdges {e}) =
        simple_graph_triangle_packing_number G)
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

We perform a case split on whether there exists an edge whose deletion strictly decreases the triangle packing number. If such an edge exists, the first alternative holds immediately. Otherwise, no edge deletion strictly decreases the packing number, and deleting an edge cannot increase it because the triangle packing number is monotone under subgraph inclusion. Combining these two inequalities shows that every edge deletion leaves the triangle packing number unchanged.

  1. If some edge deletion strictly decreases the triangle packing number, the first disjunct holds.

    We perform a case analysis on whether there exists an edge e ∈ E(G) whose deletion strictly decreases the triangle packing number. In the affirmative case, the left disjunct of the theorem holds immediately by Or.inl.

    lines 10–11

    uses Or.inl

      by_cases h : ∃ e ∈ G.edgeSet, simple_graph_triangle_packing_number (G.deleteEdges {e}) < simple_graph_triangle_packing_number G
      · exact Or.inl h
  2. In the remaining case, it suffices to show that deleting an arbitrary edge e ∈ E(G) preserves the triangle packing number.

    Assuming no edge deletion strictly decreases the packing number, we target the right disjunct (right) and fix an arbitrary edge e ∈ E(G) (intro e he).

    lines 12–13

      · right
        intro e he
  3. Deleting e preserves the triangle packing number: ν(G \ {e}) = ν(G).

    Deleting e yields a subgraph G \ {e} ≤ G by SimpleGraph.deleteEdges_le, so monotonicity of the triangle packing number (simple_graph_triangle_packing_number_mono) ensures that the packing number cannot increase: ν(G \ {e}) ≤ ν(G). Moreover, ν(G \ {e}) < ν(G) cannot hold because e would then witness the existence of a strictly decreasing edge deletion, contradicting the case hypothesis. Since ν(G \ {e}) ≤ ν(G) and ¬(ν(G \ {e}) < ν(G)), linear arithmetic over ℕ (omega) concludes that ν(G \ {e}) = ν(G).

    lines 14–18

    uses simple_graph_triangle_packing_number_mono, SimpleGraph.deleteEdges_le

        have hle : simple_graph_triangle_packing_number (G.deleteEdges {e}) ≤ simple_graph_triangle_packing_number G :=
          simple_graph_triangle_packing_number_mono G (G.deleteEdges {e}) (SimpleGraph.deleteEdges_le {e})
        have hnot : ¬ (simple_graph_triangle_packing_number (G.deleteEdges {e}) < simple_graph_triangle_packing_number G) :=
          fun hlt => h ⟨e, he, hlt⟩
        omega
Or.inl
If proposition a holds, then the disjunction a ∨ b holds.
SimpleGraph.deleteEdges_le
Deleting a set of edges from a graph G produces a subgraph of G.
simple_graph_triangle_packing_number_mono
If a graph H is a subgraph of G (H ≤ G), then the triangle packing number of H is at most that of G.

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

/-- Dichotomy of edge deletions for the triangle packing number: either one deletion drops it, or all deletions preserve it. -/theorem simple_graph_triangle_packing_number_delete_edge_lt_or_eq {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) :    (∃ e ∈ G.edgeSet,      simple_graph_triangle_packing_number (G.deleteEdges {e}) <        simple_graph_triangle_packing_number G) ∨    (∀ e ∈ G.edgeSet,      simple_graph_triangle_packing_number (G.deleteEdges {e}) =        simple_graph_triangle_packing_number G) := by  by_cases h : ∃ e ∈ G.edgeSet, simple_graph_triangle_packing_number (G.deleteEdges {e}) < simple_graph_triangle_packing_number G  · exact Or.inl h  · right    intro e he    have hle : simple_graph_triangle_packing_number (G.deleteEdges {e}) ≤ simple_graph_triangle_packing_number G :=      simple_graph_triangle_packing_number_mono G (G.deleteEdges {e}) (SimpleGraph.deleteEdges_le {e})    have hnot : ¬ (simple_graph_triangle_packing_number (G.deleteEdges {e}) < simple_graph_triangle_packing_number G) :=      fun hlt => h ⟨e, he, hlt⟩    omega
See it in the graphDiscuss this resultChallenge it