AFTD Auto-Formalizing Theoretical Domains

finite_vertex_family_edge_packing_cover_bridge

theoremverified

Encoding each member of a finite vertex-set family of size at least two by its non-diagonal pairs preserves the family size, converts vertex-intersection-at-most-one packings into disjoint set packings, and converts nondiagnonal edge covers into point covers.

Statement

theorem finite_vertex_family_edge_packing_cover_bridge {V : Type*} [DecidableEq V]
    (P : Finset (Finset V)) (C : Finset (Sym2 V))
    (hsize : ∀ t ∈ P, 2 ≤ t.card) (hC : ∀ e ∈ C, ¬ e.IsDiag) :
    (P.image finite_vertex_set_edge_encoding).card = P.card ∧
    (((P.image finite_vertex_set_edge_encoding : Finset (Finset (Sym2 V))) :
        Set (Finset (Sym2 V))).Pairwise Disjoint ↔
      (P : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1)) ∧
    ((∀ F ∈ P.image finite_vertex_set_edge_encoding, ¬ Disjoint F C) ↔
      (∀ t ∈ P, ∃ e ∈ C, ∀ x ∈ e, x ∈ t))
Source
Bridge for the published separator reduction, https://www.cs.tau.ac.il/~krivelev/2.pdf, Lemma 5.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • finite_vertex_set_edge_encodingThe non-diagonal unordered vertex pairs spanned by a finite vertex set.
  • FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via ZMod.
Used by 3

The proof, explained

