simple_graph_triangle_free_independent_neighborhood_matching
In a finite triangle-free graph with no independent set of size k, if v has degree k − 1 and s is an independent set consisting of non-neighbors of v, then the vertices of s can be matched injectively to distinct neighbors of v that they are adjacent to.
Statement
theorem simple_graph_triangle_free_independent_neighborhood_matching {α : Type*} [Fintype α] (G : SimpleGraph α) [DecidableRel G.Adj] (k : ℕ) (htri : G.CliqueFree 3) (hfree : Gᶜ.CliqueFree k) (v : α) (hdegree : G.degree v + 1 = k) (s : Finset α) (hs : G.IsIndepSet s) (hns : ∀ x ∈ s, ¬ G.Adj v x) : ∃ f : {x // x ∈ s} → α, Function.Injective f ∧ ∀ x, G.Adj v (f x) ∧ G.Adj (f x) x
- Source
- Neighborhood gluing for OP-926, https://arxiv.org/abs/2401.00392; the matching form follows from the independent-set covering condition.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- simple_graph_triangle_free_independent_neighborhood_coverIn a finite triangle-free graph with no independent set of size k, let s be an independent set all of whose vertices are non-neighbors of…
- Used by 1
- simple_graph_triangle_free_private_neighborhood_neighbor_uniqueIn a finite triangle-free graph with no independent k-set, if v has degree k − 1 and vertices x and y both have w as their only neighbor…
The proof, explained
The theorem is proved by applying Hall's Marriage Theorem to find an injective choice of distinct neighbors in N(v) for the vertices of s. For an arbitrary subset u ⊆ s, let J be its vertex set in G and let t be the set of neighbors of v that have no edges to J. A previously proven cover lemma gives |u| + |t| = |J| + |t| < k, while N(v) partitions disjointly into t and the candidate neighbor sets ⋃_{x ∈ u} L(x), giving |t| + |⋃_{x ∈ u} L(x)| = deg(v) = k - 1. Together these yield Hall's condition |u| ≤ |⋃_{x ∈ u} L(x)|, from which Hall's theorem produces the desired injective matching.
Define the candidate target neighbor set L(x) for each vertex x in s.
For each vertex x in s, define L(x) to be the set of neighbors of v that are adjacent to x, that is, L(x) = N(v) ∩ N(x).
classical let L : {x // x ∈ s} → Finset α := fun x => (G.neighborFinset v).filter (fun w => G.Adj w x)
For any subset u of s, represent it as a set J of vertices with |J| = |u| and J ⊆ s, and define the set t of neighbors of v non-adjacent to J.
To check Hall's marriage condition, consider an arbitrary subset u ⊆ s. Let J be the image of u in the ambient graph under the subtype inclusion. Since inclusion is injective, |J| = |u|, and every element of J is in s. Let t be the set of neighbors of v that have no edges to J.
uses
Finset.card_image_of_injective,Subtype.val_injective,Finset.coe_image,Set.mem_image,Finset.mem_coehave hall : ∀ u : Finset {x // x ∈ s}, u.card ≤ (u.biUnion L).card := by intro u let J : Finset α := u.image Subtype.val let t : Finset α := (G.neighborFinset v).filter (fun w => ∀ x ∈ J, ¬ G.Adj w x) have hJ : J.card = u.card := Finset.card_image_of_injective u Subtype.val_injective have hJsub : (J : Set α) ⊆ s := by intro x hx simp only [J, Finset.coe_image, Set.mem_image, Finset.mem_coe] at hx obtain ⟨y, hy, rfl⟩ := hx exact y.property
The sum of |J| and |t| is strictly less than k.
Because s is an independent set consisting of non-neighbors of v, the subset J ⊆ s is also an independent set of non-neighbors of v. Applying simple_graph_triangle_free_independent_neighborhood_cover to J and t gives |J| + |t| < k.
uses
simple_graph_triangle_free_independent_neighborhood_coverhave hbound := simple_graph_triangle_free_independent_neighborhood_cover G k htri hfree v J t (hs.mono hJsub) (fun x hx => hns x (hJsub hx)) (by intro w simp [t])
The neighborhood N(v) is the union of t and the union of candidate neighbor sets L(x) for x in u.
Both t and each L(x) consist of neighbors of v. Conversely, any neighbor w of v either has no neighbor in u (so w belongs to t) or has a neighbor x in u (so w belongs to L(x) and hence to the union over u).
uses
Finset.mem_union,Finset.mem_filter,SimpleGraph.mem_neighborFinset,Finset.mem_biUnion,Finset.mem_imagehave hpartition : t ∪ u.biUnion L = G.neighborFinset v := by ext w simp only [t, Finset.mem_union, Finset.mem_filter, SimpleGraph.mem_neighborFinset, Finset.mem_biUnion, L, J, Finset.mem_image] constructor · rintro (⟨hw, _⟩ | ⟨x, hx, hw, _⟩) <;> exact hw · intro hw by_cases he : ∃ x ∈ u, G.Adj w x · right obtain ⟨x, hx, ha⟩ := he exact ⟨x, hx, hw, ha⟩ · left refine ⟨hw, ?_⟩ intro x hx obtain ⟨y, hy, rfl⟩ := hx intro ha exact he ⟨y, hy, ha⟩
The sets t and the union of L(x) for x in u are disjoint.
If a vertex w belonged to both sets, it would be non-adjacent to all vertices of J (by definition of t), yet adjacent to some x in u ⊆ J (by definition of L(x)), a contradiction.
uses
Finset.disjoint_left.mpr,Finset.mem_filter.mp,Finset.mem_biUnion.mp,Finset.mem_image.mprhave hdisj : Disjoint t (u.biUnion L) := by apply Finset.disjoint_left.mpr intro w hwt hwL obtain ⟨_, hwa⟩ := Finset.mem_filter.mp hwt obtain ⟨x, hx, hxl⟩ := Finset.mem_biUnion.mp hwL have hxJ : (x : α) ∈ J := Finset.mem_image.mpr ⟨x, hx, rfl⟩ exact hwa x hxJ ((Finset.mem_filter.mp hxl).2)
Hall's marriage condition |u| ≤ |⋃_{x ∈ u} L(x)| holds for every subset u of s.
Because t and ⋃_{x ∈ u} L(x) partition N(v) into disjoint sets, their cardinalities sum to |N(v)| = deg(v) = k - 1. Combining this with |u| + |t| = |J| + |t| < k shows that |u| ≤ |⋃_{x ∈ u} L(x)| by linear arithmetic.
uses
congrArg,Finset.card_union_of_disjointhave hc := congrArg Finset.card hpartition rw [Finset.card_union_of_disjoint hdisj] at hc change t.card + (u.biUnion L).card = G.degree v at hc rw [hJ] at hbound omega
There exists an injective matching from s into N(v) connecting each vertex to its match.
By Hall's Marriage Theorem (Finset.all_card_le_biUnion_card_iff_existsInjective'), the condition verified in the previous step guarantees an injective function f : s → V(G) such that f(x) ∈ L(x) for each x ∈ s. By definition of L(x), each f(x) is adjacent to v and to x.
uses
Finset.all_card_le_biUnion_card_iff_existsInjective'obtain ⟨f, hfinj, hfmem⟩ := (Finset.all_card_le_biUnion_card_iff_existsInjective' L).mp hall refine ⟨f, hfinj, ?_⟩ intro x simpa [L] using hfmem x
Finset.card_image_of_injective- An injective function preserves the cardinality of a finite set under image.
Subtype.val_injective- The inclusion from a subtype to its ambient type is injective.
Finset.coe_image- Coercing the image of a finite set to a set equals the set-theoretic image of the coerced finite set.
Set.mem_image- An element is in the image of a set under f if and only if it is the image of some element in the set.
Finset.mem_coe- Membership in a finite set coerced to a set is equivalent to membership in the finite set.
simple_graph_triangle_free_independent_neighborhood_cover- In a triangle-free graph with no independent set of size k, if s is an independent set of non-neighbors of v, and t is the set of neighbors of v non-adjacent to every vertex in s, then |s| + |t| < k.
Finset.mem_union- An element belongs to the union of two finite sets if and only if it belongs to at least one of them.
Finset.mem_filter- An element belongs to a filtered finite set if and only if it belongs to the set and satisfies the predicate.
SimpleGraph.mem_neighborFinset- A vertex belongs to the neighborhood finset of v if and only if it is adjacent to v.
Finset.mem_biUnion- An element belongs to an indexed union of finite sets if and only if it belongs to the component set for some index.
Finset.mem_image- An element belongs to the image of a finite set if and only if it is the image of some element in that set.
Finset.disjoint_left.mpr- Two finite sets are disjoint if no element of the first belongs to the second.
Finset.mem_filter.mp- If an element belongs to a filtered finite set, then it belongs to the underlying set and satisfies the predicate.
Finset.mem_biUnion.mp- If an element belongs to an indexed union of finite sets, then it belongs to the component set for some index.
Finset.mem_image.mpr- If an element is the image of some member of a finite set, it belongs to the image of that set.
congrArg- Applying the same function to equal arguments produces equal values.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.all_card_le_biUnion_card_iff_existsInjective'- Hall's Marriage Theorem for finite sets: a family of sets admits an injective choice of representatives if and only if the union of any subfamily has at least as many elements as the subfamily itself.
- The proof maps the collection u of subtype elements {x // x ∈ s} to a set J of vertices in the ambient graph α to apply the neighborhood cover theorem.
- The final cardinality comparison for Hall's condition relies on the automated linear arithmetic solver omega.
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.
theorem simple_graph_triangle_free_independent_neighborhood_matching {α : Type*} [Fintype α] (G : SimpleGraph α) [DecidableRel G.Adj] (k : ℕ) (htri : G.CliqueFree 3) (hfree : Gᶜ.CliqueFree k) (v : α) (hdegree : G.degree v + 1 = k) (s : Finset α) (hs : G.IsIndepSet s) (hns : ∀ x ∈ s, ¬ G.Adj v x) : ∃ f : {x // x ∈ s} → α, Function.Injective f ∧ ∀ x, G.Adj v (f x) ∧ G.Adj (f x) x := by classical let L : {x // x ∈ s} → Finset α := fun x => (G.neighborFinset v).filter (fun w => G.Adj w x) have hall : ∀ u : Finset {x // x ∈ s}, u.card ≤ (u.biUnion L).card := by intro u let J : Finset α := u.image Subtype.val let t : Finset α := (G.neighborFinset v).filter (fun w => ∀ x ∈ J, ¬ G.Adj w x) have hJ : J.card = u.card := Finset.card_image_of_injective u Subtype.val_injective have hJsub : (J : Set α) ⊆ s := by intro x hx simp only [J, Finset.coe_image, Set.mem_image, Finset.mem_coe] at hx obtain ⟨y, hy, rfl⟩ := hx exact y.property have hbound := simple_graph_triangle_free_independent_neighborhood_cover G k htri hfree v J t (hs.mono hJsub) (fun x hx => hns x (hJsub hx)) (by intro w simp [t]) have hpartition : t ∪ u.biUnion L = G.neighborFinset v := by ext w simp only [t, Finset.mem_union, Finset.mem_filter, SimpleGraph.mem_neighborFinset, Finset.mem_biUnion, L, J, Finset.mem_image] constructor · rintro (⟨hw, _⟩ | ⟨x, hx, hw, _⟩) <;> exact hw · intro hw by_cases he : ∃ x ∈ u, G.Adj w x · right obtain ⟨x, hx, ha⟩ := he exact ⟨x, hx, hw, ha⟩ · left refine ⟨hw, ?_⟩ intro x hx obtain ⟨y, hy, rfl⟩ := hx intro ha exact he ⟨y, hy, ha⟩ have hdisj : Disjoint t (u.biUnion L) := by apply Finset.disjoint_left.mpr intro w hwt hwL obtain ⟨_, hwa⟩ := Finset.mem_filter.mp hwt obtain ⟨x, hx, hxl⟩ := Finset.mem_biUnion.mp hwL have hxJ : (x : α) ∈ J := Finset.mem_image.mpr ⟨x, hx, rfl⟩ exact hwa x hxJ ((Finset.mem_filter.mp hxl).2) have hc := congrArg Finset.card hpartition rw [Finset.card_union_of_disjoint hdisj] at hc change t.card + (u.biUnion L).card = G.degree v at hc rw [hJ] at hbound omega obtain ⟨f, hfinj, hfmem⟩ := (Finset.all_card_le_biUnion_card_iff_existsInjective' L).mp hall refine ⟨f, hfinj, ?_⟩ intro x simpa [L] using hfmem x