simple_graph_triangle_packing_decreases_of_high_codegree
Deleting an edge with more than twice the maximum triangle packing number common neighbors strictly decreases the packing number.
Statement
theorem simple_graph_triangle_packing_decreases_of_high_codegree {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (u v : V) (huv : G.Adj u v) (hlarge : 2 * simple_graph_triangle_packing_number G < ((Finset.univ : Finset V).filter (fun w => G.Adj u w ∧ G.Adj v w)).card) : simple_graph_triangle_packing_number (G.deleteEdges {s(u,v)}) < simple_graph_triangle_packing_number G
- Source
- Structural helper for the triangle packing-cover campaign; related matching-cover reductions are in https://arxiv.org/abs/2610.15269, Lemma 2.3. Finite checks and limitations are recorded in state/campaigns/triangle_reductions/high_codegree_route_in512.md.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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).
- simple_graph_maximum_triangle_packing_edge_meetsEvery triangle shares an edge with a member of a maximum edge-disjoint triangle packing.
- simple_graph_maximal_packing_common_neighbors_leIf a maximal edge-disjoint triangle packing avoids an edge, that edge has at most twice as many common neighbors as the packing has…
The proof, explained
The proof proceeds by contradiction. If deleting the edge {u, v} does not strictly decrease the triangle packing number, then the remaining graph H = G \ {{u, v}} has a maximum triangle packing P of size equal to ν(G), making P a maximum triangle packing of G as well. Since the edge {u, v} was deleted, no triangle in P can contain both u and v. However, any maximal triangle packing avoiding {u, v} forces the codegree of u and v to be at most 2|P| = 2ν(G), contradicting the hypothesis that u and v have strictly more than 2ν(G) common neighbors.
The graph H obtained by deleting the edge {u, v} is a subgraph of G, so its triangle packing number satisfies ν(H) ≤ ν(G).
Let H = G \ {{u, v}}. Since deleting edges produces a subgraph (H ≤ G by SimpleGraph.deleteEdges_le), monotonicity of the triangle packing number (simple_graph_triangle_packing_number_mono) implies that ν(H) ≤ ν(G).
uses
SimpleGraph.deleteEdges_le,simple_graph_triangle_packing_number_monoclassical let H := G.deleteEdges {s(u,v)} have hHG : H ≤ G := SimpleGraph.deleteEdges_le (G := G) {s(u,v)} have hle : simple_graph_triangle_packing_number H ≤ simple_graph_triangle_packing_number G := simple_graph_triangle_packing_number_mono G H hHG
Assuming the packing number does not strictly decrease implies ν(H) = ν(G).
Assume for contradiction that ν(H) < ν(G) does not hold. Because ν(H) ≤ ν(G), linear integer arithmetic implies that ν(H) = ν(G).
by_contra hn change ¬ simple_graph_triangle_packing_number H < simple_graph_triangle_packing_number G at hn have heq : simple_graph_triangle_packing_number H = simple_graph_triangle_packing_number G := by omega
There exists an edge-disjoint triangle packing P in H achieving the maximum size |P| = ν(H).
Let A be the set of sizes of edge-disjoint triangle packings in H. The empty packing shows that 0 ∈ A, so A is nonempty. Moreover, every packing is a family of subsets of V, so its size is bounded by the total number of subsets |Finset V| via Finset.card_le_univ. By Nat.sSup_mem, the supremum ν(H) = sSup A is attained by some packing P in H with |P| = ν(H).
uses
Finset.card_le_univ,Nat.sSup_memlet A : Set ℕ := {n | ∃ P : Finset (Finset V), (∀ t ∈ P, H.IsNClique 3 t) ∧ (P : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ P.card = n} have hne : A.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩ have hbdd : BddAbove A := by refine ⟨Fintype.card (Finset V), ?_⟩ rintro n ⟨P, _, _, rfl⟩ exact Finset.card_le_univ P obtain ⟨P, hPH, hpair, hcard⟩ := Nat.sSup_mem hne hbdd
P is a maximum triangle packing of G, so every triangle in G shares an edge with some triangle in P.
Since |P| = ν(H) and ν(H) = ν(G), we have |P| = ν(G). Furthermore, because H ≤ G, every triangle in H is also a triangle in G. Thus P is a triangle packing in G of maximum possible size ν(G). By simple_graph_maximum_triangle_packing_edge_meets, every triangle in G must share at least two vertices with some triangle in P.
uses
simple_graph_maximum_triangle_packing_edge_meetshave hcard' : P.card = simple_graph_triangle_packing_number G := by change P.card = simple_graph_triangle_packing_number H at hcard omega have hPG : ∀ t ∈ P, G.IsNClique 3 t := by intro t ht exact (hPH t ht).mono hHG have hmax := simple_graph_maximum_triangle_packing_edge_meets G P hPG hpair hcard'
No triangle in P contains both u and v.
Suppose some triangle s ∈ P contains both u and v. Since s is a clique in H, u and v would be adjacent in H. However, the edge {u, v} was deleted to form H, so SimpleGraph.deleteEdges_adj.mp implies that {u, v} cannot be an edge of H, giving a contradiction.
uses
SimpleGraph.deleteEdges_adj.mphave havoid : ∀ s ∈ P, ¬(u ∈ s ∧ v ∈ s) := by intro s hs hmem have hadj : H.Adj u v := (hPH s hs).isClique hmem.1 hmem.2 (G.ne_of_adj huv) have := (SimpleGraph.deleteEdges_adj.mp hadj).2 exact this (by simp)
The number of common neighbors of u and v is at most 2ν(G), contradicting the hypothesis.
Because P is a maximal triangle packing in G that avoids the edge {u, v}, simple_graph_maximal_packing_common_neighbors_le implies that the number of common neighbors of u and v in G is at most 2|P| = 2ν(G). But the hypothesis hlarge asserts that the common neighbor count is strictly greater than 2ν(G). Linear arithmetic closes the goal with a contradiction.
uses
simple_graph_maximal_packing_common_neighbors_lehave hsmall := simple_graph_maximal_packing_common_neighbors_le G u v P huv hPG hmax havoid rw [hcard'] at hsmall omega
SimpleGraph.deleteEdges_le- Deleting a set of edges from a graph results in a subgraph of the original graph.
simple_graph_triangle_packing_number_mono- If H is a subgraph of G, the triangle packing number of H is at most that of G.
Finset.card_le_univ- The cardinality of any finite subset of α is at most the total cardinality of α.
Nat.sSup_mem- Any nonempty, bounded-above set of natural numbers contains its supremum (maximum).
simple_graph_maximum_triangle_packing_edge_meets- In any maximum triangle packing, every triangle in the graph shares at least an edge (two vertices) with some triangle in the packing.
SimpleGraph.deleteEdges_adj.mp- If an edge belongs to a graph obtained by deleting a set of edges, then it belonged to the original graph and was not in the deleted set.
simple_graph_maximal_packing_common_neighbors_le- If a maximal triangle packing avoids an edge {u, v}, then the number of common neighbors of u and v is at most twice the size of the packing.
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.
open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem simple_graph_triangle_packing_decreases_of_high_codegree {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (u v : V) (huv : G.Adj u v) (hlarge : 2 * simple_graph_triangle_packing_number G < ((Finset.univ : Finset V).filter (fun w => G.Adj u w ∧ G.Adj v w)).card) : simple_graph_triangle_packing_number (G.deleteEdges {s(u,v)}) < simple_graph_triangle_packing_number G := by classical let H := G.deleteEdges {s(u,v)} have hHG : H ≤ G := SimpleGraph.deleteEdges_le (G := G) {s(u,v)} have hle : simple_graph_triangle_packing_number H ≤ simple_graph_triangle_packing_number G := simple_graph_triangle_packing_number_mono G H hHG by_contra hn change ¬ simple_graph_triangle_packing_number H < simple_graph_triangle_packing_number G at hn have heq : simple_graph_triangle_packing_number H = simple_graph_triangle_packing_number G := by omega let A : Set ℕ := {n | ∃ P : Finset (Finset V), (∀ t ∈ P, H.IsNClique 3 t) ∧ (P : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ P.card = n} have hne : A.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩ have hbdd : BddAbove A := by refine ⟨Fintype.card (Finset V), ?_⟩ rintro n ⟨P, _, _, rfl⟩ exact Finset.card_le_univ P obtain ⟨P, hPH, hpair, hcard⟩ := Nat.sSup_mem hne hbdd have hcard' : P.card = simple_graph_triangle_packing_number G := by change P.card = simple_graph_triangle_packing_number H at hcard omega have hPG : ∀ t ∈ P, G.IsNClique 3 t := by intro t ht exact (hPH t ht).mono hHG have hmax := simple_graph_maximum_triangle_packing_edge_meets G P hPG hpair hcard' have havoid : ∀ s ∈ P, ¬(u ∈ s ∧ v ∈ s) := by intro s hs hmem have hadj : H.Adj u v := (hPH s hs).isClique hmem.1 hmem.2 (G.ne_of_adj huv) have := (SimpleGraph.deleteEdges_adj.mp hadj).2 exact this (by simp) have hsmall := simple_graph_maximal_packing_common_neighbors_le G u v P huv hPG hmax havoid rw [hcard'] at hsmall omega