The theorem establishes an exact isomorphism between hypergraph packing and covering on a family of vertex sets P (with member sizes at least 2) and standard set packing and hitting sets over edges. By mapping each vertex set s to the complete graph edge set on s (all non-diagonal unordered pairs), the encoding is injective and preserves the family cardinality. Two edge encodings are disjoint if and only if the corresponding vertex sets intersect in at most one vertex, converting a nearly-disjoint packing problem into a disjoint set packing problem. Furthermore, a set of edges C intersects an edge encoding if and only if C contains an edge entirely supported on the corresponding vertex set, converting an edge cover into a hitting set.

  1. An unordered pair s(a, b) belongs to the edge encoding of a vertex set s if and only if a ∈ s, b ∈ s, and a ≠ b.

    By unfolding the definition of the edge encoding as the set of pairs from s that are not diagonal, and rewriting non-diagonality as a ≠ b, the simplifier reduces membership to a ∈ s ∧ b ∈ s ∧ a ≠ b.

    lines 1–4

    uses Sym2.mk_isDiag_iff, and_assoc

    private theorem in519_mk_mem_edges {V : Type*} [DecidableEq V] (s : Finset V) (a b : V) :
        s(a,b) ∈ finite_vertex_set_edge_encoding s ↔ a ∈ s ∧ b ∈ s ∧ a ≠ b := by
      simp [finite_vertex_set_edge_encoding, Sym2.mk_isDiag_iff, and_assoc]
    
  2. If the edge encodings of s and t are disjoint, then |s ∩ t| ≤ 1.

    We argue by contradiction. If |s ∩ t| > 1, the intersection contains two distinct vertices a and b. Then the non-diagonal edge s(a, b) belongs to both edge encodings, contradicting their disjointness.

    lines 5–16

    uses Finset.one_lt_card.mp, Finset.mem_inter.mp, in519_mk_mem_edges, Finset.disjoint_left.mp

    private theorem in519_edges_disjoint_iff_inter_small {V : Type*} [DecidableEq V] (s t : Finset V) :
        Disjoint (finite_vertex_set_edge_encoding s) (finite_vertex_set_edge_encoding t) ↔ (s ∩ t).card ≤ 1 := by
      constructor
      · intro h
        by_contra hn
        have hgt : 1 < (s ∩ t).card := by omega
        obtain ⟨a,ha,b,hb,hab⟩ := Finset.one_lt_card.mp hgt
        have ha' := Finset.mem_inter.mp ha
        have hb' := Finset.mem_inter.mp hb
        have he₁ : s(a,b) ∈ finite_vertex_set_edge_encoding s := (in519_mk_mem_edges s a b).mpr ⟨ha'.1,hb'.1,hab⟩
        have he₂ : s(a,b) ∈ finite_vertex_set_edge_encoding t := (in519_mk_mem_edges t a b).mpr ⟨ha'.2,hb'.2,hab⟩
        exact Finset.disjoint_left.mp h he₁ he₂
  3. If |s ∩ t| ≤ 1, then the edge encodings of s and t are disjoint.

    Suppose an edge e belongs to both edge encodings. Writing e as an unordered pair s(a, b), both a and b are distinct vertices belonging to both s and t, so a, b ∈ s ∩ t with a ≠ b. This forces |s ∩ t| > 1, contradicting the hypothesis |s ∩ t| ≤ 1.

    lines 17–27

    uses Finset.disjoint_left.mpr, Sym2.ind, in519_mk_mem_edges, Finset.one_lt_card.mpr, Finset.mem_inter.mpr

      · intro h
        apply Finset.disjoint_left.mpr
        intro e he₁ he₂
        induction e using Sym2.ind with
        | _ a b =>
          obtain ⟨ha,hb,hab⟩ := (in519_mk_mem_edges s a b).mp he₁
          obtain ⟨ha',hb',_⟩ := (in519_mk_mem_edges t a b).mp he₂
          have hgt : 1 < (s ∩ t).card := Finset.one_lt_card.mpr
            ⟨a,Finset.mem_inter.mpr ⟨ha,ha'⟩,b,Finset.mem_inter.mpr ⟨hb,hb'⟩,hab⟩
          omega
    
  4. In any finite set r with at least two elements, every element x ∈ r has another element y ∈ r distinct from it.

    Because |r| ≥ 2, there exist two distinct elements a, b ∈ r. If x = a, we choose y = b; otherwise, we choose y = a.

    lines 28–36

    uses Finset.one_lt_card.mp

    private theorem in519_edges_injective_on_nontrivial {V : Type*} [DecidableEq V] (s t : Finset V)
        (hs : 2 ≤ s.card) (ht : 2 ≤ t.card)
        (heq : finite_vertex_set_edge_encoding s = finite_vertex_set_edge_encoding t) : s = t := by
      have hex : ∀ (r : Finset V), 2 ≤ r.card → ∀ x ∈ r, ∃ y ∈ r, x ≠ y := by
        intro r hr x hx
        obtain ⟨a,ha,b,hb,hab⟩ := Finset.one_lt_card.mp (by omega : 1 < r.card)
        by_cases h : x = a
        · exact ⟨b,hb,by simpa [h] using hab⟩
        · exact ⟨a,ha,h⟩
  5. The edge encoding is injective on finite vertex sets of cardinality at least 2.

    By extensionality, we show x ∈ s ↔ x ∈ t. If x ∈ s, we choose a distinct partner y ∈ s; then the edge s(x, y) is in the edge encoding of s, hence in the edge encoding of t, giving x ∈ t. The reverse implication holds symmetrically.

    lines 37–53

    uses Finset.ext, in519_mk_mem_edges

      apply Finset.ext
      intro x
      constructor
      · intro hx
        obtain ⟨y,hy,hxy⟩ := hex s hs x hx
        have he : s(x,y) ∈ finite_vertex_set_edge_encoding t := by
          rw [← heq]
          exact (in519_mk_mem_edges s x y).mpr ⟨hx,hy,hxy⟩
        exact ((in519_mk_mem_edges t x y).mp he).1
      · intro hx
        obtain ⟨y,hy,hxy⟩ := hex t ht x hx
        have he : s(x,y) ∈ finite_vertex_set_edge_encoding s := by
          rw [heq]
          exact (in519_mk_mem_edges t x y).mpr ⟨hx,hy,hxy⟩
        exact ((in519_mk_mem_edges s x y).mp he).1
    
    
  6. The edge encoding preserves the cardinality of any family P of vertex sets of size at least 2.

    Because the edge encoding map is injective on sets of size at least 2, the image of P under this map has the exact same cardinality as P.

    lines 54–60

    uses Finset.card_image_iff.mpr, in519_edges_injective_on_nontrivial

    private theorem in519_edge_image_card {V : Type*} [DecidableEq V]
        (P : Finset (Finset V)) (hsize : ∀ t ∈ P, 2 ≤ t.card) :
        (P.image finite_vertex_set_edge_encoding).card = P.card := by
      apply Finset.card_image_iff.mpr
      intro s hs t ht heq
      exact in519_edges_injective_on_nontrivial s t (hsize s hs) (hsize t ht) heq
    
  7. If the edge encodings of members of P are pairwise disjoint, then any two distinct members of P intersect in at most one vertex.

    Let s, t ∈ P be distinct sets. Because both have size at least 2 and the encoding is injective, their edge encodings are distinct. Pairwise disjointness of the image implies that these edge encodings are disjoint, which in turn implies |s ∩ t| ≤ 1.

    lines 61–72

    uses in519_edges_injective_on_nontrivial, in519_edges_disjoint_iff_inter_small, Finset.mem_image.mpr

    private theorem in519_edge_image_packing_iff {V : Type*} [DecidableEq V]
        (P : Finset (Finset V)) (hsize : ∀ t ∈ P, 2 ≤ t.card) :
        ((P.image finite_vertex_set_edge_encoding : Finset (Finset (Sym2 V))) :
          Set (Finset (Sym2 V))).Pairwise Disjoint ↔
          (P : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) := by
      constructor
      · intro h s hs t ht hne
        have hne' : finite_vertex_set_edge_encoding s ≠ finite_vertex_set_edge_encoding t := by
          intro heq
          exact hne (in519_edges_injective_on_nontrivial s t (hsize s hs) (hsize t ht) heq)
        apply (in519_edges_disjoint_iff_inter_small s t).mp
        exact h (Finset.mem_image.mpr ⟨s,hs,rfl⟩) (Finset.mem_image.mpr ⟨t,ht,rfl⟩) hne'
  8. If members of P pairwise intersect in at most one vertex, then their edge encodings are pairwise disjoint.

    Two distinct edge encodings in the image come from distinct sets s', t' ∈ P. By hypothesis, |s' ∩ t'| ≤ 1, so their edge encodings are disjoint.

    lines 73–79

    uses Finset.mem_image.mp, congrArg, in519_edges_disjoint_iff_inter_small

      · intro h s hs t ht hne
        obtain ⟨s',hs',rfl⟩ := Finset.mem_image.mp hs
        obtain ⟨t',ht',rfl⟩ := Finset.mem_image.mp ht
        have hne' : s' ≠ t' := by intro heq; exact hne (congrArg finite_vertex_set_edge_encoding heq)
        exact (in519_edges_disjoint_iff_inter_small s' t').mpr (h hs' ht' hne')
    
    
  9. If C intersects every edge encoding in the image of P, then every set t ∈ P contains both endpoints of some edge in C.

    Given t ∈ P, its edge encoding is in the image and must share an edge e with C. Since e belongs to the edge encoding of t, both of its endpoints are elements of t.

    lines 80–91

    uses Finset.mem_image.mpr, Finset.not_disjoint_iff.mp, Finset.mem_sym2_iff.mp, Finset.mem_filter.mp

    private theorem in519_edge_image_cover_iff {V : Type*} [DecidableEq V]
        (P : Finset (Finset V)) (C : Finset (Sym2 V))
        (hC : ∀ e ∈ C, ¬ e.IsDiag) :
        (∀ F ∈ P.image finite_vertex_set_edge_encoding, ¬ Disjoint F C) ↔
          (∀ t ∈ P, ∃ e ∈ C, ∀ x ∈ e, x ∈ t) := by
      constructor
      · intro h t ht
        have ht' : finite_vertex_set_edge_encoding t ∈ P.image finite_vertex_set_edge_encoding :=
          Finset.mem_image.mpr ⟨t,ht,rfl⟩
        obtain ⟨e,he,hC⟩ := Finset.not_disjoint_iff.mp (h _ ht')
        refine ⟨e,hC,?_⟩
        exact Finset.mem_sym2_iff.mp (Finset.mem_filter.mp he).1
  10. If every set t ∈ P contains both endpoints of some edge in C, then C intersects every edge encoding in the image of P.

    Any member of the image is the edge encoding of some t ∈ P. By assumption, there is an edge e ∈ C with e ⊆ t. Since e ∈ C is non-diagonal, e is in the edge encoding of t, showing that the edge encoding and C share an element.

    lines 92–99

    uses Finset.mem_image.mp, Finset.not_disjoint_iff.mpr, Finset.mem_filter.mpr, Finset.mem_sym2_iff.mpr

      · intro h F hF
        obtain ⟨t,ht,rfl⟩ := Finset.mem_image.mp hF
        obtain ⟨e,he,hsub⟩ := h t ht
        apply Finset.not_disjoint_iff.mpr
        refine ⟨e,?_,he⟩
        apply Finset.mem_filter.mpr
        exact ⟨Finset.mem_sym2_iff.mpr hsub,hC e he⟩
    
  11. The bridge theorem holds: the edge encoding preserves family size, converts vertex-intersection-at-most-one packings into disjoint set packings, and converts edge covers into hitting sets.

    The main theorem combines the three established properties as a conjunction: cardinality preservation, the packing equivalence, and the cover equivalence.

    lines 100–109

    uses in519_edge_image_card, in519_edge_image_packing_iff, in519_edge_image_cover_iff

    theorem finite_vertex_family_edge_packing_cover_bridge {V : Type*} [DecidableEq V]
        (P : Finset (Finset V)) (C : Finset (Sym2 V))
        (hsize : ∀ t ∈ P, 2 ≤ t.card) (hC : ∀ e ∈ C, ¬ e.IsDiag) :
        (P.image finite_vertex_set_edge_encoding).card = P.card ∧
        (((P.image finite_vertex_set_edge_encoding : Finset (Finset (Sym2 V))) :
            Set (Finset (Sym2 V))).Pairwise Disjoint ↔
          (P : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1)) ∧
        ((∀ F ∈ P.image finite_vertex_set_edge_encoding, ¬ Disjoint F C) ↔
          (∀ t ∈ P, ∃ e ∈ C, ∀ x ∈ e, x ∈ t)) := by
      exact ⟨in519_edge_image_card P hsize, in519_edge_image_packing_iff P hsize, in519_edge_image_cover_iff P C hC⟩
Sym2.mk_isDiag_iff
An unordered pair s(a, b) is diagonal (a self-loop) if and only if a = b.
and_assoc
Conjunction of propositions is associative.
Finset.one_lt_card.mp
A finite set has cardinality strictly greater than 1 only if it contains at least two distinct elements.
Finset.mem_inter.mp
An element in the intersection of two sets belongs to both sets.
in519_mk_mem_edges
An edge s(a, b) belongs to the edge encoding of a vertex set s if and only if a ∈ s, b ∈ s, and a ≠ b.
Finset.disjoint_left.mp
If two sets are disjoint, any element in the first set is not in the second.
Finset.disjoint_left.mpr
Two sets are disjoint if no element of the first belongs to the second.
Sym2.ind
To prove a property for all unordered pairs in Sym2, it suffices to prove it for pairs of the form s(x, y).
Finset.one_lt_card.mpr
If a finite set contains at least two distinct elements, its cardinality is strictly greater than 1.
Finset.mem_inter.mpr
An element belonging to both sets belongs to their intersection.
Finset.ext
Two finite sets are equal if they contain the same elements.
Finset.card_image_iff.mpr
A function that is injective on a finite set preserves its cardinality under image.
in519_edges_injective_on_nontrivial
The edge encoding map is injective on vertex sets of cardinality at least 2.
in519_edges_disjoint_iff_inter_small
The edge encodings of two vertex sets are disjoint if and only if the sets intersect in at most one vertex.
Finset.mem_image.mpr
If an element is the image of a member of a set, it belongs to the image of the set.
Finset.mem_image.mp
Any element in the image of a set under a function is the image of some element of the set.
congrArg
A function applied to equal arguments yields equal values.
Finset.not_disjoint_iff.mp
If two sets are not disjoint, they have an element in common.
Finset.mem_sym2_iff.mp
An unordered pair belongs to s.sym2 only if both of its endpoints belong to s.
Finset.mem_filter.mp
An element in a filtered set belongs to the original set and satisfies the filtering predicate.
Finset.not_disjoint_iff.mpr
If two sets share an element, they are not disjoint.
Finset.mem_filter.mpr
An element in a set satisfying a predicate belongs to the set filtered by that predicate.
Finset.mem_sym2_iff.mpr
An unordered pair whose endpoints both belong to s belongs to s.sym2.
in519_edge_image_card
Mapping a family of sets of size at least 2 by edge encoding preserves the number of sets in the family.
in519_edge_image_packing_iff
A family of sets of size at least 2 has pairwise disjoint edge encodings if and only if any two distinct sets intersect in at most one vertex.
in519_edge_image_cover_iff
A set of non-diagonal edges intersects every edge encoding of a family if and only if every set in the family contains at least one of those edges.

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

private theorem in519_mk_mem_edges {V : Type*} [DecidableEq V] (s : Finset V) (a b : V) :    s(a,b) ∈ finite_vertex_set_edge_encoding s ↔ a ∈ s ∧ b ∈ s ∧ a ≠ b := by  simp [finite_vertex_set_edge_encoding, Sym2.mk_isDiag_iff, and_assoc]private theorem in519_edges_disjoint_iff_inter_small {V : Type*} [DecidableEq V] (s t : Finset V) :    Disjoint (finite_vertex_set_edge_encoding s) (finite_vertex_set_edge_encoding t) ↔ (s ∩ t).card ≤ 1 := by  constructor  · intro h    by_contra hn    have hgt : 1 < (s ∩ t).card := by omega    obtain ⟨a,ha,b,hb,hab⟩ := Finset.one_lt_card.mp hgt    have ha' := Finset.mem_inter.mp ha    have hb' := Finset.mem_inter.mp hb    have he₁ : s(a,b) ∈ finite_vertex_set_edge_encoding s := (in519_mk_mem_edges s a b).mpr ⟨ha'.1,hb'.1,hab⟩    have he₂ : s(a,b) ∈ finite_vertex_set_edge_encoding t := (in519_mk_mem_edges t a b).mpr ⟨ha'.2,hb'.2,hab⟩    exact Finset.disjoint_left.mp h he₁ he₂  · intro h    apply Finset.disjoint_left.mpr    intro e he₁ he₂    induction e using Sym2.ind with    | _ a b =>      obtain ⟨ha,hb,hab⟩ := (in519_mk_mem_edges s a b).mp he₁      obtain ⟨ha',hb',_⟩ := (in519_mk_mem_edges t a b).mp he₂      have hgt : 1 < (s ∩ t).card := Finset.one_lt_card.mpr        ⟨a,Finset.mem_inter.mpr ⟨ha,ha'⟩,b,Finset.mem_inter.mpr ⟨hb,hb'⟩,hab⟩      omegaprivate theorem in519_edges_injective_on_nontrivial {V : Type*} [DecidableEq V] (s t : Finset V)    (hs : 2 ≤ s.card) (ht : 2 ≤ t.card)    (heq : finite_vertex_set_edge_encoding s = finite_vertex_set_edge_encoding t) : s = t := by  have hex : ∀ (r : Finset V), 2 ≤ r.card → ∀ x ∈ r, ∃ y ∈ r, x ≠ y := by    intro r hr x hx    obtain ⟨a,ha,b,hb,hab⟩ := Finset.one_lt_card.mp (by omega : 1 < r.card)    by_cases h : x = a    · exact ⟨b,hb,by simpa [h] using hab⟩    · exact ⟨a,ha,h⟩  apply Finset.ext  intro x  constructor  · intro hx    obtain ⟨y,hy,hxy⟩ := hex s hs x hx    have he : s(x,y) ∈ finite_vertex_set_edge_encoding t := by      rw [← heq]      exact (in519_mk_mem_edges s x y).mpr ⟨hx,hy,hxy⟩    exact ((in519_mk_mem_edges t x y).mp he).1  · intro hx    obtain ⟨y,hy,hxy⟩ := hex t ht x hx    have he : s(x,y) ∈ finite_vertex_set_edge_encoding s := by      rw [heq]      exact (in519_mk_mem_edges t x y).mpr ⟨hx,hy,hxy⟩    exact ((in519_mk_mem_edges s x y).mp he).1private theorem in519_edge_image_card {V : Type*} [DecidableEq V]    (P : Finset (Finset V)) (hsize : ∀ t ∈ P, 2 ≤ t.card) :    (P.image finite_vertex_set_edge_encoding).card = P.card := by  apply Finset.card_image_iff.mpr  intro s hs t ht heq  exact in519_edges_injective_on_nontrivial s t (hsize s hs) (hsize t ht) heqprivate theorem in519_edge_image_packing_iff {V : Type*} [DecidableEq V]    (P : Finset (Finset V)) (hsize : ∀ t ∈ P, 2 ≤ t.card) :    ((P.image finite_vertex_set_edge_encoding : Finset (Finset (Sym2 V))) :      Set (Finset (Sym2 V))).Pairwise Disjoint ↔      (P : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) := by  constructor  · intro h s hs t ht hne    have hne' : finite_vertex_set_edge_encoding s ≠ finite_vertex_set_edge_encoding t := by      intro heq      exact hne (in519_edges_injective_on_nontrivial s t (hsize s hs) (hsize t ht) heq)    apply (in519_edges_disjoint_iff_inter_small s t).mp    exact h (Finset.mem_image.mpr ⟨s,hs,rfl⟩) (Finset.mem_image.mpr ⟨t,ht,rfl⟩) hne'  · intro h s hs t ht hne    obtain ⟨s',hs',rfl⟩ := Finset.mem_image.mp hs    obtain ⟨t',ht',rfl⟩ := Finset.mem_image.mp ht    have hne' : s' ≠ t' := by intro heq; exact hne (congrArg finite_vertex_set_edge_encoding heq)    exact (in519_edges_disjoint_iff_inter_small s' t').mpr (h hs' ht' hne')private theorem in519_edge_image_cover_iff {V : Type*} [DecidableEq V]    (P : Finset (Finset V)) (C : Finset (Sym2 V))    (hC : ∀ e ∈ C, ¬ e.IsDiag) :    (∀ F ∈ P.image finite_vertex_set_edge_encoding, ¬ Disjoint F C) ↔      (∀ t ∈ P, ∃ e ∈ C, ∀ x ∈ e, x ∈ t) := by  constructor  · intro h t ht    have ht' : finite_vertex_set_edge_encoding t ∈ P.image finite_vertex_set_edge_encoding :=      Finset.mem_image.mpr ⟨t,ht,rfl⟩    obtain ⟨e,he,hC⟩ := Finset.not_disjoint_iff.mp (h _ ht')    refine ⟨e,hC,?_⟩    exact Finset.mem_sym2_iff.mp (Finset.mem_filter.mp he).1  · intro h F hF    obtain ⟨t,ht,rfl⟩ := Finset.mem_image.mp hF    obtain ⟨e,he,hsub⟩ := h t ht    apply Finset.not_disjoint_iff.mpr    refine ⟨e,?_,he⟩    apply Finset.mem_filter.mpr    exact ⟨Finset.mem_sym2_iff.mpr hsub,hC e he⟩theorem finite_vertex_family_edge_packing_cover_bridge {V : Type*} [DecidableEq V]    (P : Finset (Finset V)) (C : Finset (Sym2 V))    (hsize : ∀ t ∈ P, 2 ≤ t.card) (hC : ∀ e ∈ C, ¬ e.IsDiag) :    (P.image finite_vertex_set_edge_encoding).card = P.card ∧    (((P.image finite_vertex_set_edge_encoding : Finset (Finset (Sym2 V))) :        Set (Finset (Sym2 V))).Pairwise Disjoint ↔      (P : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1)) ∧    ((∀ F ∈ P.image finite_vertex_set_edge_encoding, ¬ Disjoint F C) ↔      (∀ t ∈ P, ∃ e ∈ C, ∀ x ∈ e, x ∈ t)) := by  exact ⟨in519_edge_image_card P hsize, in519_edge_image_packing_iff P hsize, in519_edge_image_cover_iff P C hC⟩
See it in the graphDiscuss this resultChallenge it