AFTD Auto-Formalizing Theoretical Domains

simple_graph_common_neighbors_matching_of_avoided_packing

theoremverified

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

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

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

    lines 16–21

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

    lines 22–30

    uses Finset.filter_subset, Finset.erase_subset

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

    lines 31–41

    uses Finset.mem_filter.mp

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

    lines 42–58

    uses Finset.card_filter_le, Finset.card_erase_of_mem, Finset.mem_image.mp

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

    lines 59–74

    uses Finset.mem_filter.mp, simple_graph_common_neighbor_meets_packing_star, Finset.mem_biUnion.mpr, Finset.mem_image.mpr, G.ne_of_adj

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

    line 75

    uses finset_rank_two_cover_matching_bound

      obtain ⟨M, hMB, hMdis, hMtwo, hbound⟩ := finset_rank_two_cover_matching_bound B hBsize
  7. Every 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.

    lines 76–85

    uses Finset.mem_image.mp, Finset.mem_filter.mp

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

    lines 86–89

    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

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