AFTD Auto-Formalizing Theoretical Domains

graph_defect_le_one

theoremverifiedformalization

For every graph G on at least one vertex and every integer t ≥ 2, the defect def_t(G) satisfies def_t(G) ≤ 1. That is, the least nonnegative integer d such that every Z_t-labeling of K_{2n} either provides a vertex-disjoint copy of the same weight for each copy of G, or contains two copies of G with different weights on some subset of at most n + d vertices, is at most 1.

Statement

theorem graph_defect_le_one {α : Type*} [Fintype α] [Nonempty α] (G : SimpleGraph α)
    (t : ℕ) (ht : 2 ≤ t) :
    let copyWeight (C : SimpleGraph.TopEdgeLabeling (Fin (2 * Fintype.card α)) (ZMod t))
        (f : SimpleGraph.Copy G (⊤ : SimpleGraph (Fin (2 * Fintype.card α)))) : ZMod t :=
      open Classical in ∑ e : G.edgeSet, C (f.mapEdgeSet e)
    sInf {d : ℕ |
      ∀ (C : SimpleGraph.TopEdgeLabeling (Fin (2 * Fintype.card α)) (ZMod t)),
        (∀ (f₁ : SimpleGraph.Copy G (⊤ : SimpleGraph (Fin (2 * Fintype.card α)))),
          ∃ (f₂ : SimpleGraph.Copy G (⊤ : SimpleGraph (Fin (2 * Fintype.card α)))),
            Disjoint (Set.range f₁) (Set.range f₂) ∧
            copyWeight C f₁ = copyWeight C f₂) ∨
        (∃ (U : Finset (Fin (2 * Fintype.card α))), U.card ≤ Fintype.card α + d ∧
          ∃ (f₁ f₂ : SimpleGraph.Copy G (⊤ : SimpleGraph (Fin (2 * Fintype.card α)))),
            (∀ v, f₁ v ∈ U) ∧ (∀ v, f₂ v ∈ U) ∧
            copyWeight C f₁ ≠ copyWeight C f₂)} ≤ 1
Formalizes
arXiv:2611.14160 Lemma 3.7
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • weightThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…

Read back from the Lean

