AFTD Auto-Formalizing Theoretical Domains

simple_graph_independent_parts_injective_matching

theoremverified

In a finite graph with no independent k-set, let A, B and P be disjoint independent sets, where |A|=|B|, |A|+|P|+1=k, and P has no edges to A or B. Then A can be matched injectively into B along graph edges.

Statement

theorem simple_graph_independent_parts_injective_matching {α : Type*} [Fintype α] [DecidableEq α] (G : SimpleGraph α) [DecidableRel G.Adj]
    (k : ℕ) (hfree : Gᶜ.CliqueFree k)
    (A B P : Finset α) (hA : G.IsIndepSet A) (hB : G.IsIndepSet B)
    (hP : G.IsIndepSet P) (hab : Disjoint A B) (habp : Disjoint (A ∪ B) P)
    (hpa : ∀ p ∈ P, ∀ x ∈ A ∪ B, ¬ G.Adj p x)
    (hcard : A.card = B.card) (hk : A.card + P.card + 1 = k) :
    ∃ f : {x // x ∈ A} → α, Function.Injective f ∧
      ∀ x, f x ∈ B ∧ G.Adj x (f x)
Source
General matching consequence for independent sets, motivated by the five-cycle link constraints for OP-926.
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

Lean source view module on GitHub

theorem simple_graph_independent_parts_injective_matching {α : Type*} [Fintype α] [DecidableEq α] (G : SimpleGraph α) [DecidableRel G.Adj]
    (k : ℕ) (hfree : Gᶜ.CliqueFree k)
    (A B P : Finset α) (hA : G.IsIndepSet A) (hB : G.IsIndepSet B)
    (hP : G.IsIndepSet P) (hab : Disjoint A B) (habp : Disjoint (A ∪ B) P)
    (hpa : ∀ p ∈ P, ∀ x ∈ A ∪ B, ¬ G.Adj p x)
    (hcard : A.card = B.card) (hk : A.card + P.card + 1 = k) :
    ∃ f : {x // x ∈ A} → α, Function.Injective f ∧
      ∀ x, f x ∈ B ∧ G.Adj x (f x) := by
  classical
  let L : {x // x ∈ A} → Finset α := fun x => B.filter (G.Adj x)
  have hall : ∀ u : Finset {x // x ∈ A}, u.card ≤ (u.biUnion L).card := by
    intro u
    let J : Finset α := u.image Subtype.val
    let t : Finset α := B.filter (fun y => ∀ x ∈ J, ¬ G.Adj x y)
    have hJ : J.card = u.card := Finset.card_image_of_injective u Subtype.val_injective
    have hJsub : J ⊆ A := by
      intro x hx
      obtain ⟨y, hy, rfl⟩ := Finset.mem_image.mp hx
      exact y.property
    have hjt : Disjoint J t := by
      apply Finset.disjoint_left.mpr
      intro x hx hy
      exact (Finset.disjoint_left.mp hab) (hJsub hx) ((Finset.mem_filter.mp hy).1)
    have hjtp : Disjoint (J ∪ t) P := by
      apply Finset.disjoint_left.mpr
      intro x hx hp
      apply (Finset.disjoint_left.mp habp) _ hp
      rcases Finset.mem_union.mp hx with hx | hx
      · exact Finset.mem_union_left B (hJsub hx)
      · exact Finset.mem_union_right A ((Finset.mem_filter.mp hx).1)
    have hind : G.IsIndepSet ((J ∪ t) ∪ P : Finset α) := by
      intro x hx y hy hxy
      simp only [Finset.coe_union, Set.mem_union] at hx hy
      rcases hx with (hx | hx) | hx <;> rcases hy with (hy | hy) | hy
      · exact hA (hJsub hx) (hJsub hy) hxy
      · exact fun he => ((Finset.mem_filter.mp hy).2 x hx) he
      · exact fun he => (hpa y hy x (Finset.mem_union_left B (hJsub hx))) he.symm
      · exact fun he => ((Finset.mem_filter.mp hx).2 y hy) he.symm
      · exact hB ((Finset.mem_filter.mp hx).1) ((Finset.mem_filter.mp hy).1) hxy
      · exact fun he => (hpa y hy x (Finset.mem_union_right A ((Finset.mem_filter.mp hx).1))) he.symm
      · exact fun he => (hpa x hx y (Finset.mem_union_left B (hJsub hy))) he
      · exact fun he => (hpa x hx y (Finset.mem_union_right A ((Finset.mem_filter.mp hy).1))) he
      · exact hP hx hy hxy
    have hbound : J.card + t.card + P.card < k := by
      by_contra hn
      have hle : k ≤ ((J ∪ t) ∪ P).card := by
        rw [Finset.card_union_of_disjoint hjtp, Finset.card_union_of_disjoint hjt]
        omega
      obtain ⟨v, hv, hvc⟩ := Finset.exists_subset_card_eq hle
      apply hfree v
      apply (Gᶜ.isNClique_iff).2
      constructor
      · rw [SimpleGraph.isClique_compl]
        exact hind.mono (by exact_mod_cast hv)
      · exact hvc
    have hpartition : t ∪ u.biUnion L = B := by
      ext y
      simp only [t, Finset.mem_union, Finset.mem_filter, Finset.mem_biUnion, L, J,
        Finset.mem_image]
      constructor
      · rintro (⟨hy, _⟩ | ⟨x, hx, hy, _⟩) <;> exact hy
      · intro hy
        by_cases he : ∃ x ∈ u, G.Adj x y
        · right
          obtain ⟨x, hx, ha⟩ := he
          exact ⟨x, hx, hy, ha⟩
        · left
          refine ⟨hy, ?_⟩
          intro x hx
          obtain ⟨z, hz, rfl⟩ := hx
          intro ha
          exact he ⟨z, hz, ha⟩
    have hdisj : Disjoint t (u.biUnion L) := by
      apply Finset.disjoint_left.mpr
      intro y hyt hyL
      obtain ⟨_, hya⟩ := Finset.mem_filter.mp hyt
      obtain ⟨x, hx, hxl⟩ := Finset.mem_biUnion.mp hyL
      have hxJ : (x : α) ∈ J := Finset.mem_image.mpr ⟨x, hx, rfl⟩
      exact hya x hxJ ((Finset.mem_filter.mp hxl).2)
    have hc := congrArg Finset.card hpartition
    rw [Finset.card_union_of_disjoint hdisj] 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