finite_vertex_family_edge_packing_cover_bridge
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
- simple_graph_seven_packing_local_minimum_seed_supergraph_rigidityA graph on the nine vertices of the local-exchange seed that contains all seed edges and has triangle packing number at most seven adds no…
- simple_graph_maximum_packing_two_forced_edges_k4For a maximum triangle packing, if a packed triangle has two singleton-forced edges then its three vertices have a common fourth vertex…
- simple_graph_stable_triangle_active_edge_in_maximum_packingIn a finite graph where deleting any edge preserves the maximum triangle packing number, every edge belonging to a triangle is used by…
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.
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.
uses
Sym2.mk_isDiag_iff,and_assocprivate 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]
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.
uses
Finset.one_lt_card.mp,Finset.mem_inter.mp,in519_mk_mem_edges,Finset.disjoint_left.mpprivate 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₂
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.
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
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.
uses
Finset.one_lt_card.mpprivate 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⟩
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.
uses
Finset.ext,in519_mk_mem_edgesapply 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
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.
uses
Finset.card_image_iff.mpr,in519_edges_injective_on_nontrivialprivate 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
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.
uses
in519_edges_injective_on_nontrivial,in519_edges_disjoint_iff_inter_small,Finset.mem_image.mprprivate 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'
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.
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')
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.
uses
Finset.mem_image.mpr,Finset.not_disjoint_iff.mp,Finset.mem_sym2_iff.mp,Finset.mem_filter.mpprivate 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
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.
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⟩
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.
uses
in519_edge_image_card,in519_edge_image_packing_iff,in519_edge_image_cover_ifftheorem 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.
- The definition `finite_vertex_set_edge_encoding s` takes the symmetric square `s.sym2` and filters out diagonal pairs `s(x, x)`, representing the set of 2-element subsets (undirected graph edges) on vertex set $s$.
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.
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⟩