simple_graph_triangle_cover_of_avoided_near_high_codegree
If a maximum triangle packing avoids an edge with at least twice the packing number minus one common neighbors and the packing number is at least two, the triangle cover number is at most twice the packing number.
Statement
theorem simple_graph_triangle_cover_of_avoided_near_high_codegree {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (u v : V) (P : Finset (Finset V)) (huv : G.Adj u v) (hcl : ∀ t ∈ P, G.IsNClique 3 t) (hmax : ∀ t : Finset V, G.IsNClique 3 t → ∃ s ∈ P, 2 ≤ (s ∩ t).card) (havoid : ∀ s ∈ P, ¬(u ∈ s ∧ v ∈ s)) (hsize : P.card = simple_graph_triangle_packing_number G) (hPtwo : 2 ≤ P.card) (hlarge : 2 * P.card ≤ ((Finset.univ : Finset V).filter (fun w => G.Adj u w ∧ G.Adj v w)).card + 1) : simple_graph_triangle_cover_number G ≤ 2 * simple_graph_triangle_packing_number G
- Source
- Structural helper for the triangle packing-cover campaign, related to matching-cover reductions in https://arxiv.org/abs/2610.15269; see state/campaigns/triangle_reductions/high_codegree_route_in512.md.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- simple_graph_common_neighbors_matching_of_avoided_packingFor a triangle-maximal family of size p avoiding an edge with d common neighbors, their induced graph contains a matching of size at least…
- simple_graph_triangle_cover_of_near_full_common_matchingIf an edge has a common-neighbor matching of size one below the graph triangle packing number and another common neighbor outside the…
- 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_cover_numberτ(G): the minimum number of edges of G such that every triangle of G contains one of them.
The proof, explained
The proof applies simple_graph_common_neighbors_matching_of_avoided_packing to find a matching M of pairs in the common neighborhood N of u and v such that |N| ≤ |P| + |M|. Using the lower bound |N| ≥ 2|P| - 1, we extract a sub-matching M₀ ⊆ M of size |P| - 1, which covers at most 2|P| - 2 vertices and thus leaves an uncovered common neighbor w ∈ N ∖ ⋃ M₀. Finally, simple_graph_triangle_cover_of_near_full_common_matching bounds the cover number by |M₀| + 3 = |P| + 2, which is at most 2|P| = 2ν(G) since |P| ≥ 2.
There exists a pairwise disjoint collection M of 2-element cliques in the common neighborhood of u and v with |P| - 1 ≤ |M|.
Let N be the set of common neighbors of u and v. By simple_graph_common_neighbors_matching_of_avoided_packing, there is a pairwise disjoint family M of pairs of adjacent vertices in N (forming triangles with both u and v) such that |N| ≤ |P| + |M|. Since 2|P| ≤ |N| + 1 by hypothesis, linear arithmetic implies |P| - 1 ≤ |M|.
uses
simple_graph_common_neighbors_matching_of_avoided_packingclassical let N : Finset V := (Finset.univ : Finset V).filter (fun w => G.Adj u w ∧ G.Adj v w) obtain ⟨M, hMdis, hMprop, hMbound⟩ := simple_graph_common_neighbors_matching_of_avoided_packing G u v P huv hcl hmax havoid have hsubcard : P.card - 1 ≤ M.card := by omega
There exists a sub-matching M₀ ⊆ M of size |P| - 1 consisting of pairwise disjoint pairs.
Since |P| - 1 ≤ |M|, Finset.exists_subset_card_eq guarantees the existence of a subset M₀ ⊆ M of cardinality |P| - 1. Because M₀ is a subset of the pairwise disjoint family M, the pairs in M₀ are also pairwise disjoint.
uses
Finset.exists_subset_card_eqobtain ⟨M0, hM0sub, hM0card⟩ := Finset.exists_subset_card_eq hsubcard have hM0dis : (M0 : Set (Finset V)).Pairwise Disjoint := by intro e he f hf hef exact hMdis (hM0sub he) (hM0sub hf) hef
The union of the pairs in M₀ contains at most 2|M₀| vertices.
By Finset.card_biUnion_le, the size of the union ⋃ M₀ is bounded by the sum of the cardinalities of the sets in M₀. Since each set e ∈ M₀ has size 2, summing 2 over M₀ gives 2|M₀| by Finset.sum_le_sum, le_of_eq, and Nat.mul_comm.
uses
Finset.card_biUnion_le,Finset.sum_le_sum,le_of_eq,Nat.mul_commhave hUcard : (M0.biUnion id).card ≤ 2 * M0.card := by calc (M0.biUnion id).card ≤ ∑ e ∈ M0, e.card := Finset.card_biUnion_le _ ≤ ∑ _e ∈ M0, 2 := by apply Finset.sum_le_sum intro e he exact le_of_eq (hMprop e (hM0sub he)).1 _ = 2 * M0.card := by simp [Nat.mul_comm]
The common neighborhood N is not contained in ⋃ M₀.
If N ⊆ ⋃ M₀, then by Finset.card_le_card, |N| ≤ |⋃ M₀| ≤ 2|M₀| = 2(|P| - 1). But 2|P| ≤ |N| + 1 implies 2|P| ≤ 2|P| - 1, a contradiction by linear arithmetic.
uses
Finset.card_le_cardhave hnot : ¬N ⊆ M0.biUnion id := by intro hs have hh := Finset.card_le_card hs change 2 * P.card ≤ N.card + 1 at hlarge rw [hM0card] at hUcard omega
There exists a common neighbor w ∈ N not in ⋃ M₀, and every pair in M₀ avoids w while retaining its clique and neighborhood properties.
Since N is not a subset of ⋃ M₀, Finset.not_subset.mp yields a vertex w ∈ N with w ∉ ⋃ M₀. By Finset.mem_filter.mp, w is adjacent to both u and v. Each pair e ∈ M₀ inherits from M the property of consisting of two adjacent common neighbors of u and v. Furthermore, w ∉ e, since otherwise w ∈ ⋃ M₀ by Finset.mem_biUnion.mpr.
uses
Finset.not_subset.mp,Finset.mem_filter.mp,Finset.mem_biUnion.mprobtain ⟨w, hwN, hwU⟩ := Finset.not_subset.mp hnot have hw' : G.Adj u w ∧ G.Adj v w := (Finset.mem_filter.mp hwN).2 have hM0prop : ∀ e ∈ M0, e.card = 2 ∧ w ∉ e ∧ (∀ x ∈ e, G.Adj u x ∧ G.Adj v x) ∧ (∀ x ∈ e, ∀ y ∈ e, x ≠ y → G.Adj x y) := by intro e he have hp := hMprop e (hM0sub he) refine ⟨hp.1, ?_, hp.2⟩ intro hw apply hwU exact Finset.mem_biUnion.mpr ⟨e, he, hw⟩
The triangle packing number of G equals |M₀| + 1.
Since |M₀| = |P| - 1 and |P| is the triangle packing number of G, rearranging gives ν(G) = |M₀| + 1.
have hnum : simple_graph_triangle_packing_number G = M0.card + 1 := by rw [hM0card, ← hsize] omega
The triangle cover number of G is at most 2 * simple_graph_triangle_packing_number G.
Applying simple_graph_triangle_cover_of_near_full_common_matching to u, v, w, and M₀ yields τ(G) ≤ |M₀| + 3. Substituting |M₀| = |P| - 1 gives τ(G) ≤ |P| + 2. Because |P| ≥ 2, linear arithmetic gives |P| + 2 ≤ 2|P| = 2ν(G).
uses
simple_graph_triangle_cover_of_near_full_common_matchinghave hc := simple_graph_triangle_cover_of_near_full_common_matching G u v w M0 huv hw'.1 hw'.2 hM0prop hM0dis hnum rw [hM0card] at hc omega
simple_graph_common_neighbors_matching_of_avoided_packing- If a maximum triangle packing P avoids the edge uv, there exists a pairwise disjoint set M of 2-element cliques in the common neighborhood of u and v such that the number of common neighbors of u and v is at most |P| + |M|.
Finset.exists_subset_card_eq- If n ≤ |s| for a finite set s, there exists a subset t ⊆ s with |t| = n.
Finset.card_biUnion_le- The cardinality of a union of a family of finite sets is at most the sum of the cardinalities of the sets.
Finset.sum_le_sum- A sum indexed by a finite set is bounded above by the sum of pointwise upper bounds.
le_of_eq- An equality a = b implies the inequality a ≤ b.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
Finset.card_le_card- If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
Finset.not_subset.mp- If s is not a subset of t, there exists an element x ∈ s with x ∉ t.
Finset.mem_filter.mp- If an element belongs to the filter of a finite set by a predicate, it belongs to the set and satisfies the predicate.
Finset.mem_biUnion.mpr- If x belongs to some set in a family, then x belongs to the union of that family.
simple_graph_triangle_cover_of_near_full_common_matching- In a graph where edge uv has a common neighbor w and a disjoint matching M of size 2 in the common neighborhood disjoint from w, if the triangle packing number is |M| + 1, then the triangle cover number is at most |M| + 3.
- Linear arithmetic inequalities over ℕ (such as deducing |P| - 1 ≤ |M| from 2|P| ≤ |N| + 1 and |N| ≤ |P| + |M|) are discharged automatically by the omega tactic.
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_cover_of_avoided_near_high_codegree {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (u v : V) (P : Finset (Finset V)) (huv : G.Adj u v) (hcl : ∀ t ∈ P, G.IsNClique 3 t) (hmax : ∀ t : Finset V, G.IsNClique 3 t → ∃ s ∈ P, 2 ≤ (s ∩ t).card) (havoid : ∀ s ∈ P, ¬(u ∈ s ∧ v ∈ s)) (hsize : P.card = simple_graph_triangle_packing_number G) (hPtwo : 2 ≤ P.card) (hlarge : 2 * P.card ≤ ((Finset.univ : Finset V).filter (fun w => G.Adj u w ∧ G.Adj v w)).card + 1) : simple_graph_triangle_cover_number G ≤ 2 * simple_graph_triangle_packing_number G := by classical let N : Finset V := (Finset.univ : Finset V).filter (fun w => G.Adj u w ∧ G.Adj v w) obtain ⟨M, hMdis, hMprop, hMbound⟩ := simple_graph_common_neighbors_matching_of_avoided_packing G u v P huv hcl hmax havoid have hsubcard : P.card - 1 ≤ M.card := by omega obtain ⟨M0, hM0sub, hM0card⟩ := Finset.exists_subset_card_eq hsubcard have hM0dis : (M0 : Set (Finset V)).Pairwise Disjoint := by intro e he f hf hef exact hMdis (hM0sub he) (hM0sub hf) hef have hUcard : (M0.biUnion id).card ≤ 2 * M0.card := by calc (M0.biUnion id).card ≤ ∑ e ∈ M0, e.card := Finset.card_biUnion_le _ ≤ ∑ _e ∈ M0, 2 := by apply Finset.sum_le_sum intro e he exact le_of_eq (hMprop e (hM0sub he)).1 _ = 2 * M0.card := by simp [Nat.mul_comm] have hnot : ¬N ⊆ M0.biUnion id := by intro hs have hh := Finset.card_le_card hs change 2 * P.card ≤ N.card + 1 at hlarge rw [hM0card] at hUcard omega obtain ⟨w, hwN, hwU⟩ := Finset.not_subset.mp hnot have hw' : G.Adj u w ∧ G.Adj v w := (Finset.mem_filter.mp hwN).2 have hM0prop : ∀ e ∈ M0, e.card = 2 ∧ w ∉ e ∧ (∀ x ∈ e, G.Adj u x ∧ G.Adj v x) ∧ (∀ x ∈ e, ∀ y ∈ e, x ≠ y → G.Adj x y) := by intro e he have hp := hMprop e (hM0sub he) refine ⟨hp.1, ?_, hp.2⟩ intro hw apply hwU exact Finset.mem_biUnion.mpr ⟨e, he, hw⟩ have hnum : simple_graph_triangle_packing_number G = M0.card + 1 := by rw [hM0card, ← hsize] omega have hc := simple_graph_triangle_cover_of_near_full_common_matching G u v w M0 huv hw'.1 hw'.2 hM0prop hM0dis hnum rw [hM0card] at hc omega