simple_graph_triangle_packing_number_ge_of_edge_reduction
Let G be a finite simple graph, F a nonempty edge subset, S a pairwise edge-disjoint triangle family, and X an edge subset such that X meets every triangle containing an edge of F and E(S) \ F ⊆ X. Then the triangle packing number of G \ (F ∪ X) plus |S| is at most the triangle packing number of G.
Statement
open Classical in theorem simple_graph_triangle_packing_number_ge_of_edge_reduction {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (F : Finset (Sym2 V)) (hF : F ⊆ G.edgeFinset) (hFne : F.Nonempty) (S : Finset (Finset V)) (hS : ∀ t ∈ S, G.IsNClique 3 t) (hSpairwise : (S : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1)) (X : Finset (Sym2 V)) (hX : X ⊆ G.edgeFinset) (hXmeets : ∀ t : Finset V, G.IsNClique 3 t → (∃ e ∈ F, ∀ x ∈ e, x ∈ t) → ∃ e ∈ X, ∀ x ∈ e, x ∈ t) (hES : (S.biUnion finite_vertex_set_edge_encoding \ F) ⊆ X) : simple_graph_triangle_packing_number (G.deleteEdges (↑(F ∪ X) : Set (Sym2 V))) + S.card ≤ simple_graph_triangle_packing_number G
- Source
- arXiv:2611.11128 Lemma 2.2 -- Triangle-overlap cores and density bounds for Tuza's conjecture
- Verified
- 11 Nov 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).
- finite_vertex_set_edge_encodingThe non-diagonal unordered vertex pairs spanned by a finite vertex set.
- Used by 1
- simple_graph_edge_reduction_inequalityLet G be a finite simple graph. Suppose there exist a nonempty edge set F ⊆ E(G), a set S of pairwise edge-disjoint triangles of G, and an…
Read back from the Lean
Let $V$ be a finite type with decidable equality, and let $G$ be a simple graph on $V$. Let $F$ be a finite set of edges of $G$ ($F \subseteq G.\text{edgeFinset}$) that is nonempty ($F.\text{Nonempty}$). Let $S$ be a finite set of finite vertex subsets of $V$ such that: 1. Every $t \in S$ is a 3-clique in $G$ ($G.\text{IsNClique } 3\ t$), and 2. The sets in $S$ are pairwise edge-disjoint: for any distinct $s, t \in S$, $|s \cap t| \le 1$. Let $X$ be a finite set of edges of $G$ ($X \subseteq G.\text{edgeFinset}$) such that: 1. For every finite vertex set $t \subseteq V$, if $t$ is a 3-clique in $G$ and $t$ contains both endpoints of some edge in $F$, then $t$ contains both endpoints of some edge in $X$; and 2. Every edge of every triangle in $S$ that is not in $F$ belongs to $X$ (i.e., $(\bigcup_{s \in S} \{ e \in s.\text{sym2} \mid \neg e.\text{IsDiag} \}) \setminus F \subseteq X$). Then, the triangle packing number of the graph obtained by deleting the edges $F \cup X$ from $G$, plus $|S|$, is less than or equal to the triangle packing number of $G$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
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.
open Classicaldef simple_graph_triangle_packing_number_ge_of_edge_reduction.feasible {V : Type*} [DecidableEq V] (G : SimpleGraph V) (T : Finset (Finset V)) : Prop := (∀ t ∈ T, G.IsNClique 3 t) ∧ ((T : Set (Finset V)).Pairwise fun s t => (s ∩ t).card ≤ 1)lemma simple_graph_triangle_packing_number_ge_of_edge_reduction.feasible_eq {V : Type*} [DecidableEq V] (G : SimpleGraph V) : simple_graph_triangle_packing_number G = sSup {n : ℕ | ∃ T, feasible G T ∧ T.card = n} := by simp only [simple_graph_triangle_packing_number, feasible, and_assoc]lemma simple_graph_triangle_packing_number_ge_of_edge_reduction.bddAbove {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) : BddAbove {n : ℕ | ∃ T, feasible G T ∧ T.card = n} := by refine ⟨(Finset.univ.powerset : Finset (Finset V)).card, ?_⟩ rintro n ⟨T, hT, rfl⟩ apply Finset.card_le_card intro x hx rw [Finset.mem_powerset] exact Finset.subset_univ xlemma simple_graph_triangle_packing_number_ge_of_edge_reduction.nonempty {V : Type*} [DecidableEq V] (G : SimpleGraph V) : ({n : ℕ | ∃ T, feasible G T ∧ T.card = n} : Set ℕ).Nonempty := by refine ⟨0, ∅, ?_, by simp⟩ simp [feasible]lemma simple_graph_triangle_packing_number_ge_of_edge_reduction.card_le {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (T : Finset (Finset V)) (h : feasible G T) : T.card ≤ simple_graph_triangle_packing_number G := by rw [feasible_eq] exact le_csSup (bddAbove G) ⟨T, h, rfl⟩lemma simple_graph_triangle_packing_number_ge_of_edge_reduction.exists_packing {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) : ∃ T, feasible G T ∧ T.card = simple_graph_triangle_packing_number G := by rw [feasible_eq] exact Nat.sSup_mem (nonempty G) (bddAbove G)open Classical in/-- Under an edge reduction (F, S, X), the triangle packing number of G is at least that of G \ (F ∪ X) plus |S|. -/theorem simple_graph_triangle_packing_number_ge_of_edge_reduction {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (F : Finset (Sym2 V)) (hF : F ⊆ G.edgeFinset) (hFne : F.Nonempty) (S : Finset (Finset V)) (hS : ∀ t ∈ S, G.IsNClique 3 t) (hSpairwise : (S : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1)) (X : Finset (Sym2 V)) (hX : X ⊆ G.edgeFinset) (hXmeets : ∀ t : Finset V, G.IsNClique 3 t → (∃ e ∈ F, ∀ x ∈ e, x ∈ t) → ∃ e ∈ X, ∀ x ∈ e, x ∈ t) (hES : (S.biUnion finite_vertex_set_edge_encoding \ F) ⊆ X) : simple_graph_triangle_packing_number (G.deleteEdges (↑(F ∪ X) : Set (Sym2 V))) + S.card ≤ simple_graph_triangle_packing_number G := by obtain ⟨T0, hT0, hT0card⟩ := simple_graph_triangle_packing_number_ge_of_edge_reduction.exists_packing (G.deleteEdges (↑(F ∪ X) : Set (Sym2 V))) have hcross : ∀ t ∈ T0, ∀ s ∈ S, (t ∩ s).card ≤ 1 := by intro t ht s hs by_contra hle rw [not_le] at hle obtain ⟨a, ha, b, hb, hab⟩ := Finset.one_lt_card.mp hle rw [Finset.mem_inter] at ha hb have hadj' : (G.deleteEdges (↑(F ∪ X) : Set (Sym2 V))).Adj a b := (hT0.1 t ht).isClique ha.1 hb.1 hab have hadj : G.Adj a b := (hS s hs).isClique ha.2 hb.2 hab have he'_edge : s(a, b) ∈ (G.deleteEdges (↑(F ∪ X) : Set (Sym2 V))).edgeSet := (SimpleGraph.mem_edgeSet (G.deleteEdges (↑(F ∪ X) : Set (Sym2 V)))).mpr hadj' rw [SimpleGraph.edgeSet_deleteEdges] at he'_edge have he_notin : s(a, b) ∉ F ∪ X := fun hmem => he'_edge.2 (by simpa using hmem) have he_enc : s(a, b) ∈ finite_vertex_set_edge_encoding s := by rw [finite_vertex_set_edge_encoding, Finset.mem_filter] exact ⟨Finset.mk_mem_sym2_iff.mpr ⟨ha.2, hb.2⟩, by rwa [Sym2.mk_isDiag_iff]⟩ have he_bi : s(a, b) ∈ S.biUnion finite_vertex_set_edge_encoding := Finset.mem_biUnion.mpr ⟨s, hs, he_enc⟩ have heFX : s(a, b) ∈ F ∪ X := by by_cases heF : s(a, b) ∈ F · exact Finset.mem_union.mpr (Or.inl heF) · exact Finset.mem_union.mpr (Or.inr (hES (Finset.mem_sdiff.mpr ⟨he_bi, heF⟩))) exact he_notin heFX have hdisj : Disjoint T0 S := by rw [Finset.disjoint_left] intro s hsT hsS have h1 := hcross s hsT s hsS rw [Finset.inter_self] at h1 have h2 : s.card = 3 := (hS s hsS).card_eq omega have hunion : simple_graph_triangle_packing_number_ge_of_edge_reduction.feasible G (T0 ∪ S) := by constructor · intro t ht rw [Finset.mem_union] at ht rcases ht with ht | ht · exact (hT0.1 t ht).mono (SimpleGraph.deleteEdges_le (↑(F ∪ X) : Set (Sym2 V))) · exact hS t ht · rw [Finset.coe_union, Set.pairwise_union] refine ⟨hT0.2, hSpairwise, ?_⟩ intro a ha b hb hab exact ⟨hcross a ha b hb, by rw [Finset.inter_comm]; exact hcross a ha b hb⟩ have hcard : (T0 ∪ S).card = T0.card + S.card := Finset.card_union_of_disjoint hdisj have hle : (T0 ∪ S).card ≤ simple_graph_triangle_packing_number G := simple_graph_triangle_packing_number_ge_of_edge_reduction.card_le G (T0 ∪ S) hunion rw [hcard, hT0card] at hle exact hle