AFTD Auto-Formalizing Theoretical Domains

finite_vertex_set_edge_encoding_disjoint_iff_inter_card_le_one

theoremverified

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

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.

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

    lines 6–10

    uses Finset.disjoint_left.mpr, Sym2.ind

      classical
      apply Finset.disjoint_left.mpr
      intro e hes het
      induction e using Sym2.ind with
      | _ u v =>
  2. 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.

    lines 11–15

    uses Finset.mem_filter, Finset.mk_mem_sym2_iff, Sym2.isDiag_iff_proj_eq, Finset.mem_inter.mpr

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

    lines 16–17

    uses Finset.one_lt_card.mpr

        have hh : 1 < (s ∩ t).card := Finset.one_lt_card.mpr ⟨u,hm,v,hn,hne⟩
        omega
  4. 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.

    lines 21–26

    uses Finset.one_lt_card.mp, Finset.mem_inter.mp

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

    lines 27–31

    uses Finset.disjoint_left.mp

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

    line 35

    uses In700Edge.in700_encoding_disjoint_iff, In700Edge.in700_encoding_disjoint

      exact ⟨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

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