simple_graph_triangle_packing_number_delete_edge_lt_or_eq
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
- 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).
- simple_graph_triangle_packing_number_monoTriangle packing number is monotone under subgraph inclusion: if H ≤ G, then ν(H) ≤ ν(G).
- Used by 1
- simple_graph_triangle_cover_number_le_two_mul_packing_number_of_packing_critical_caseTuza's conjecture follows from its packing-critical case: if every finite graph G with 2 ≤ ν(G) in which every edge deletion preserves ν…
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.
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.
uses
Or.inlby_cases h : ∃ e ∈ G.edgeSet, simple_graph_triangle_packing_number (G.deleteEdges {e}) < simple_graph_triangle_packing_number G · exact Or.inl h
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).
· right intro e he
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).
uses
simple_graph_triangle_packing_number_mono,SimpleGraph.deleteEdges_lehave 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
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.
/-- 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