simple_graph_matching_link_star_packing
Disjoint two-vertex edges in a vertex link yield a same-size edge-disjoint triangle packing through the vertex.
Statement
theorem simple_graph_matching_link_star_packing {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (z : V) (M : Finset (Finset V)) (hM : ∀ e ∈ M, e.card = 2 ∧ (∀ x ∈ e, G.Adj z x) ∧ (∀ x ∈ e, ∀ y ∈ e, x ≠ y → G.Adj x y)) (hdis : (M : Set (Finset V)).Pairwise Disjoint) : (∀ t ∈ M.image (fun e => insert z e), G.IsNClique 3 t) ∧ ((M.image (fun e => insert z e) : Finset (Finset V)) : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ (M.image (fun e => insert z e)).card = M.card
- 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- Used by 2
- simple_graph_triangle_cover_of_full_common_matchingIf an edge common-neighbor graph has a matching as large as the graph triangle packing number, the triangle cover number is at most the…
- 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…
The proof, explained
Given a collection M of pairwise disjoint edges in the link of a vertex z, we cone z over each edge e ∈ M to form triangles t = e ∪ {z}. Because z is adjacent to every vertex in each edge e and the vertices of e are adjacent to each other, with z ∉ e by graph irreflexivity, each such t is a 3-clique. Distinct triangles come from disjoint edges, so their intersection is contained in the singleton {z}, which means they share at most one vertex and are edge-disjoint. Finally, erasing z recovers the original edge e, proving the map e ↦ e ∪ {z} is injective and thus yields exactly |M| triangles.
The center vertex z does not belong to any edge in M.
Assuming for contradiction that z ∈ e for some e ∈ M, the hypothesis hM that every vertex in e is adjacent to z would imply that z is adjacent to itself (G.Adj z z). In a simple graph, adjacency is irreflexive (G.irrefl), which yields False.
classical have hnz : ∀ e ∈ M, z ∉ e := by intro e he hz have hz' := (hM e he).2.1 z hz exact G.irrefl hz'
Each set e ∪ {z} for e ∈ M is a 3-clique in G.
We take an arbitrary triangle t in the image of M under coning with z, so t = e ∪ {z} for some e ∈ M (by Finset.mem_image.mp). By SimpleGraph.isNClique_iff, t is a 3-clique if it is a clique and has cardinality 3. For the clique condition, we check all pairs of distinct vertices a, b ∈ e ∪ {z} (using Finset.mem_coe and Finset.mem_insert): the case a = z = b contradicts a ≠ b; if one vertex is z and the other is in e, they are adjacent by hM; if both lie in e, they are distinct vertices in e and are adjacent by hM. For the cardinality, since z ∉ e, the size of e ∪ {z} is |e| + 1 = 2 + 1 = 3 by Finset.card_insert_of_notMem and hM.
uses
Finset.mem_image.mp,SimpleGraph.isNClique_iff,Finset.mem_coe,Finset.mem_insert,Finset.card_insert_of_notMemconstructor · intro t ht obtain ⟨e, he, rfl⟩ := Finset.mem_image.mp ht rw [SimpleGraph.isNClique_iff] constructor · intro a ha b hb hab simp only [Finset.mem_coe, Finset.mem_insert] at ha hb rcases ha with rfl | ha <;> rcases hb with rfl | hb · exact (hab rfl).elim · exact (hM e he).2.1 b hb · exact ((hM e he).2.1 a ha).symm · exact (hM e he).2.2 a ha b hb hab · rw [Finset.card_insert_of_notMem (hnz e he), (hM e he).1]
Any two distinct triangles in the image share at most one vertex.
Let s = e ∪ {z} and t = f ∪ {z} be distinct triangles for e, f ∈ M (by Finset.mem_image.mp). Since s ≠ t, the edges e and f must be distinct (via congrArg), so the pairwise disjointness of M implies e and f are disjoint. We then show (e ∪ {z}) ∩ (f ∪ {z}) ⊆ {z}: any x in the intersection (Finset.mem_inter, Finset.mem_insert) must either equal z (putting it in {z} by Finset.mem_singleton) or belong to both e and f, which contradicts their disjointness (Finset.disjoint_left.mp, False.elim). By monotonicity of cardinality (Finset.card_le_card), |s ∩ t| ≤ |{z}| = 1.
uses
Finset.mem_image.mp,congrArg,Finset.mem_inter,Finset.mem_insert,Finset.mem_singleton,False.elim,Finset.disjoint_left.mp,Finset.card_le_cardconstructor · intro s hs t ht hst obtain ⟨e, he, rfl⟩ := Finset.mem_image.mp hs obtain ⟨f, hf, rfl⟩ := Finset.mem_image.mp ht have hef : e ≠ f := by intro h apply hst exact congrArg (fun q : Finset V => insert z q) h have hefdis : Disjoint e f := hdis he hf hef have hsub : insert z e ∩ insert z f ⊆ {z} := by intro x hx simp only [Finset.mem_inter, Finset.mem_insert] at hx simp only [Finset.mem_singleton] rcases hx.1 with rfl | hxe · rfl · rcases hx.2 with rfl | hxf · rfl · exact False.elim (Finset.disjoint_left.mp hefdis hxe hxf) exact (Finset.card_le_card hsub).trans (by simp)
The number of triangles equals |M|.
By Finset.card_image_iff.mpr, it suffices to prove that the coning map e ↦ e ∪ {z} is injective on M. Given e, f ∈ M with e ∪ {z} = f ∪ {z}, erasing z from both sets (via congrArg) preserves equality. Because z ∉ e and z ∉ f, removing z leaves e and f unchanged, so e = f.
uses
Finset.card_image_iff.mpr,congrArg· apply Finset.card_image_iff.mpr intro e he f hf heq have hh := congrArg (fun s : Finset V => s.erase z) heq simpa [hnz e he, hnz f hf] using hh
False.elim- From a contradiction (False), any conclusion follows.
Finset.card_image_iff.mpr- If a function is injective on a finite set S, the cardinality of the image f(S) equals the cardinality of S.
Finset.card_insert_of_notMem- Inserting an element a into a finite set s increases its size by 1, provided a ∉ s.
Finset.card_le_card- If s ⊆ t for finite sets, then |s| ≤ |t|.
Finset.disjoint_left.mp- If two sets are disjoint, no element of the first belongs to the second.
Finset.mem_coe- An element belongs to the set coercion of a finset if and only if it belongs to the finset.
Finset.mem_image.mp- If y belongs to f(S), there exists x ∈ S such that f(x) = y.
Finset.mem_insert- An element a belongs to s ∪ {b} if and only if a = b or a ∈ s.
Finset.mem_inter- An element belongs to s₁ ∩ s₂ if and only if it belongs to both s₁ and s₂.
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
congrArg- Applying a function to equal inputs yields equal outputs.
SimpleGraph.isNClique_iff- A finite set of vertices forms an n-clique in G if and only if it has cardinality n and every pair of distinct vertices in it is adjacent.
- Two triangles sharing at most one vertex is the standard combinatorial encoding of edge-disjointness for triangles, formalized here as `(s ∩ t).card ≤ 1`.
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_matching_link_star_packing {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (z : V) (M : Finset (Finset V)) (hM : ∀ e ∈ M, e.card = 2 ∧ (∀ x ∈ e, G.Adj z x) ∧ (∀ x ∈ e, ∀ y ∈ e, x ≠ y → G.Adj x y)) (hdis : (M : Set (Finset V)).Pairwise Disjoint) : (∀ t ∈ M.image (fun e => insert z e), G.IsNClique 3 t) ∧ ((M.image (fun e => insert z e) : Finset (Finset V)) : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ (M.image (fun e => insert z e)).card = M.card := by classical have hnz : ∀ e ∈ M, z ∉ e := by intro e he hz have hz' := (hM e he).2.1 z hz exact G.irrefl hz' constructor · intro t ht obtain ⟨e, he, rfl⟩ := Finset.mem_image.mp ht rw [SimpleGraph.isNClique_iff] constructor · intro a ha b hb hab simp only [Finset.mem_coe, Finset.mem_insert] at ha hb rcases ha with rfl | ha <;> rcases hb with rfl | hb · exact (hab rfl).elim · exact (hM e he).2.1 b hb · exact ((hM e he).2.1 a ha).symm · exact (hM e he).2.2 a ha b hb hab · rw [Finset.card_insert_of_notMem (hnz e he), (hM e he).1] constructor · intro s hs t ht hst obtain ⟨e, he, rfl⟩ := Finset.mem_image.mp hs obtain ⟨f, hf, rfl⟩ := Finset.mem_image.mp ht have hef : e ≠ f := by intro h apply hst exact congrArg (fun q : Finset V => insert z q) h have hefdis : Disjoint e f := hdis he hf hef have hsub : insert z e ∩ insert z f ⊆ {z} := by intro x hx simp only [Finset.mem_inter, Finset.mem_insert] at hx simp only [Finset.mem_singleton] rcases hx.1 with rfl | hxe · rfl · rcases hx.2 with rfl | hxf · rfl · exact False.elim (Finset.disjoint_left.mp hefdis hxe hxf) exact (Finset.card_le_card hsub).trans (by simp) · apply Finset.card_image_iff.mpr intro e he f hf heq have hh := congrArg (fun s : Finset V => s.erase z) heq simpa [hnz e he, hnz f hf] using hh