simple_graph_common_neighbors_matching_of_avoided_packing
For a triangle-maximal family of size p avoiding an edge with d common neighbors, their induced graph contains a matching of size at least d minus p.
Statement
theorem simple_graph_common_neighbors_matching_of_avoided_packing {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)) : ∃ M : Finset (Finset V), (M : Set (Finset V)).Pairwise Disjoint ∧ (∀ e ∈ M, e.card = 2 ∧ (∀ x ∈ e, G.Adj u x ∧ G.Adj v x) ∧ (∀ x ∈ e, ∀ y ∈ e, x ≠ y → G.Adj x y)) ∧ ((Finset.univ : Finset V).filter (fun w => G.Adj u w ∧ G.Adj v w)).card ≤ P.card + M.card
- 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 2
- finset_rank_two_cover_matching_boundFor any finite family of sets of size at most two, some pairwise-disjoint subfamily of two-element sets has size at least the size of the…
- simple_graph_common_neighbor_meets_packing_starFor a triangle-maximal family avoiding an edge, each common neighbor of the edge lies with one endpoint in a family triangle.
- Used by 1
- simple_graph_triangle_cover_of_avoided_near_high_codegreeIf a maximum triangle packing avoids an edge with at least twice the packing number minus one common neighbors and the packing number is…
The proof, explained
The proof projects the triangle packing P onto the set N of common neighbors of u and v by defining, for each triangle s ∈ P, the set F(s) of its vertices in N other than u or v. Because each triangle in P avoids containing both u and v simultaneously, each F(s) contains at most 2 vertices, forming a hypergraph B of rank at most 2. By a helper lemma, every common neighbor is covered by some F(s), so N ⊆ ⋃ B. Applying a general rank-2 hypergraph matching bound then extracts a pairwise disjoint matching M of edges in the subgraph induced by N satisfying |N| ≤ |B| + |M| ≤ |P| + |M|.
Define the common neighborhood N, the projection map F from triangles to subsets of N, and the family of hyperedges B.
We work classically and define N to be the set of common neighbors of u and v. For any triangle s, F(s) is formed by removing u (if u ∈ s) or v (if v ∈ s) and retaining only those vertices that lie in N; if neither u nor v is in s, F(s) is empty. Finally, B is defined as the image of the packing P under F.
classical let N : Finset V := (Finset.univ : Finset V).filter (fun w => G.Adj u w ∧ G.Adj v w) let F (s : Finset V) : Finset V := if u ∈ s then (s.erase u).filter (fun x => x ∈ N) else if v ∈ s then (s.erase v).filter (fun x => x ∈ N) else ∅ let B : Finset (Finset V) := P.image F
For every set s, F(s) ⊆ s.
We proceed by cases on whether u ∈ s or v ∈ s. When u ∈ s, F(s) is obtained by removing u from s and filtering by N, both of which are subset operations. The case v ∈ s is identical with v removed. If neither u nor v is in s, F(s) is empty, which is a subset of s.
uses
Finset.filter_subset,Finset.erase_subsethave hFsub : ∀ s, F s ⊆ s := by intro s by_cases hu : u ∈ s · simp only [F, hu, ↓reduceIte] exact (Finset.filter_subset _ _).trans (Finset.erase_subset _ _) · by_cases hv : v ∈ s · simp only [F, hu, hv, ↓reduceIte] exact (Finset.filter_subset _ _).trans (Finset.erase_subset _ _) · simp [F, hu, hv]
For every set s, F(s) ⊆ N.
By case analysis on whether u ∈ s or v ∈ s, any vertex retained in F(s) explicitly satisfies the filter predicate of belonging to N. If neither is in s, F(s) is the empty set, which is trivially contained in N.
uses
Finset.mem_filter.mphave hFN : ∀ s, F s ⊆ N := by intro s by_cases hu : u ∈ s · simp only [F, hu, ↓reduceIte] intro x hx exact (Finset.mem_filter.mp hx).2 · by_cases hv : v ∈ s · simp only [F, hu, hv, ↓reduceIte] intro x hx exact (Finset.mem_filter.mp hx).2 · simp [F, hu, hv]
Every hyperedge in B has cardinality at most 2.
For any triangle s ∈ P, |s| = 3. If u ∈ s, erasing u leaves a 2-element set, so filtering by N yields at most 2 elements. Symmetrically, if v ∈ s, erasing v and filtering yields at most 2 elements. If neither belongs to s, F(s) is empty. Since each hyperedge in B is F(s) for some s ∈ P, every element of B has size at most 2.
uses
Finset.card_filter_le,Finset.card_erase_of_mem,Finset.mem_image.mphave hFsize : ∀ s ∈ P, (F s).card ≤ 2 := by intro s hs by_cases hu : u ∈ s · simp only [F, hu, ↓reduceIte] have hh := Finset.card_filter_le (s.erase u) (fun x => x ∈ N) rw [Finset.card_erase_of_mem hu, (hcl s hs).card_eq] at hh omega · by_cases hv : v ∈ s · simp only [F, hu, hv, ↓reduceIte] have hh := Finset.card_filter_le (s.erase v) (fun x => x ∈ N) rw [Finset.card_erase_of_mem hv, (hcl s hs).card_eq] at hh omega · simp [F, hu, hv] have hBsize : ∀ e ∈ B, e.card ≤ 2 := by intro e he obtain ⟨s, hs, rfl⟩ := Finset.mem_image.mp he exact hFsize s hs
The hypergraph B covers all common neighbors: N ⊆ ⋃ B.
For any common neighbor w ∈ N, the vertices u, v, w form a triangle in G. By simple_graph_common_neighbor_meets_packing_star, some triangle s ∈ P contains w and also contains either u or v. If u ∈ s, then since w is adjacent to u, w ≠ u; thus w ∈ s \ {u}, and since w ∈ N, w ∈ F(s) ∈ B. If instead v ∈ s, the hypothesis havoid ensures u ∉ s, and since w is adjacent to v, w ≠ v; thus again w ∈ F(s) ∈ B.
uses
Finset.mem_filter.mp,simple_graph_common_neighbor_meets_packing_star,Finset.mem_biUnion.mpr,Finset.mem_image.mpr,G.ne_of_adjhave hNsub : N ⊆ B.biUnion id := by intro w hw have hwN := (Finset.mem_filter.mp hw).2 obtain ⟨s, hs, hws, hus | hvs⟩ := simple_graph_common_neighbor_meets_packing_star G u v P huv hmax havoid w hwN.1 hwN.2 · apply Finset.mem_biUnion.mpr refine ⟨F s, Finset.mem_image.mpr ⟨s, hs, rfl⟩, ?_⟩ have hwu : w ≠ u := (G.ne_of_adj hwN.1).symm simp [F, hus, hws, hwu, hw] · apply Finset.mem_biUnion.mpr refine ⟨F s, Finset.mem_image.mpr ⟨s, hs, rfl⟩, ?_⟩ have hwv : w ≠ v := (G.ne_of_adj hwN.2).symm have hunot : u ∉ s := by intro hu exact havoid s hs ⟨hu, hvs⟩ simp [F, hunot, hvs, hws, hwv, hw]
There exists a matching M ⊆ B of pairwise disjoint 2-element sets satisfying |⋃ B| ≤ |B| + |M|.
Applying finset_rank_two_cover_matching_bound to the hypergraph B (whose edges all have size at most 2) provides a matching M ⊆ B consisting of pairwise disjoint pairs such that the total number of vertices covered by B is bounded by |B| + |M|.
uses
finset_rank_two_cover_matching_boundobtain ⟨M, hMB, hMdis, hMtwo, hbound⟩ := finset_rank_two_cover_matching_bound B hBsizeEvery edge e ∈ M consists of two adjacent common neighbors of u and v.
We show that M meets all conditions for the desired matching. M is pairwise disjoint and each e ∈ M has cardinality 2. Since M ⊆ B, every e ∈ M equals F(s) for some triangle s ∈ P. Since F(s) ⊆ N, all vertices in e are common neighbors of u and v. Furthermore, since F(s) ⊆ s and s is a 3-clique in G, any two distinct vertices in e are adjacent in G.
uses
Finset.mem_image.mp,Finset.mem_filter.mprefine ⟨M, hMdis, ?_, ?_⟩ · intro e he have heB : e ∈ B := hMB he obtain ⟨s, hs, rfl⟩ := Finset.mem_image.mp heB refine ⟨hMtwo _ he, ?_, ?_⟩ · intro x hx have hxN := hFN s hx exact (Finset.mem_filter.mp hxN).2 · intro x hx y hy hxy exact (hcl s hs).isClique (hFsub s hx) (hFsub s hy) hxy
The common neighborhood satisfies |N| ≤ |P| + |M|.
Because N ⊆ ⋃ B, we have |N| ≤ |⋃ B|. Combining this with the matching bound |⋃ B| ≤ |B| + |M| and the fact that |B| = |P.image F| ≤ |P|, linear arithmetic deduces that |N| ≤ |P| + |M|.
uses
Finset.card_le_card,Finset.card_image_le· have hNcard := Finset.card_le_card hNsub have hBcard : B.card ≤ P.card := Finset.card_image_le change N.card ≤ P.card + M.card omega
Finset.filter_subset- Filtering a finite set by a predicate produces a subset of the original set.
Finset.erase_subset- Removing an element from a finite set produces a subset of the original set.
Finset.mem_filter.mp- If an element belongs to the filter of a finite set by a predicate, then it belongs to the set and satisfies the predicate.
Finset.card_filter_le- The cardinality of a filtered finite set is at most the cardinality of the original set.
Finset.card_erase_of_mem- Removing an element that belongs to a finite set decreases its cardinality by one.
Finset.mem_image.mp- If an element belongs to the image of a finite set under a function, it is the image of some element of that set.
simple_graph_common_neighbor_meets_packing_star- For an edge uv and a maximal triangle packing P avoiding uv, every common neighbor of u and v belongs to some triangle in P containing u or v.
Finset.mem_biUnion.mpr- If an element belongs to the image set of some element of a collection, then it belongs to the union of the collection.
Finset.mem_image.mpr- If an element is the image of an element of a finite set under a function, then it belongs to the image of that set.
G.ne_of_adj- In a simple graph, two adjacent vertices are distinct.
finset_rank_two_cover_matching_bound- In any hypergraph of edges of size at most 2, there is a matching of pairwise disjoint 2-element edges such that the number of vertices covered is at most the number of hyperedges plus the size of the matching.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is less than or equal to the cardinality of the other.
Finset.card_image_le- The image of a finite set under any function has cardinality at most that of the original set.
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_common_neighbors_matching_of_avoided_packing {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)) : ∃ M : Finset (Finset V), (M : Set (Finset V)).Pairwise Disjoint ∧ (∀ e ∈ M, e.card = 2 ∧ (∀ x ∈ e, G.Adj u x ∧ G.Adj v x) ∧ (∀ x ∈ e, ∀ y ∈ e, x ≠ y → G.Adj x y)) ∧ ((Finset.univ : Finset V).filter (fun w => G.Adj u w ∧ G.Adj v w)).card ≤ P.card + M.card := by classical let N : Finset V := (Finset.univ : Finset V).filter (fun w => G.Adj u w ∧ G.Adj v w) let F (s : Finset V) : Finset V := if u ∈ s then (s.erase u).filter (fun x => x ∈ N) else if v ∈ s then (s.erase v).filter (fun x => x ∈ N) else ∅ let B : Finset (Finset V) := P.image F have hFsub : ∀ s, F s ⊆ s := by intro s by_cases hu : u ∈ s · simp only [F, hu, ↓reduceIte] exact (Finset.filter_subset _ _).trans (Finset.erase_subset _ _) · by_cases hv : v ∈ s · simp only [F, hu, hv, ↓reduceIte] exact (Finset.filter_subset _ _).trans (Finset.erase_subset _ _) · simp [F, hu, hv] have hFN : ∀ s, F s ⊆ N := by intro s by_cases hu : u ∈ s · simp only [F, hu, ↓reduceIte] intro x hx exact (Finset.mem_filter.mp hx).2 · by_cases hv : v ∈ s · simp only [F, hu, hv, ↓reduceIte] intro x hx exact (Finset.mem_filter.mp hx).2 · simp [F, hu, hv] have hFsize : ∀ s ∈ P, (F s).card ≤ 2 := by intro s hs by_cases hu : u ∈ s · simp only [F, hu, ↓reduceIte] have hh := Finset.card_filter_le (s.erase u) (fun x => x ∈ N) rw [Finset.card_erase_of_mem hu, (hcl s hs).card_eq] at hh omega · by_cases hv : v ∈ s · simp only [F, hu, hv, ↓reduceIte] have hh := Finset.card_filter_le (s.erase v) (fun x => x ∈ N) rw [Finset.card_erase_of_mem hv, (hcl s hs).card_eq] at hh omega · simp [F, hu, hv] have hBsize : ∀ e ∈ B, e.card ≤ 2 := by intro e he obtain ⟨s, hs, rfl⟩ := Finset.mem_image.mp he exact hFsize s hs have hNsub : N ⊆ B.biUnion id := by intro w hw have hwN := (Finset.mem_filter.mp hw).2 obtain ⟨s, hs, hws, hus | hvs⟩ := simple_graph_common_neighbor_meets_packing_star G u v P huv hmax havoid w hwN.1 hwN.2 · apply Finset.mem_biUnion.mpr refine ⟨F s, Finset.mem_image.mpr ⟨s, hs, rfl⟩, ?_⟩ have hwu : w ≠ u := (G.ne_of_adj hwN.1).symm simp [F, hus, hws, hwu, hw] · apply Finset.mem_biUnion.mpr refine ⟨F s, Finset.mem_image.mpr ⟨s, hs, rfl⟩, ?_⟩ have hwv : w ≠ v := (G.ne_of_adj hwN.2).symm have hunot : u ∉ s := by intro hu exact havoid s hs ⟨hu, hvs⟩ simp [F, hunot, hvs, hws, hwv, hw] obtain ⟨M, hMB, hMdis, hMtwo, hbound⟩ := finset_rank_two_cover_matching_bound B hBsize refine ⟨M, hMdis, ?_, ?_⟩ · intro e he have heB : e ∈ B := hMB he obtain ⟨s, hs, rfl⟩ := Finset.mem_image.mp heB refine ⟨hMtwo _ he, ?_, ?_⟩ · intro x hx have hxN := hFN s hx exact (Finset.mem_filter.mp hxN).2 · intro x hx y hy hxy exact (hcl s hs).isClique (hFsub s hx) (hFsub s hy) hxy · have hNcard := Finset.card_le_card hNsub have hBcard : B.card ≤ P.card := Finset.card_image_le change N.card ≤ P.card + M.card omega