Let $\alpha$ be a finite, non-empty type, and let $G$ be a simple graph on $\alpha$. Let $n = \mathrm{card}(\alpha)$. Let $t$ be a natural number with $t \ge 2$. Define the weight of a copy $f$ of $G$ in the complete graph $\top$ on $\mathrm{Fin}(2n)$, with respect to an edge labeling $C : \mathrm{edgeSet}(\top) \to \mathbb{Z}/t\mathbb{Z}$, by $$\mathrm{copyWeight}(C, f) = \sum_{e \in G.\mathrm{edgeSet}} C(f(e)) \in \mathbb{Z}/t\mathbb{Z}.$$ Consider the set of all $d \in \mathbb{N}$ such that for every edge labeling $C$ of the complete graph on $\mathrm{Fin}(2n)$ with values in $\mathbb{Z}/t\mathbb{Z}$, at least one of the following two conditions holds: 1. For every copy $f_1$ of $G$ in $\top$, there exists a copy $f_2$ of $G$ in $\top$ such that the vertex ranges of $f_1$ and $f_2$ are disjoint, and $\mathrm{copyWeight}(C, f_1) = \mathrm{copyWeight}(C, f_2)$. 2. There exists a subset $U \subseteq \mathrm{Fin}(2n)$ with $\mathrm{card}(U) \le n + d$, and two copies $f_1, f_2$ of $G$ in $\top$ both having their vertex ranges contained in $U$ (i.e., $\forall v \in \alpha, f_1(v) \in U$ and $f_2(v) \in U$), such that $\mathrm{copyWeight}(C, f_1) \ne \mathrm{copyWeight}(C, f_2)$. The theorem asserts that the infimum (in $\mathbb{N}$) of this set of natural numbers $d$ is at most $1$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof establishes that $d = 1$ is an admissible defect, which implies $\operatorname{def}_t(G) \le 1$. If there exists a subset of at most $n + 1$ vertices supporting two copies of $G$ with different weights, the second alternative of the defect dichotomy holds immediately. Otherwise, any two copies sharing a subset of size at most $n + 1$ must have the same weight, which implies that swapping a single vertex between two $n$-subsets preserves copy weights. By induction on the symmetric difference, every $n$-element subset has the same canonical copy weight; in particular, any copy of $G$ has the same weight as any copy on its complementary $n$-vertex set, providing the desired vertex-disjoint copy of equal weight.

  1. Either there exist two copies of $G$ of different weights on some subset of at most $n+1$ vertices, or no such pair exists.

    We introduce the copy-weight function `cw` and perform a case split on whether there exists a subset $U \subseteq V$ of size at most $n + 1$ supporting two copies $f_1, f_2$ of $G$ with $cw(f_1) \ne cw(f_2)$. If such a set $U$ exists, the second alternative of the theorem holds immediately.

    lines 15–19

    uses Or.inr

      intro cw
      by_cases hA : ∃ (U : Finset V), U.card ≤ Fintype.card α + 1 ∧
          ∃ (f₁ f₂ : SimpleGraph.Copy G (⊤ : SimpleGraph V)),
            (∀ v, f₁ v ∈ U) ∧ (∀ v, f₂ v ∈ U) ∧ cw f₁ ≠ cw f₂
      · exact Or.inr hA
  2. Any two copies of $G$ whose vertices lie in a common subset of size at most $n+1$ must have equal weight.

    Under the negation of the case split, we focus on proving the first alternative (that every copy has a disjoint copy of identical weight). By contradiction, if two copies $f, g$ supported on some subset $U$ of size at most $n + 1$ had different weights, this would directly contradict the negation hypothesis.

    lines 20–26

      · left
        have key : ∀ (U : Finset V), U.card ≤ Fintype.card α + 1 →
            ∀ (f g : SimpleGraph.Copy G (⊤ : SimpleGraph V)),
            (∀ v, f v ∈ U) → (∀ v, g v ∈ U) → cw f = cw g := by
          intro U hU f g hf hg
          by_contra hne
          exact hA ⟨U, hU, f, g, hf, hg, hne⟩
  3. Every subset $T \subseteq V$ of size $n$ contains an embedded copy of $G$.

    Since $|T| = |\alpha| = n$, there is a bijection between $\alpha$ and $T$. Because the ambient host graph on $V$ is the complete graph $\top$, any injective vertex map preserves adjacency (distinct vertices in $G$ map to distinct, hence adjacent, vertices in $\top$). Thus this bijection defines an embedded copy of $G$ with vertex range contained in $T$.

    lines 27–37

    uses Fintype.card_coe, Fintype.equivOfCardEq, Subtype.coe_injective, SimpleGraph.Copy.mk, SimpleGraph.top_adj

        have hex : ∀ (T : Finset V), T.card = Fintype.card α →
            ∃ f : SimpleGraph.Copy G (⊤ : SimpleGraph V), ∀ v, f v ∈ T := by
          intro T hT
          have hc : Fintype.card α = Fintype.card T := by rw [Fintype.card_coe, hT]
          let e : α ≃ T := Fintype.equivOfCardEq hc
          let g : α → V := fun a => (e a : V)
          have hg : Function.Injective g := fun a b h => e.injective (Subtype.coe_injective h)
          refine ⟨SimpleGraph.Copy.mk ⟨g, ?_⟩ hg, fun a => (e a).2⟩
          intro a b hab
          simp only [SimpleGraph.top_adj]
          exact fun h => G.ne_of_adj hab (hg h)
  4. For any subset $T$ of size at most $n+1$, the canonical weight $w(T)$ is well-defined and equals the weight of any copy of $G$ contained in $T$.

    We define $w(T)$ by choosing a copy of $G$ inside $T$ via classical choice if one exists, and 0 otherwise. When $|T| \le n+1$, the key equality guarantees that all copies in $T$ have the identical weight, so $w(T) = cw(f)$ for any copy $f$ whose vertices lie in $T$.

    lines 38–47

    uses Classical.choose, dif_pos, Classical.choose_spec

        let w : Finset V → ZMod t := fun T => if h : ∃ f : SimpleGraph.Copy G (⊤ : SimpleGraph V), ∀ v, f v ∈ T
            then cw (Classical.choose h) else 0
        have w_eq : ∀ (T : Finset V), T.card ≤ Fintype.card α + 1 →
            ∀ (f : SimpleGraph.Copy G (⊤ : SimpleGraph V)), (∀ v, f v ∈ T) → w T = cw f := by
          intro T hT f hf
          have hhex : ∃ g : SimpleGraph.Copy G (⊤ : SimpleGraph V), ∀ v, g v ∈ T := ⟨f, hf⟩
          show (if h : ∃ f : SimpleGraph.Copy G (⊤ : SimpleGraph V), ∀ v, f v ∈ T
              then cw (Classical.choose h) else 0) = cw f
          rw [dif_pos hhex]
          exact key T hT _ _ (Classical.choose_spec hhex) hf
  5. Any two $n$-subsets whose union has size at most $n+1$ have the same canonical weight.

    Given $n$-element subsets $A, B$ with $|A \cup B| \le n+1$, each contains a copy of $G$ by the existence lemma. Since both copies are contained in $A \cup B$ and $|A \cup B| \le n+1$, the key equality implies they have equal weight, so $w(A) = w(B)$.

    lines 48–55

    uses Finset.mem_union_left, Finset.mem_union_right

        have hswap : ∀ (A B : Finset V), A.card = Fintype.card α → B.card = Fintype.card α →
            (A ∪ B).card ≤ Fintype.card α + 1 → w A = w B := by
          intro A B hA hB hAB
          obtain ⟨f, hf⟩ := hex A hA
          obtain ⟨g, hg⟩ := hex B hB
          rw [w_eq A (by omega) f hf, w_eq B (by omega) g hg]
          exact key (A ∪ B) hAB f g (fun v => Finset.mem_union_left _ (hf v))
            (fun v => Finset.mem_union_right _ (hg v))
  6. All $n$-subsets have equal canonical weight: setting up induction on the set difference $|A \setminus B| \le k$ and resolving the base case $k = 0$.

    To show $w(A) = w(B)$ for all $n$-element sets $A, B$, it suffices to prove this whenever $|A \setminus B| \le k$ by induction on $k$. In the base case $k = 0$, we have $A \setminus B = \emptyset$, so $A \subseteq B$. Since $|A| = |B| = n$, this implies $A = B$, so $w(A) = w(B)$ trivially.

    lines 56–68

    uses le_rfl, Finset.sdiff_eq_empty_iff_subset.mp, Finset.card_eq_zero.mp, Nat.le_zero.mp, Finset.eq_of_subset_of_card_le

        have hconst : ∀ (A B : Finset V), A.card = Fintype.card α → B.card = Fintype.card α →
            w A = w B := by
          intro A B hA hB
          suffices H : ∀ k, ∀ (A B : Finset V), A.card = Fintype.card α → B.card = Fintype.card α →
              (A \ B).card ≤ k → w A = w B from H _ A B hA hB le_rfl
          intro k
          induction k with
          | zero =>
            intro A B hA hB hk
            have hsub : A ⊆ B :=
              Finset.sdiff_eq_empty_iff_subset.mp (Finset.card_eq_zero.mp (Nat.le_zero.mp hk))
            have hEq : A = B := Finset.eq_of_subset_of_card_le hsub (by omega)
            rw [hEq]
  7. Inductive step: swapping one element between $A \setminus B$ and $B \setminus A$ produces an intermediate $n$-subset $A_1$ with $w(A) = w(A_1) = w(B)$.

    If $A \subseteq B$, then $A = B$ immediately. Otherwise, there exist $a \in A \setminus B$ and $b \in B \setminus A$. Defining $A_1 = (A \setminus \{a\}) \cup \{b\}$, we have $|A_1| = n$ and $|A \cup A_1| = |A \cup \{b\}| = n + 1$, so $w(A) = w(A_1)$ by the swap property. Moreover, $A_1 \setminus B = (A \setminus B) \setminus \{a\}$, so $|A_1 \setminus B| = |A \setminus B| - 1 \le k$. By the induction hypothesis, $w(A_1) = w(B)$, completing the induction.

    lines 69–118

    uses Finset.eq_of_subset_of_card_le, Finset.sdiff_nonempty.mpr, Finset.mem_sdiff.mp, Finset.card_sdiff, Finset.inter_comm, Finset.card_pos.mpr, Finset.card_pos.mp, Finset.mem_of_mem_erase, Finset.card_insert_of_notMem, Finset.card_erase_add_one, Finset.mem_sdiff, Finset.mem_insert, Finset.mem_erase, Or.inr, Finset.card_erase_of_mem, Finset.mem_union, Or.inl

          | succ k ih =>
            intro A B hA hB hk
            by_cases hsub : A ⊆ B
            · have hEq : A = B := Finset.eq_of_subset_of_card_le hsub (by omega)
              rw [hEq]
            · obtain ⟨a, ha⟩ := Finset.sdiff_nonempty.mpr hsub
              have haA : a ∈ A := (Finset.mem_sdiff.mp ha).1
              have haB : a ∉ B := (Finset.mem_sdiff.mp ha).2
              have hcardEq : (B \ A).card = (A \ B).card := by
                rw [Finset.card_sdiff, Finset.card_sdiff, Finset.inter_comm, hA, hB]
              have hpos : 0 < (A \ B).card := Finset.card_pos.mpr ⟨a, ha⟩
              obtain ⟨b, hb⟩ := Finset.card_pos.mp (by omega : 0 < (B \ A).card)
              have hbB : b ∈ B := (Finset.mem_sdiff.mp hb).1
              have hbA : b ∉ A := (Finset.mem_sdiff.mp hb).2
              set A₁ : Finset V := insert b (A.erase a) with hA₁def
              have hbnot : b ∉ A.erase a := fun h => hbA (Finset.mem_of_mem_erase h)
              have hA₁card : A₁.card = Fintype.card α := by
                have h1 := Finset.card_insert_of_notMem hbnot
                have h2 := Finset.card_erase_add_one haA
                rw [hA₁def]
                omega
              have hdiff : A₁ \ B = (A \ B).erase a := by
                rw [hA₁def]
                ext x
                simp only [Finset.mem_sdiff, Finset.mem_insert, Finset.mem_erase]
                constructor
                · rintro ⟨hx, hxB⟩
                  rcases hx with hxb | ⟨hxa, hxA⟩
                  · subst hxb; exact absurd hbB hxB
                  · exact ⟨hxa, ⟨hxA, hxB⟩⟩
                · intro h
                  exact ⟨Or.inr ⟨h.1, h.2.1⟩, h.2.2⟩
              have hdiffcard : (A₁ \ B).card ≤ k := by
                rw [hdiff, Finset.card_erase_of_mem ha]
                omega
              have hunion : (A ∪ A₁).card ≤ Fintype.card α + 1 := by
                have hun : A ∪ A₁ = insert b A := by
                  rw [hA₁def]
                  ext x
                  simp only [Finset.mem_union, Finset.mem_insert, Finset.mem_erase]
                  constructor
                  · rintro (h | rfl | ⟨hxa, hxA⟩)
                    · exact Or.inr h
                    · exact Or.inl rfl
                    · exact Or.inr hxA
                  · rintro (rfl | h)
                    · exact Or.inr (Or.inl rfl)
                    · exact Or.inl h
                rw [hun, Finset.card_insert_of_notMem hbA, hA]
              exact (hswap A A₁ hA hA₁card hunion).trans (ih A₁ B hA₁card hB hdiffcard)
  8. Every copy $f_1$ of $G$ has a vertex-disjoint copy $f_2$ of the same weight.

    Let $S = \operatorname{range}(f_1) \subseteq V$, which has size $n$. Its complement $T = S^c$ in the $2n$-element vertex set $V$ also has size $n$. By the existence lemma, $T$ hosts a copy $f_2$ of $G$, which is vertex-disjoint from $f_1$ by construction. Since all $n$-element subsets have identical weight, $cw(f_1) = w(S) = w(T) = cw(f_2)$.

    lines 119–147

    uses Finset.card_image_of_injective, Finset.card_compl, Set.disjoint_left, Finset.mem_univ, Finset.mem_compl

        intro f₁
        let S : Finset V := Finset.univ.image f₁
        have hS : S.card = Fintype.card α := by
          have hinj : Function.Injective (⇑f₁) := f₁.injective
          rw [show S = Finset.univ.image f₁ from rfl, Finset.card_image_of_injective _ hinj]
          simp
        let T : Finset V := Sᶜ
        have hT : T.card = Fintype.card α := by
          rw [show T = Sᶜ from rfl, Finset.card_compl, hS, hV]
          omega
        obtain ⟨f₂, hf₂⟩ := hex T hT
        refine ⟨f₂, ?_, ?_⟩
        · rw [Set.disjoint_left]
          intro x hx1 hx2
          have hxS : x ∈ S := by
            obtain ⟨v, hv⟩ := hx1
            exact hv ▸ Finset.mem_image.mpr ⟨v, Finset.mem_univ v, rfl⟩
          obtain ⟨v, hv⟩ := hx2
          have hxT : f₂ v ∈ T := hf₂ v
          rw [hv] at hxT
          have hxS' : x ∉ S := by
            simpa only [T, Finset.mem_compl] using hxT
          exact hxS' hxS
        · have h1 : w S = cw f₁ :=
            w_eq S (by omega) f₁ (fun v => Finset.mem_image.mpr ⟨v, Finset.mem_univ v, rfl⟩)
          have h2 : w T = cw f₂ := w_eq T (by omega) f₂ hf₂
          have h3 : w S = w T := hconst S T hS hT
          rw [← h1, ← h2]
          exact h3
  9. The defect $\operatorname{def}_t(G)$ is at most 1.

    By the auxiliary lemma, $d = 1$ belongs to the set of integers $d$ for which every $\mathbb{Z}_t$-labeling satisfies the dichotomy. Therefore, the infimum of this set is at most 1.

    lines 165–169

    uses Nat.sInf_le, graph_defect_le_one_aux

      have _ : 2 ≤ t := ht
      dsimp only
      apply Nat.sInf_le
      intro C
      exact graph_defect_le_one_aux G t (by simp) C
