graph_defect_le_one
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.
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.
uses
Or.inrintro 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
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.
· 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⟩
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$.
uses
Fintype.card_coe,Fintype.equivOfCardEq,Subtype.coe_injective,SimpleGraph.Copy.mk,SimpleGraph.top_adjhave 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)
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$.
uses
Classical.choose,dif_pos,Classical.choose_speclet 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
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)$.
uses
Finset.mem_union_left,Finset.mem_union_righthave 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))
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.
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_lehave 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]
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.
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)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)$.
uses
Finset.card_image_of_injective,Finset.card_compl,Set.disjoint_left,Finset.mem_univ,Finset.mem_complintro 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
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.
uses
Nat.sInf_le,graph_defect_le_one_auxhave _ : 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.
- The auxiliary lemma `graph_defect_le_one_aux` establishes the dichotomy for $d = 1$ on an arbitrary vertex type $V$ of cardinality $2|\alpha|$. The main theorem instantiates $V$ with `Fin (2 * Fintype.card α)` and deduces the infimum bound from the fact that $1$ belongs to the set of valid defect values.
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 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