finite_vertex_set_edge_encoding_disjoint_iff_inter_card_le_one
Two finite vertex sets have disjoint non-diagonal unordered-pair encodings exactly when their intersection contains at most one vertex.
Statement
theorem finite_vertex_set_edge_encoding_disjoint_iff_inter_card_le_one {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
- Source
- Reusable packing step for simple_graph_forced_k4_face_pivot_retains_forcing.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- finite_vertex_set_edge_encodingThe non-diagonal unordered vertex pairs spanned by a finite vertex set.
The proof, explained
The equivalence is established by proving each implication separately in helper lemmas. If the edge encodings are disjoint, their vertex sets cannot intersect in two or more elements; otherwise, any two distinct vertices in s ∩ t would form a shared non-diagonal edge, contradicting disjointness. Conversely, if |s ∩ t| ≤ 1, no shared edge can exist, because any edge in both encodings would provide two distinct vertices in s ∩ t and force |s ∩ t| > 1. Combining these two implications completes the proof.
To show that the edge encodings of s and t are disjoint, it suffices to derive a contradiction from the existence of a shared edge.
By Finset.disjoint_left.mpr, two finite sets are disjoint if they share no element. Assuming for contradiction that an edge e belongs to both encodings, Sym2.ind allows us to write e as an unordered pair s(u, v) of vertices.
uses
Finset.disjoint_left.mpr,Sym2.indclassical apply Finset.disjoint_left.mpr intro e hes het induction e using Sym2.ind with | _ u v =>
Both endpoints u and v are distinct vertices belonging to the intersection s ∩ t.
Unfolding the definition of finite_vertex_set_edge_encoding using Finset.mem_filter, Finset.mk_mem_sym2_iff, and Sym2.isDiag_iff_proj_eq shows that an edge s(u, v) belongs to the encoding of a set if and only if both u and v belong to the set and u ≠ v. Since s(u, v) is in both encodings, both u and v belong to s and to t, and u ≠ v. By Finset.mem_inter.mpr, this means u ∈ s ∩ t and v ∈ s ∩ t.
uses
Finset.mem_filter,Finset.mk_mem_sym2_iff,Sym2.isDiag_iff_proj_eq,Finset.mem_inter.mprsimp only [finite_vertex_set_edge_encoding, Finset.mem_filter, Finset.mk_mem_sym2_iff, Sym2.isDiag_iff_proj_eq] at hes het have hm : u ∈ s ∩ t := Finset.mem_inter.mpr ⟨hes.1.1,het.1.1⟩ have hn : v ∈ s ∩ t := Finset.mem_inter.mpr ⟨hes.1.2,het.1.2⟩ have hne : u ≠ v := hes.2
The existence of two distinct elements in s ∩ t contradicts |s ∩ t| ≤ 1.
Since u and v are distinct elements of s ∩ t, Finset.one_lt_card.mpr implies that 1 < (s ∩ t).card. This directly contradicts the assumption (s ∩ t).card ≤ 1, and linear arithmetic (omega) closes the goal.
uses
Finset.one_lt_card.mprhave hh : 1 < (s ∩ t).card := Finset.one_lt_card.mpr ⟨u,hm,v,hn,hne⟩ omega
Assuming |s ∩ t| > 1, there exist two distinct vertices u, v in s ∩ t.
Assuming for contradiction that (s ∩ t).card ≤ 1 fails, linear integer arithmetic (omega) yields 1 < (s ∩ t).card. By Finset.one_lt_card.mp, any finite set of cardinality greater than 1 contains two distinct elements u and v. Since both lie in s ∩ t, Finset.mem_inter.mp gives u ∈ s, u ∈ t, v ∈ s, and v ∈ t.
uses
Finset.one_lt_card.mp,Finset.mem_inter.mpclassical by_contra hn have hh : 1 < (s ∩ t).card := by omega obtain ⟨u,hu,v,hv,huv⟩ := Finset.one_lt_card.mp hh obtain ⟨hus,hut⟩ := Finset.mem_inter.mp hu obtain ⟨hvs,hvt⟩ := Finset.mem_inter.mp hv
The edge s(u, v) belongs to both encodings, contradicting their disjointness.
Because u, v ∈ s and u ≠ v, the pair s(u, v) belongs to finite_vertex_set_edge_encoding s. Similarly, because u, v ∈ t and u ≠ v, s(u, v) belongs to finite_vertex_set_edge_encoding t. By Finset.disjoint_left.mp, this contradicts the hypothesis that the two encodings are disjoint.
uses
Finset.disjoint_left.mphave h1 : s(u,v) ∈ finite_vertex_set_edge_encoding s := by simp [finite_vertex_set_edge_encoding, hus, hvs, huv] have h2 : s(u,v) ∈ finite_vertex_set_edge_encoding t := by simp [finite_vertex_set_edge_encoding, hut, hvt, huv] exact Finset.disjoint_left.mp h h1 h2
The edge encodings of s and t are disjoint if and only if |s ∩ t| ≤ 1.
The equivalence follows by pairing the two directions: In700Edge.in700_encoding_disjoint_iff establishes that disjointness implies (s ∩ t).card ≤ 1, and In700Edge.in700_encoding_disjoint establishes that (s ∩ t).card ≤ 1 implies disjointness.
uses
In700Edge.in700_encoding_disjoint_iff,In700Edge.in700_encoding_disjointexact ⟨In700Edge.in700_encoding_disjoint_iff s t, In700Edge.in700_encoding_disjoint s t⟩
Finset.disjoint_left.mpr- Two finite sets are disjoint if no element belonging to the first belongs to the second.
Finset.disjoint_left.mp- If two finite sets are disjoint, no element belonging to the first can belong to the second.
Finset.mem_filter- An element belongs to a filtered finite set if and only if it belongs to the original set and satisfies the predicate.
Finset.mk_mem_sym2_iff- An unordered pair belongs to the symmetric square of a finite set if and only if both endpoints belong to the set.
Finset.mem_inter.mpr- An element belongs to the intersection of two finite sets if it belongs to both sets.
Finset.mem_inter.mp- If an element belongs to the intersection of two finite sets, it belongs to both sets.
Finset.one_lt_card.mpr- A finite set with at least two distinct elements has cardinality strictly greater than 1.
Finset.one_lt_card.mp- A finite set with cardinality strictly greater than 1 contains at least two distinct elements.
Sym2.ind- Any property of unordered pairs holds for all pairs if it holds for pairs of the form s(x, y).
Sym2.isDiag_iff_proj_eq- An unordered pair s(x, y) is on the diagonal (degenerate) if and only if its two endpoints are equal.
In700Edge.in700_encoding_disjoint- If the intersection of two vertex sets has cardinality at most 1, their non-diagonal edge encodings are disjoint.
In700Edge.in700_encoding_disjoint_iff- If the non-diagonal edge encodings of two vertex sets are disjoint, their intersection has cardinality at most 1.
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.
open scoped Sym2namespace In700Edgelemma in700_encoding_disjoint {V : Type*} [DecidableEq V] (s t : Finset V) (h : (s ∩ t).card ≤ 1) : Disjoint (finite_vertex_set_edge_encoding s) (finite_vertex_set_edge_encoding t) := by classical apply Finset.disjoint_left.mpr intro e hes het induction e using Sym2.ind with | _ u v => simp only [finite_vertex_set_edge_encoding, Finset.mem_filter, Finset.mk_mem_sym2_iff, Sym2.isDiag_iff_proj_eq] at hes het have hm : u ∈ s ∩ t := Finset.mem_inter.mpr ⟨hes.1.1,het.1.1⟩ have hn : v ∈ s ∩ t := Finset.mem_inter.mpr ⟨hes.1.2,het.1.2⟩ have hne : u ≠ v := hes.2 have hh : 1 < (s ∩ t).card := Finset.one_lt_card.mpr ⟨u,hm,v,hn,hne⟩ omegalemma in700_encoding_disjoint_iff {V : Type*} [DecidableEq V] (s t : Finset V) (h : Disjoint (finite_vertex_set_edge_encoding s) (finite_vertex_set_edge_encoding t)) : (s ∩ t).card ≤ 1 := by classical by_contra hn have hh : 1 < (s ∩ t).card := by omega obtain ⟨u,hu,v,hv,huv⟩ := Finset.one_lt_card.mp hh obtain ⟨hus,hut⟩ := Finset.mem_inter.mp hu obtain ⟨hvs,hvt⟩ := Finset.mem_inter.mp hv have h1 : s(u,v) ∈ finite_vertex_set_edge_encoding s := by simp [finite_vertex_set_edge_encoding, hus, hvs, huv] have h2 : s(u,v) ∈ finite_vertex_set_edge_encoding t := by simp [finite_vertex_set_edge_encoding, hut, hvt, huv] exact Finset.disjoint_left.mp h h1 h2end In700Edgetheorem finite_vertex_set_edge_encoding_disjoint_iff_inter_card_le_one {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 exact ⟨In700Edge.in700_encoding_disjoint_iff s t, In700Edge.in700_encoding_disjoint s t⟩