AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_free_independent_neighborhood_matching

theoremverified

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
Used by 1

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.

  1. 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).

    lines 7–9

      classical
      let L : {x // x ∈ s} → Finset α := fun x =>
        (G.neighborFinset v).filter (fun w => G.Adj w x)
  2. 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.

    lines 10–19

    uses Finset.card_image_of_injective, Subtype.val_injective, Finset.coe_image, Set.mem_image, Finset.mem_coe

      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
  3. 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.

    lines 20–23

    uses simple_graph_triangle_free_independent_neighborhood_cover

        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])
  4. 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).

    lines 24–40

    uses Finset.mem_union, Finset.mem_filter, SimpleGraph.mem_neighborFinset, Finset.mem_biUnion, Finset.mem_image

        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⟩
  5. 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.

    lines 41–47

    uses Finset.disjoint_left.mpr, Finset.mem_filter.mp, Finset.mem_biUnion.mp, Finset.mem_image.mpr

        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)
  6. 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.

    lines 48–52

    uses congrArg, Finset.card_union_of_disjoint

        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
  7. 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.

    lines 53–56

    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.

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

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
See it in the graphDiscuss this resultChallenge it