Or.inr
Given a proof of $b$, constructs a proof of the disjunction $a \lor b$.
Fintype.card_coe
The cardinality of a finset viewed as a subtype equals the cardinality of the finset itself.
Fintype.equivOfCardEq
Two finite types with the same cardinality are in bijection.
Subtype.coe_injective
The canonical coercion from a subtype to the underlying type is an injective function.
SimpleGraph.Copy.mk
Constructs an embedding (copy) of graph $A$ into graph $B$ from an injective graph homomorphism.
SimpleGraph.top_adj
In the complete graph $\top$, two vertices are adjacent if and only if they are distinct.
Classical.choose
Given an existential assertion $\exists x, p(x)$, returns a witness $x$ satisfying $p(x)$.
dif_pos
In a dependent if-then-else `if h : c then t else e`, when the condition $c$ is true, the expression evaluates to $t(h)$.
Classical.choose_spec
The witness returned by `Classical.choose` satisfies the claimed property $p$.
Finset.mem_union_left
If an element belongs to finset $s$, it belongs to the union $s \cup t$.
Finset.mem_union_right
If an element belongs to finset $t$, it belongs to the union $s \cup t$.
le_rfl
Every element is less than or equal to itself in a preorder.
Finset.sdiff_eq_empty_iff_subset.mp
The set difference $s \setminus t$ is empty if and only if $s \subseteq t$.
Finset.card_eq_zero.mp
A finset has cardinality zero if and only if it is the empty set.
Nat.le_zero.mp
If a natural number is at most zero, it equals zero.
Finset.eq_of_subset_of_card_le
If $s \subseteq t$ and $|t| \le |s|$, then $s = t$.
Finset.sdiff_nonempty.mpr
If $s$ is not a subset of $t$, then the difference $s \setminus t$ is nonempty.
Finset.mem_sdiff.mp
An element belongs to $s \setminus t$ if and only if it is in $s$ and not in $t$.
Finset.card_sdiff
The cardinality of $t \setminus s$ equals $|t| - |s \cap t|$.
Finset.inter_comm
Finset intersection is commutative: $s_1 \cap s_2 = s_2 \cap s_1$.
Finset.card_pos.mpr
A finset has strictly positive cardinality if and only if it is nonempty.
Finset.card_pos.mp
If a finset has strictly positive cardinality, it is nonempty.
Finset.mem_of_mem_erase
If $b$ is in $s \setminus \{a\}$, then $b \in s$.
Finset.card_insert_of_notMem
Inserting an element not in $s$ increases the cardinality of $s$ by 1.
Finset.card_erase_add_one
Removing an element from $s$ yields a finset whose cardinality plus 1 equals $|s|$.
Finset.card_erase_of_mem
Removing an element $a \in s$ from $s$ gives a finset of cardinality $|s| - 1$.
Finset.mem_sdiff
Membership in a difference: $a \in s \setminus t$ if and only if $a \in s$ and $a \notin t$.
Finset.mem_insert
Membership in an inserted set: $x \in \operatorname{insert}(a, s)$ if and only if $x = a$ or $x \in s$.
Finset.mem_erase
Membership in an erased set: $x \in s \setminus \{a\}$ if and only if $x \in s$ and $x \ne a$.
Finset.mem_union
Membership in a union: $x \in s \cup t$ if and only if $x \in s$ or $x \in t$.
Or.inl
Given a proof of $a$, constructs a proof of the disjunction $a \lor b$.
Finset.card_image_of_injective
The image of a finset under an injective function has the same cardinality as the finset.
Finset.card_compl
The cardinality of the complement of a finset $s$ in a finite type $\alpha$ is $|\alpha| - |s|$.
Set.disjoint_left
Two sets are disjoint if and only if no element of the first set belongs to the second set.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
Finset.mem_compl
An element belongs to the complement $s^c$ if and only if it does not belong to $s$.
Nat.sInf_le
If a natural number $m$ belongs to a set $s \subseteq \mathbb{N}$, then $\inf s \le m$.
graph_defect_le_one_aux
For every $\mathbb{Z}_t$-edge-labeling of $K_{2n}$, either every copy of $G$ has a vertex-disjoint copy of the same weight, or some subset of at most $n+1$ vertices contains two copies of $G$ with different weights.

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 Classical in/-- For a labelling of the complete graph on `2 * |α|` vertices: either every copy of `G` has avertex-disjoint copy of the same weight, or two copies of `G` with different weights both live on aset of at most `|α| + 1` vertices. -/private lemma graph_defect_le_one_aux {α : Type*} [Fintype α] [Nonempty α] (G : SimpleGraph α) (t : ℕ)    {V : Type*} [Fintype V] [DecidableEq V]    (hV : Fintype.card V = 2 * Fintype.card α)    (C : SimpleGraph.TopEdgeLabeling V (ZMod t)) :    let cw : SimpleGraph.Copy G (⊤ : SimpleGraph V) → ZMod t := fun f => ∑ e : G.edgeSet, C (f.mapEdgeSet e)    (∀ (f₁ : SimpleGraph.Copy G (⊤ : SimpleGraph V)), ∃ (f₂ : SimpleGraph.Copy G (⊤ : SimpleGraph V)),        Disjoint (Set.range f₁) (Set.range f₂) ∧ cw f₁ = cw f₂) ∨    (∃ (U : Finset V), U.card ≤ Fintype.card α + 1 ∧      ∃ (f₁ f₂ : SimpleGraph.Copy G (⊤ : SimpleGraph V)),        (∀ v, f₁ v ∈ U) ∧ (∀ v, f₂ v ∈ U) ∧ cw f₁ ≠ cw f₂) := by  intro cw  by_cases hA : ∃ (U : Finset V), U.card ≤ Fintype.card α + 1 ∧      ∃ (f₁ f₂ : SimpleGraph.Copy G (⊤ : SimpleGraph V)),        (∀ v, f₁ v ∈ U) ∧ (∀ v, f₂ v ∈ U) ∧ cw f₁ ≠ cw f₂  · exact Or.inr hA  · left    have key : ∀ (U : Finset V), U.card ≤ Fintype.card α + 1 →        ∀ (f g : SimpleGraph.Copy G (⊤ : SimpleGraph V)),        (∀ v, f v ∈ U) → (∀ v, g v ∈ U) → cw f = cw g := by      intro U hU f g hf hg      by_contra hne      exact hA ⟨U, hU, f, g, hf, hg, hne⟩    have hex : ∀ (T : Finset V), T.card = Fintype.card α →        ∃ f : SimpleGraph.Copy G (⊤ : SimpleGraph V), ∀ v, f v ∈ T := by      intro T hT      have hc : Fintype.card α = Fintype.card T := by rw [Fintype.card_coe, hT]      let e : α ≃ T := Fintype.equivOfCardEq hc      let g : α → V := fun a => (e a : V)      have hg : Function.Injective g := fun a b h => e.injective (Subtype.coe_injective h)      refine ⟨SimpleGraph.Copy.mk ⟨g, ?_⟩ hg, fun a => (e a).2⟩      intro a b hab      simp only [SimpleGraph.top_adj]      exact fun h => G.ne_of_adj hab (hg h)    let w : Finset V → ZMod t := fun T => if h : ∃ f : SimpleGraph.Copy G (⊤ : SimpleGraph V), ∀ v, f v ∈ T        then cw (Classical.choose h) else 0    have w_eq : ∀ (T : Finset V), T.card ≤ Fintype.card α + 1 →        ∀ (f : SimpleGraph.Copy G (⊤ : SimpleGraph V)), (∀ v, f v ∈ T) → w T = cw f := by      intro T hT f hf      have hhex : ∃ g : SimpleGraph.Copy G (⊤ : SimpleGraph V), ∀ v, g v ∈ T := ⟨f, hf⟩      show (if h : ∃ f : SimpleGraph.Copy G (⊤ : SimpleGraph V), ∀ v, f v ∈ T          then cw (Classical.choose h) else 0) = cw f      rw [dif_pos hhex]      exact key T hT _ _ (Classical.choose_spec hhex) hf    have hswap : ∀ (A B : Finset V), A.card = Fintype.card α → B.card = Fintype.card α →        (A ∪ B).card ≤ Fintype.card α + 1 → w A = w B := by      intro A B hA hB hAB      obtain ⟨f, hf⟩ := hex A hA      obtain ⟨g, hg⟩ := hex B hB      rw [w_eq A (by omega) f hf, w_eq B (by omega) g hg]      exact key (A ∪ B) hAB f g (fun v => Finset.mem_union_left _ (hf v))        (fun v => Finset.mem_union_right _ (hg v))    have hconst : ∀ (A B : Finset V), A.card = Fintype.card α → B.card = Fintype.card α →        w A = w B := by      intro A B hA hB      suffices H : ∀ k, ∀ (A B : Finset V), A.card = Fintype.card α → B.card = Fintype.card α →          (A \ B).card ≤ k → w A = w B from H _ A B hA hB le_rfl      intro k      induction k with      | zero =>        intro A B hA hB hk        have hsub : A ⊆ B :=          Finset.sdiff_eq_empty_iff_subset.mp (Finset.card_eq_zero.mp (Nat.le_zero.mp hk))        have hEq : A = B := Finset.eq_of_subset_of_card_le hsub (by omega)        rw [hEq]      | succ k ih =>        intro A B hA hB hk        by_cases hsub : A ⊆ B        · have hEq : A = B := Finset.eq_of_subset_of_card_le hsub (by omega)          rw [hEq]        · obtain ⟨a, ha⟩ := Finset.sdiff_nonempty.mpr hsub          have haA : a ∈ A := (Finset.mem_sdiff.mp ha).1          have haB : a ∉ B := (Finset.mem_sdiff.mp ha).2          have hcardEq : (B \ A).card = (A \ B).card := by            rw [Finset.card_sdiff, Finset.card_sdiff, Finset.inter_comm, hA, hB]          have hpos : 0 < (A \ B).card := Finset.card_pos.mpr ⟨a, ha⟩          obtain ⟨b, hb⟩ := Finset.card_pos.mp (by omega : 0 < (B \ A).card)          have hbB : b ∈ B := (Finset.mem_sdiff.mp hb).1          have hbA : b ∉ A := (Finset.mem_sdiff.mp hb).2          set A₁ : Finset V := insert b (A.erase a) with hA₁def          have hbnot : b ∉ A.erase a := fun h => hbA (Finset.mem_of_mem_erase h)          have hA₁card : A₁.card = Fintype.card α := by            have h1 := Finset.card_insert_of_notMem hbnot            have h2 := Finset.card_erase_add_one haA            rw [hA₁def]            omega          have hdiff : A₁ \ B = (A \ B).erase a := by            rw [hA₁def]            ext x            simp only [Finset.mem_sdiff, Finset.mem_insert, Finset.mem_erase]            constructor            · rintro ⟨hx, hxB⟩              rcases hx with hxb | ⟨hxa, hxA⟩              · subst hxb; exact absurd hbB hxB              · exact ⟨hxa, ⟨hxA, hxB⟩⟩            · intro h              exact ⟨Or.inr ⟨h.1, h.2.1⟩, h.2.2⟩          have hdiffcard : (A₁ \ B).card ≤ k := by            rw [hdiff, Finset.card_erase_of_mem ha]            omega          have hunion : (A ∪ A₁).card ≤ Fintype.card α + 1 := by            have hun : A ∪ A₁ = insert b A := by              rw [hA₁def]              ext x              simp only [Finset.mem_union, Finset.mem_insert, Finset.mem_erase]              constructor              · rintro (h | rfl | ⟨hxa, hxA⟩)                · exact Or.inr h                · exact Or.inl rfl                · exact Or.inr hxA              · rintro (rfl | h)                · exact Or.inr (Or.inl rfl)                · exact Or.inl h            rw [hun, Finset.card_insert_of_notMem hbA, hA]          exact (hswap A A₁ hA hA₁card hunion).trans (ih A₁ B hA₁card hB hdiffcard)    intro f₁    let S : Finset V := Finset.univ.image f₁    have hS : S.card = Fintype.card α := by      have hinj : Function.Injective (⇑f₁) := f₁.injective      rw [show S = Finset.univ.image f₁ from rfl, Finset.card_image_of_injective _ hinj]      simp    let T : Finset V := Sᶜ    have hT : T.card = Fintype.card α := by      rw [show T = Sᶜ from rfl, Finset.card_compl, hS, hV]      omega    obtain ⟨f₂, hf₂⟩ := hex T hT    refine ⟨f₂, ?_, ?_⟩    · rw [Set.disjoint_left]      intro x hx1 hx2      have hxS : x ∈ S := by        obtain ⟨v, hv⟩ := hx1        exact hv ▸ Finset.mem_image.mpr ⟨v, Finset.mem_univ v, rfl⟩      obtain ⟨v, hv⟩ := hx2      have hxT : f₂ v ∈ T := hf₂ v      rw [hv] at hxT      have hxS' : x ∉ S := by        simpa only [T, Finset.mem_compl] using hxT      exact hxS' hxS    · have h1 : w S = cw f₁ :=        w_eq S (by omega) f₁ (fun v => Finset.mem_image.mpr ⟨v, Finset.mem_univ v, rfl⟩)      have h2 : w T = cw f₂ := w_eq T (by omega) f₂ hf₂      have h3 : w S = w T := hconst S T hS hT      rw [← h1, ← h2]      exact h3/-- Universal defect bound (Lemma 3.7): for every graph G on n >= 1 vertices and every t >= 2, the defect def_t(G) is at most 1. -/theorem graph_defect_le_one {α : Type*} [Fintype α] [Nonempty α] (G : SimpleGraph α)    (t : ℕ) (ht : 2 ≤ t) :    let copyWeight (C : SimpleGraph.TopEdgeLabeling (Fin (2 * Fintype.card α)) (ZMod t))        (f : SimpleGraph.Copy G (⊤ : SimpleGraph (Fin (2 * Fintype.card α)))) : ZMod t :=      open Classical in ∑ e : G.edgeSet, C (f.mapEdgeSet e)    sInf {d : ℕ |      ∀ (C : SimpleGraph.TopEdgeLabeling (Fin (2 * Fintype.card α)) (ZMod t)),        (∀ (f₁ : SimpleGraph.Copy G (⊤ : SimpleGraph (Fin (2 * Fintype.card α)))),          ∃ (f₂ : SimpleGraph.Copy G (⊤ : SimpleGraph (Fin (2 * Fintype.card α)))),            Disjoint (Set.range f₁) (Set.range f₂) ∧            copyWeight C f₁ = copyWeight C f₂) ∨        (∃ (U : Finset (Fin (2 * Fintype.card α))), U.card ≤ Fintype.card α + d ∧          ∃ (f₁ f₂ : SimpleGraph.Copy G (⊤ : SimpleGraph (Fin (2 * Fintype.card α)))),            (∀ v, f₁ v ∈ U) ∧ (∀ v, f₂ v ∈ U) ∧            copyWeight C f₁ ≠ copyWeight C f₂)} ≤ 1 := by  have _ : 2 ≤ t := ht  dsimp only  apply Nat.sInf_le  intro C  exact graph_defect_le_one_aux G t (by simp) C
See it in the graphDiscuss this resultChallenge it