/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtilErdős Problem 19
The Erdős–Faber–Lovász conjecture: if $G$ is an edge-disjoint union of $n$ copies of $K_n$, is $\chi(G) = n$?
We model $G$ by a family of $n$ vertex sets of size $n$ (the copies of $K_n$) which pairwise share at most one vertex and which cover the vertex type. Two copies of $K_n$ are edge-disjoint exactly when their vertex sets share at most one vertex.
References:
[Hi81] Hindman, N., On a conjecture of Erdős, Faber, and Lovász about $n$-colorings. Canad. J. Math. (1981).
[Ka92] Kahn, J., Coloring nearly-disjoint hypergraphs with $n + o(n)$ colors. J. Combin. Theory Ser. A (1992).
[KKKMO21] Kang, D. Y., Kelly, T., Kühn, D., Methuku, A. and Osthus, D., A proof of the Erdős–Faber–Lovász conjecture. Ann. of Math. (2023). arXiv:2101.04698
@[expose] public sectionopen Filternamespace Erdos19open scoped Classical in
A configuration of n pairwise edge-disjoint copies of $K_n$ covering the vertex type V.
structure EFLConfig (V : Type*) (n : ℕ) where
The vertex sets of the n cliques.
A : Fin n → Finset V
Each clique has exactly n vertices.
card_eq : ∀ i, (A i).card = nTwo different cliques share at most one vertex, i.e. they are edge-disjoint.
inter_le : ∀ i j, i ≠ j → (A i ∩ A j).card ≤ 1Every vertex lies in one of the cliques.
cover : ∀ v, ∃ i, v ∈ A inamespace EFLConfigvariable {V : Type*} {n : ℕ} (C : EFLConfig V n)The union graph: distinct vertices are adjacent iff they lie in a common clique.
def graph : SimpleGraph V where
Adj u v := u ≠ v ∧ ∃ i, u ∈ C.A i ∧ v ∈ C.A i
symm := ⟨fun _ _ ⟨h, i, hu, hv⟩ => ⟨h.symm, i, hv, hu⟩⟩
loopless := ⟨fun _ h => h.1 rfl⟩A vertex is shared if it lies in two different cliques.
def (v : V) : Prop := ∃ i j, i ≠ j ∧ v ∈ C.A i ∧ v ∈ C.A jopen scoped Classical inThe finite set of shared vertices.
noncomputable def : Finset V :=
((Finset.univ : Finset (Fin n)).biUnion C.A).filter C.IsSharedThe graph $G$ contains a copy of $K_n$, so $n \le \chi(G)$.
inr V:Type u_1n:ℕC:EFLConfig V nhn:n > 0hcl:C.graph.IsClique ↑(C.A ⟨0, hn⟩)⊢ ↑n ≤ C.graph.chromaticNumber
have := hcl.card_le_chromaticNumber inr V:Type u_1n:ℕC:EFLConfig V nhn:n > 0hcl:C.graph.IsClique ↑(C.A ⟨0, hn⟩)this:↑(C.A ⟨0, hn⟩).card ≤ C.graph.chromaticNumber⊢ ↑n ≤ C.graph.chromaticNumber
rwa [C.card_eq inr V:Type u_1n:ℕC:EFLConfig V nhn:n > 0hcl:C.graph.IsClique ↑(C.A ⟨0, hn⟩)this:↑n ≤ C.graph.chromaticNumber⊢ ↑n ≤ C.graph.chromaticNumber] inr V:Type u_1n:ℕC:EFLConfig V nhn:n > 0hcl:C.graph.IsClique ↑(C.A ⟨0, hn⟩)this:↑n ≤ C.graph.chromaticNumber⊢ ↑n ≤ C.graph.chromaticNumber at thisA vertex that is not shared lies in exactly one clique.
@[category API, AMS 5]
lemma {v : V} (hv : ¬ C.IsShared v) {i j : Fin n}
(hi : v ∈ C.A i) (hj : v ∈ C.A j) : i = j := by V:Type u_1n:ℕC:EFLConfig V nv:Vhv:¬C.IsShared vi:Fin nj:Fin nhi:v ∈ C.A ihj:v ∈ C.A j⊢ i = j
by_contra h V:Type u_1n:ℕC:EFLConfig V nv:Vhv:¬C.IsShared vi:Fin nj:Fin nhi:v ∈ C.A ihj:v ∈ C.A jh:¬i = j⊢ False
exact hv ⟨i, j, h, hi, hj⟩ All goals completed! 🐙open scoped Classical inIf the shared vertices can be coloured with $n$ colours so that shared vertices in a common clique get distinct colours, then $G$ is $n$-colourable.
@[category textbook, AMS 5]
theorem (c : V → Fin n)
(hc : ∀ i u v, u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = v) :
C.graph.Colorable n := by V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = v⊢ C.graph.Colorable n
-- private vertices and free colours of each clique
let P : Fin n → Finset V := fun i => (C.A i).filter (fun v => ¬ C.IsShared v) V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}⊢ C.graph.Colorable n
let U : Fin n → Finset V := fun i => (C.A i).filter C.IsShared V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)⊢ C.graph.Colorable n
let F : Fin n → Finset (Fin n) := fun i => Finset.univ \ (U i).image c V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)⊢ C.graph.Colorable n
have hcard : ∀ i, (P i).card ≤ (F i).card := by
intro i V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)i:Fin n⊢ (P i).card ≤ (F i).card V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).card⊢ C.graph.Colorable n
have h1 : (U i).card + (P i).card = n := by V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = v⊢ C.graph.Colorable n V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)i:Fin nh1:(U i).card + (P i).card = n⊢ (P i).card ≤ (F i).card V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).card⊢ C.graph.Colorable n
rw [← C.card_eq i V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)i:Fin n⊢ (U i).card + (P i).card = (C.A i).card V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)i:Fin n⊢ (U i).card + (P i).card = (C.A i).card V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)i:Fin nh1:(U i).card + (P i).card = n⊢ (P i).card ≤ (F i).card V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).card⊢ C.graph.Colorable n] V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)i:Fin n⊢ (U i).card + (P i).card = (C.A i).card V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)i:Fin nh1:(U i).card + (P i).card = n⊢ (P i).card ≤ (F i).card V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).card⊢ C.graph.Colorable n; exact Finset.card_filter_add_card_filter_not _ V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)i:Fin nh1:(U i).card + (P i).card = n⊢ (P i).card ≤ (F i).card V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).card⊢ C.graph.Colorable n V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)i:Fin nh1:(U i).card + (P i).card = n⊢ (P i).card ≤ (F i).card V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).card⊢ C.graph.Colorable n
have h2 : ((U i).image c).card ≤ (U i).card := Finset.card_image_le V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)i:Fin nh1:(U i).card + (P i).card = nh2:(Finset.image c (U i)).card ≤ (U i).card⊢ (P i).card ≤ (F i).card V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).card⊢ C.graph.Colorable n
have h3 : (F i).card = n - ((U i).image c).card := by V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = v⊢ C.graph.Colorable n V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)i:Fin nh1:(U i).card + (P i).card = nh2:(Finset.image c (U i)).card ≤ (U i).cardh3:(F i).card = n - (Finset.image c (U i)).card⊢ (P i).card ≤ (F i).card V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).card⊢ C.graph.Colorable n
simp [F, Finset.card_sdiff] V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)i:Fin nh1:(U i).card + (P i).card = nh2:(Finset.image c (U i)).card ≤ (U i).cardh3:(F i).card = n - (Finset.image c (U i)).card⊢ (P i).card ≤ (F i).card V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).card⊢ C.graph.Colorable n V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)i:Fin nh1:(U i).card + (P i).card = nh2:(Finset.image c (U i)).card ≤ (U i).cardh3:(F i).card = n - (Finset.image c (U i)).card⊢ (P i).card ≤ (F i).card V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).card⊢ C.graph.Colorable n
omega V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).card⊢ C.graph.Colorable n V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).card⊢ C.graph.Colorable n
have hne : ∀ i, Nonempty (P i ↪ F i) := fun i =>
Function.Embedding.nonempty_of_card_le (by V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardi:Fin n⊢ Fintype.card ↥(P i) ≤ Fintype.card ↥(F i) V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))⊢ C.graph.Colorable n simpa using hcard i All goals completed! 🐙 V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))⊢ C.graph.Colorable n) V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))⊢ C.graph.Colorable n
let e : ∀ i, P i ↪ F i := fun i => Classical.choice (hne i) V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯⊢ C.graph.Colorable n
let idx : V → Fin n := fun v => Classical.choose (C.cover v) V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯⊢ C.graph.Colorable n
have hidx : ∀ v, v ∈ C.A (idx v) := fun v => Classical.choose_spec (C.cover v) V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)⊢ C.graph.Colorable n
let col : V → Fin n := fun v =>
if h : C.IsShared v then c v
else ((e (idx v) ⟨v, Finset.mem_filter.2 ⟨hidx v, h⟩⟩ : F (idx v)) : Fin n) V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)⊢ C.graph.Colorable n
have col_priv : ∀ v (hv : ¬ C.IsShared v) j (hj : v ∈ C.A j),
col v = ((e j ⟨v, Finset.mem_filter.2 ⟨hj, hv⟩⟩ : F j) : Fin n) := by
intro v hv j hj V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)v:Vhv:¬C.IsShared vj:Fin nhj:v ∈ C.A j⊢ col v = ↑((e j) ⟨v, ⋯⟩) V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)⊢ C.graph.Colorable n
have key : ∀ i (hi : i = j) (p : v ∈ P i), ((e i ⟨v, p⟩ : F i) : Fin n) =
((e j ⟨v, Finset.mem_filter.2 ⟨hj, hv⟩⟩ : F j) : Fin n) := by V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = v⊢ C.graph.Colorable n V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)v:Vhv:¬C.IsShared vj:Fin nhj:v ∈ C.A jkey:∀ (i : Fin n), i = j → ∀ (p : v ∈ P i), ↑((e i) ⟨v, p⟩) = ↑((e j) ⟨v, ⋯⟩)⊢ col v = ↑((e j) ⟨v, ⋯⟩) V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)⊢ C.graph.Colorable n
rintro i rfl p V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)v:Vhv:¬C.IsShared vi:Fin nhj:v ∈ C.A ip:v ∈ P i⊢ ↑((e i) ⟨v, p⟩) = ↑((e i) ⟨v, ⋯⟩) V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)v:Vhv:¬C.IsShared vj:Fin nhj:v ∈ C.A jkey:∀ (i : Fin n), i = j → ∀ (p : v ∈ P i), ↑((e i) ⟨v, p⟩) = ↑((e j) ⟨v, ⋯⟩)⊢ col v = ↑((e j) ⟨v, ⋯⟩) V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)⊢ C.graph.Colorable n; rfl V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)v:Vhv:¬C.IsShared vj:Fin nhj:v ∈ C.A jkey:∀ (i : Fin n), i = j → ∀ (p : v ∈ P i), ↑((e i) ⟨v, p⟩) = ↑((e j) ⟨v, ⋯⟩)⊢ col v = ↑((e j) ⟨v, ⋯⟩) V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)⊢ C.graph.Colorable n V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)v:Vhv:¬C.IsShared vj:Fin nhj:v ∈ C.A jkey:∀ (i : Fin n), i = j → ∀ (p : v ∈ P i), ↑((e i) ⟨v, p⟩) = ↑((e j) ⟨v, ⋯⟩)⊢ col v = ↑((e j) ⟨v, ⋯⟩) V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)⊢ C.graph.Colorable n
simp only [col, dif_neg hv] V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)v:Vhv:¬C.IsShared vj:Fin nhj:v ∈ C.A jkey:∀ (i : Fin n), i = j → ∀ (p : v ∈ P i), ↑((e i) ⟨v, p⟩) = ↑((e j) ⟨v, ⋯⟩)⊢ ↑((e (idx v)) ⟨v, ⋯⟩) = ↑((e j) ⟨v, ⋯⟩) V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)⊢ C.graph.Colorable n
exact key _ (C.eq_of_not_shared hv (hidx v) hj) _ V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)⊢ C.graph.Colorable n V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)⊢ C.graph.Colorable n
have col_free : ∀ v (hv : ¬ C.IsShared v) j (hj : v ∈ C.A j), col v ∈ F j := by
intro v hv j hj V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)v:Vhv:¬C.IsShared vj:Fin nhj:v ∈ C.A j⊢ col v ∈ F j V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F j⊢ C.graph.Colorable n
rw [col_priv v hv j hj V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)v:Vhv:¬C.IsShared vj:Fin nhj:v ∈ C.A j⊢ ↑((e j) ⟨v, ⋯⟩) ∈ F j V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)v:Vhv:¬C.IsShared vj:Fin nhj:v ∈ C.A j⊢ ↑((e j) ⟨v, ⋯⟩) ∈ F j V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F j⊢ C.graph.Colorable n] V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)v:Vhv:¬C.IsShared vj:Fin nhj:v ∈ C.A j⊢ ↑((e j) ⟨v, ⋯⟩) ∈ F j V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F j⊢ C.graph.Colorable n; exact Subtype.property _ V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F j⊢ C.graph.Colorable n V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F j⊢ C.graph.Colorable n
refine ⟨SimpleGraph.Coloring.mk col ?_⟩ V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F j⊢ ∀ {v w : V}, C.graph.Adj v w → col v ≠ col w
rintro u v ⟨huv, j, hu, hv⟩ heq V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col v⊢ False
by_cases su : C.IsShared u pos V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:C.IsShared u⊢ Falseneg V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:¬C.IsShared u⊢ False <;> pos V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:C.IsShared u⊢ Falseneg V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:¬C.IsShared u⊢ False by_cases sv : C.IsShared v pos V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:¬C.IsShared usv:C.IsShared v⊢ Falseneg V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:¬C.IsShared usv:¬C.IsShared v⊢ False
· pos V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:C.IsShared usv:C.IsShared v⊢ False have : col u = c u := dif_pos su pos V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:C.IsShared usv:C.IsShared vthis:col u = c u⊢ False
have : col v = c v := dif_pos sv pos V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:C.IsShared usv:C.IsShared vthis✝:col u = c uthis:col v = c v⊢ False
exact huv (hc j u v hu hv su sv (by V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:C.IsShared usv:C.IsShared vthis✝:col u = c uthis:col v = c v⊢ c u = c v simp_all All goals completed! 🐙))
· neg V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:C.IsShared usv:¬C.IsShared v⊢ False have h1 := col_free v sv j hv neg V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:C.IsShared usv:¬C.IsShared vh1:col v ∈ F j⊢ False
have : col u = c u := dif_pos su neg V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:C.IsShared usv:¬C.IsShared vh1:col v ∈ F jthis:col u = c u⊢ False
simp only [F, Finset.mem_sdiff, Finset.mem_univ, true_and, Finset.mem_image] at h1 neg V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:C.IsShared usv:¬C.IsShared vthis:col u = c uh1:¬∃ a ∈ U j, c a = col v⊢ False
exact h1 ⟨u, Finset.mem_filter.2 ⟨hu, su⟩, by V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:C.IsShared usv:¬C.IsShared vthis:col u = c uh1:¬∃ a ∈ U j, c a = col v⊢ c u = col v rw [← this, V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:C.IsShared usv:¬C.IsShared vthis:col u = c uh1:¬∃ a ∈ U j, c a = col v⊢ col u = col v All goals completed! 🐙 heq V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:C.IsShared usv:¬C.IsShared vthis:col u = c uh1:¬∃ a ∈ U j, c a = col v⊢ col v = col v All goals completed! 🐙] All goals completed! 🐙⟩
· pos V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:¬C.IsShared usv:C.IsShared v⊢ False have h1 := col_free u su j hu pos V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:¬C.IsShared usv:C.IsShared vh1:col u ∈ F j⊢ False
have : col v = c v := dif_pos sv pos V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:¬C.IsShared usv:C.IsShared vh1:col u ∈ F jthis:col v = c v⊢ False
simp only [F, Finset.mem_sdiff, Finset.mem_univ, true_and, Finset.mem_image] at h1 pos V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:¬C.IsShared usv:C.IsShared vthis:col v = c vh1:¬∃ a ∈ U j, c a = col u⊢ False
exact h1 ⟨v, Finset.mem_filter.2 ⟨hv, sv⟩, by V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:¬C.IsShared usv:C.IsShared vthis:col v = c vh1:¬∃ a ∈ U j, c a = col u⊢ c v = col u rw [← this, V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:¬C.IsShared usv:C.IsShared vthis:col v = c vh1:¬∃ a ∈ U j, c a = col u⊢ col v = col u All goals completed! 🐙 ← heq V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:¬C.IsShared usv:C.IsShared vthis:col v = c vh1:¬∃ a ∈ U j, c a = col u⊢ col u = col u All goals completed! 🐙] All goals completed! 🐙⟩
· neg V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jheq:col u = col vsu:¬C.IsShared usv:¬C.IsShared v⊢ False rw [col_priv u su j hu, neg V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jsu:¬C.IsShared uheq:↑((e j) ⟨u, ⋯⟩) = col vsv:¬C.IsShared v⊢ False neg V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jsu:¬C.IsShared usv:¬C.IsShared vheq:↑((e j) ⟨u, ⋯⟩) = ↑((e j) ⟨v, ⋯⟩)⊢ False col_priv v sv j hv neg V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jsu:¬C.IsShared usv:¬C.IsShared vheq:↑((e j) ⟨u, ⋯⟩) = ↑((e j) ⟨v, ⋯⟩)⊢ Falseneg V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jsu:¬C.IsShared usv:¬C.IsShared vheq:↑((e j) ⟨u, ⋯⟩) = ↑((e j) ⟨v, ⋯⟩)⊢ False] at heqneg V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jsu:¬C.IsShared usv:¬C.IsShared vheq:↑((e j) ⟨u, ⋯⟩) = ↑((e j) ⟨v, ⋯⟩)⊢ False
have := (e j).injective (Subtype.ext heq) neg V:Type u_1n:ℕC:EFLConfig V nc:V → Fin nhc:∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = vP:Fin n → Finset V := fun i ↦ {v ∈ C.A i | ¬C.IsShared v}U:Fin n → Finset V := fun i ↦ Finset.filter C.IsShared (C.A i)F:Fin n → Finset (Fin n) := fun i ↦ Finset.univ \ Finset.image c (U i)hcard:∀ (i : Fin n), (P i).card ≤ (F i).cardhne:∀ (i : Fin n), Nonempty (↥(P i) ↪ ↥(F i))e:(i : Fin n) → ↥(P i) ↪ ↥(F i) := fun i ↦ Classical.choice ⋯idx:V → Fin n := fun v ↦ Classical.choose ⋯hidx:∀ (v : V), v ∈ C.A (idx v)col:V → Fin n := fun v ↦ if h : C.IsShared v then c v else ↑((e (idx v)) ⟨v, ⋯⟩)col_priv:∀ (v : V) (hv : ¬C.IsShared v) (j : Fin n) (hj : v ∈ C.A j), col v = ↑((e j) ⟨v, ⋯⟩)col_free:∀ (v : V), ¬C.IsShared v → ∀ (j : Fin n), v ∈ C.A j → col v ∈ F ju:Vv:Vhuv:u ≠ vj:Fin nhu:u ∈ C.A jhv:v ∈ C.A jsu:¬C.IsShared usv:¬C.IsShared vheq:↑((e j) ⟨u, ⋯⟩) = ↑((e j) ⟨v, ⋯⟩)this:⟨u, ⋯⟩ = ⟨v, ⋯⟩⊢ False
exact huv (congrArg Subtype.val this) All goals completed! 🐙open scoped Classical inThere are at most $\binom{n}{2}$ shared vertices, since two cliques share at most one vertex.
@[category textbook, AMS 5]
theorem : C.sharedSet.card ≤ n.choose 2 := by V:Type u_1n:ℕC:EFLConfig V n⊢ C.sharedSet.card ≤ n.choose 2
-- assign to each shared vertex a pair of cliques containing it
let f : V → Finset (Fin n) := fun v =>
if h : C.IsShared v then {Classical.choose h, Classical.choose (Classical.choose_spec h)}
else ∅ V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅⊢ C.sharedSet.card ≤ n.choose 2
have hf : ∀ v ∈ C.sharedSet, f v ∈ (Finset.univ : Finset (Fin n)).powersetCard 2 ∧
∀ x ∈ f v, v ∈ C.A x := by
intro v hv V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅v:Vhv:v ∈ C.sharedSet⊢ f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A x V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A x⊢ C.sharedSet.card ≤ n.choose 2
have hs : C.IsShared v := (Finset.mem_filter.1 hv).2 V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅v:Vhv:v ∈ C.sharedSeths:C.IsShared v⊢ f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A x V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A x⊢ C.sharedSet.card ≤ n.choose 2
obtain ⟨hij, hi, hj⟩ := Classical.choose_spec (Classical.choose_spec hs) V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅v:Vhv:v ∈ C.sharedSeths:C.IsShared vhij:Classical.choose hs ≠ Classical.choose ⋯hi:v ∈ C.A (Classical.choose hs)hj:v ∈ C.A (Classical.choose ⋯)⊢ f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A x V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A x⊢ C.sharedSet.card ≤ n.choose 2
simp only [f, dif_pos hs] V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅v:Vhv:v ∈ C.sharedSeths:C.IsShared vhij:Classical.choose hs ≠ Classical.choose ⋯hi:v ∈ C.A (Classical.choose hs)hj:v ∈ C.A (Classical.choose ⋯)⊢ {Classical.choose hs, Classical.choose ⋯} ∈ Finset.powersetCard 2 Finset.univ ∧
∀ x ∈ {Classical.choose hs, Classical.choose ⋯}, v ∈ C.A x V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A x⊢ C.sharedSet.card ≤ n.choose 2
refine ⟨Finset.mem_powersetCard.2 ⟨Finset.subset_univ _, Finset.card_pair hij⟩, ?_⟩ V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅v:Vhv:v ∈ C.sharedSeths:C.IsShared vhij:Classical.choose hs ≠ Classical.choose ⋯hi:v ∈ C.A (Classical.choose hs)hj:v ∈ C.A (Classical.choose ⋯)⊢ ∀ x ∈ {Classical.choose hs, Classical.choose ⋯}, v ∈ C.A x V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A x⊢ C.sharedSet.card ≤ n.choose 2
intro x hx V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅v:Vhv:v ∈ C.sharedSeths:C.IsShared vhij:Classical.choose hs ≠ Classical.choose ⋯hi:v ∈ C.A (Classical.choose hs)hj:v ∈ C.A (Classical.choose ⋯)x:Fin nhx:x ∈ {Classical.choose hs, Classical.choose ⋯}⊢ v ∈ C.A x V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A x⊢ C.sharedSet.card ≤ n.choose 2
rcases Finset.mem_insert.1 hx with rfl | hx inl V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅v:Vhv:v ∈ C.sharedSeths:C.IsShared vhij:Classical.choose hs ≠ Classical.choose ⋯hi:v ∈ C.A (Classical.choose hs)hj:v ∈ C.A (Classical.choose ⋯)hx:Classical.choose hs ∈ {Classical.choose hs, Classical.choose ⋯}⊢ v ∈ C.A (Classical.choose hs)inr V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅v:Vhv:v ∈ C.sharedSeths:C.IsShared vhij:Classical.choose hs ≠ Classical.choose ⋯hi:v ∈ C.A (Classical.choose hs)hj:v ∈ C.A (Classical.choose ⋯)x:Fin nhx✝:x ∈ {Classical.choose hs, Classical.choose ⋯}hx:x ∈ {Classical.choose ⋯}⊢ v ∈ C.A x V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A x⊢ C.sharedSet.card ≤ n.choose 2
· inl V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅v:Vhv:v ∈ C.sharedSeths:C.IsShared vhij:Classical.choose hs ≠ Classical.choose ⋯hi:v ∈ C.A (Classical.choose hs)hj:v ∈ C.A (Classical.choose ⋯)hx:Classical.choose hs ∈ {Classical.choose hs, Classical.choose ⋯}⊢ v ∈ C.A (Classical.choose hs) V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A x⊢ C.sharedSet.card ≤ n.choose 2 exact hi All goals completed! 🐙 V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A x⊢ C.sharedSet.card ≤ n.choose 2
· inr V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅v:Vhv:v ∈ C.sharedSeths:C.IsShared vhij:Classical.choose hs ≠ Classical.choose ⋯hi:v ∈ C.A (Classical.choose hs)hj:v ∈ C.A (Classical.choose ⋯)x:Fin nhx✝:x ∈ {Classical.choose hs, Classical.choose ⋯}hx:x ∈ {Classical.choose ⋯}⊢ v ∈ C.A x V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A x⊢ C.sharedSet.card ≤ n.choose 2 rw [Finset.mem_singleton.1 hx inr V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅v:Vhv:v ∈ C.sharedSeths:C.IsShared vhij:Classical.choose hs ≠ Classical.choose ⋯hi:v ∈ C.A (Classical.choose hs)hj:v ∈ C.A (Classical.choose ⋯)x:Fin nhx✝:x ∈ {Classical.choose hs, Classical.choose ⋯}hx:x ∈ {Classical.choose ⋯}⊢ v ∈ C.A (Classical.choose ⋯) inr V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅v:Vhv:v ∈ C.sharedSeths:C.IsShared vhij:Classical.choose hs ≠ Classical.choose ⋯hi:v ∈ C.A (Classical.choose hs)hj:v ∈ C.A (Classical.choose ⋯)x:Fin nhx✝:x ∈ {Classical.choose hs, Classical.choose ⋯}hx:x ∈ {Classical.choose ⋯}⊢ v ∈ C.A (Classical.choose ⋯) V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A x⊢ C.sharedSet.card ≤ n.choose 2]inr V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅v:Vhv:v ∈ C.sharedSeths:C.IsShared vhij:Classical.choose hs ≠ Classical.choose ⋯hi:v ∈ C.A (Classical.choose hs)hj:v ∈ C.A (Classical.choose ⋯)x:Fin nhx✝:x ∈ {Classical.choose hs, Classical.choose ⋯}hx:x ∈ {Classical.choose ⋯}⊢ v ∈ C.A (Classical.choose ⋯) V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A x⊢ C.sharedSet.card ≤ n.choose 2; exact hj V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A x⊢ C.sharedSet.card ≤ n.choose 2 V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A x⊢ C.sharedSet.card ≤ n.choose 2
have hinj : Set.InjOn f C.sharedSet := by
intro u hu v hv huv V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f v⊢ u = v V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSet⊢ C.sharedSet.card ≤ n.choose 2
obtain ⟨hpu, hu'⟩ := hf u hu V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A x⊢ u = v V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSet⊢ C.sharedSet.card ≤ n.choose 2
obtain ⟨hpv, hv'⟩ := hf v hv V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A xhpv:f v ∈ Finset.powersetCard 2 Finset.univhv':∀ x ∈ f v, v ∈ C.A x⊢ u = v V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSet⊢ C.sharedSet.card ≤ n.choose 2
obtain ⟨a, b, hab, hfab⟩ := Finset.card_eq_two.1 (Finset.mem_powersetCard.1 hpu).2 V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A xhpv:f v ∈ Finset.powersetCard 2 Finset.univhv':∀ x ∈ f v, v ∈ C.A xa:Fin nb:Fin nhab:a ≠ bhfab:f u = {a, b}⊢ u = v V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSet⊢ C.sharedSet.card ≤ n.choose 2
have ha : a ∈ f u := by V:Type u_1n:ℕC:EFLConfig V n⊢ C.sharedSet.card ≤ n.choose 2 V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A xhpv:f v ∈ Finset.powersetCard 2 Finset.univhv':∀ x ∈ f v, v ∈ C.A xa:Fin nb:Fin nhab:a ≠ bhfab:f u = {a, b}ha:a ∈ f u⊢ u = v V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSet⊢ C.sharedSet.card ≤ n.choose 2 rw [hfab V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A xhpv:f v ∈ Finset.powersetCard 2 Finset.univhv':∀ x ∈ f v, v ∈ C.A xa:Fin nb:Fin nhab:a ≠ bhfab:f u = {a, b}⊢ a ∈ {a, b} V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A xhpv:f v ∈ Finset.powersetCard 2 Finset.univhv':∀ x ∈ f v, v ∈ C.A xa:Fin nb:Fin nhab:a ≠ bhfab:f u = {a, b}⊢ a ∈ {a, b} V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A xhpv:f v ∈ Finset.powersetCard 2 Finset.univhv':∀ x ∈ f v, v ∈ C.A xa:Fin nb:Fin nhab:a ≠ bhfab:f u = {a, b}ha:a ∈ f u⊢ u = v V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSet⊢ C.sharedSet.card ≤ n.choose 2] V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A xhpv:f v ∈ Finset.powersetCard 2 Finset.univhv':∀ x ∈ f v, v ∈ C.A xa:Fin nb:Fin nhab:a ≠ bhfab:f u = {a, b}⊢ a ∈ {a, b} V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A xhpv:f v ∈ Finset.powersetCard 2 Finset.univhv':∀ x ∈ f v, v ∈ C.A xa:Fin nb:Fin nhab:a ≠ bhfab:f u = {a, b}ha:a ∈ f u⊢ u = v V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSet⊢ C.sharedSet.card ≤ n.choose 2; simp V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A xhpv:f v ∈ Finset.powersetCard 2 Finset.univhv':∀ x ∈ f v, v ∈ C.A xa:Fin nb:Fin nhab:a ≠ bhfab:f u = {a, b}ha:a ∈ f u⊢ u = v V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSet⊢ C.sharedSet.card ≤ n.choose 2 V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A xhpv:f v ∈ Finset.powersetCard 2 Finset.univhv':∀ x ∈ f v, v ∈ C.A xa:Fin nb:Fin nhab:a ≠ bhfab:f u = {a, b}ha:a ∈ f u⊢ u = v V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSet⊢ C.sharedSet.card ≤ n.choose 2
have hb : b ∈ f u := by V:Type u_1n:ℕC:EFLConfig V n⊢ C.sharedSet.card ≤ n.choose 2 V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A xhpv:f v ∈ Finset.powersetCard 2 Finset.univhv':∀ x ∈ f v, v ∈ C.A xa:Fin nb:Fin nhab:a ≠ bhfab:f u = {a, b}ha:a ∈ f uhb:b ∈ f u⊢ u = v V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSet⊢ C.sharedSet.card ≤ n.choose 2 rw [hfab V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A xhpv:f v ∈ Finset.powersetCard 2 Finset.univhv':∀ x ∈ f v, v ∈ C.A xa:Fin nb:Fin nhab:a ≠ bhfab:f u = {a, b}ha:a ∈ f u⊢ b ∈ {a, b} V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A xhpv:f v ∈ Finset.powersetCard 2 Finset.univhv':∀ x ∈ f v, v ∈ C.A xa:Fin nb:Fin nhab:a ≠ bhfab:f u = {a, b}ha:a ∈ f u⊢ b ∈ {a, b} V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A xhpv:f v ∈ Finset.powersetCard 2 Finset.univhv':∀ x ∈ f v, v ∈ C.A xa:Fin nb:Fin nhab:a ≠ bhfab:f u = {a, b}ha:a ∈ f uhb:b ∈ f u⊢ u = v V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSet⊢ C.sharedSet.card ≤ n.choose 2] V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A xhpv:f v ∈ Finset.powersetCard 2 Finset.univhv':∀ x ∈ f v, v ∈ C.A xa:Fin nb:Fin nhab:a ≠ bhfab:f u = {a, b}ha:a ∈ f u⊢ b ∈ {a, b} V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A xhpv:f v ∈ Finset.powersetCard 2 Finset.univhv':∀ x ∈ f v, v ∈ C.A xa:Fin nb:Fin nhab:a ≠ bhfab:f u = {a, b}ha:a ∈ f uhb:b ∈ f u⊢ u = v V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSet⊢ C.sharedSet.card ≤ n.choose 2; simp V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A xhpv:f v ∈ Finset.powersetCard 2 Finset.univhv':∀ x ∈ f v, v ∈ C.A xa:Fin nb:Fin nhab:a ≠ bhfab:f u = {a, b}ha:a ∈ f uhb:b ∈ f u⊢ u = v V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSet⊢ C.sharedSet.card ≤ n.choose 2 V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A xhpv:f v ∈ Finset.powersetCard 2 Finset.univhv':∀ x ∈ f v, v ∈ C.A xa:Fin nb:Fin nhab:a ≠ bhfab:f u = {a, b}ha:a ∈ f uhb:b ∈ f u⊢ u = v V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSet⊢ C.sharedSet.card ≤ n.choose 2
have hle := C.inter_le a b hab V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A xhpv:f v ∈ Finset.powersetCard 2 Finset.univhv':∀ x ∈ f v, v ∈ C.A xa:Fin nb:Fin nhab:a ≠ bhfab:f u = {a, b}ha:a ∈ f uhb:b ∈ f uhle:(C.A a ∩ C.A b).card ≤ 1⊢ u = v V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSet⊢ C.sharedSet.card ≤ n.choose 2
have hu2 : u ∈ C.A a ∩ C.A b := Finset.mem_inter.2 ⟨hu' a ha, hu' b hb⟩ V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A xhpv:f v ∈ Finset.powersetCard 2 Finset.univhv':∀ x ∈ f v, v ∈ C.A xa:Fin nb:Fin nhab:a ≠ bhfab:f u = {a, b}ha:a ∈ f uhb:b ∈ f uhle:(C.A a ∩ C.A b).card ≤ 1hu2:u ∈ C.A a ∩ C.A b⊢ u = v V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSet⊢ C.sharedSet.card ≤ n.choose 2
have hv2 : v ∈ C.A a ∩ C.A b :=
Finset.mem_inter.2 ⟨hv' a (huv ▸ ha), hv' b (huv ▸ hb)⟩ V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xu:Vhu:u ∈ ↑C.sharedSetv:Vhv:v ∈ ↑C.sharedSethuv:f u = f vhpu:f u ∈ Finset.powersetCard 2 Finset.univhu':∀ x ∈ f u, u ∈ C.A xhpv:f v ∈ Finset.powersetCard 2 Finset.univhv':∀ x ∈ f v, v ∈ C.A xa:Fin nb:Fin nhab:a ≠ bhfab:f u = {a, b}ha:a ∈ f uhb:b ∈ f uhle:(C.A a ∩ C.A b).card ≤ 1hu2:u ∈ C.A a ∩ C.A bhv2:v ∈ C.A a ∩ C.A b⊢ u = v V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSet⊢ C.sharedSet.card ≤ n.choose 2
exact Finset.card_le_one.1 hle u hu2 v hv2 V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSet⊢ C.sharedSet.card ≤ n.choose 2 V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSet⊢ C.sharedSet.card ≤ n.choose 2
have := Finset.card_le_card_of_injOn f (t := (Finset.univ : Finset (Fin n)).powersetCard 2)
(fun v hv => (hf v hv).1) hinj V:Type u_1n:ℕC:EFLConfig V nf:V → Finset (Fin n) := fun v ↦ if h : C.IsShared v then {Classical.choose h, Classical.choose ⋯} else ∅hf:∀ v ∈ C.sharedSet, f v ∈ Finset.powersetCard 2 Finset.univ ∧ ∀ x ∈ f v, v ∈ C.A xhinj:Set.InjOn f ↑C.sharedSetthis:C.sharedSet.card ≤ (Finset.powersetCard 2 Finset.univ).card⊢ C.sharedSet.card ≤ n.choose 2
simpa [Finset.card_powersetCard] using this All goals completed! 🐙end EFLConfigopen EFLConfigIf $G$ is an edge-disjoint union of $n$ copies of $K_n$, then is $\chi(G) = n$?
@[category research open, question, AMS 5]
theorem erdos_19 :
∀ (V : Type) (n : ℕ) (C : EFLConfig V n), C.graph.chromaticNumber = n := by ⊢ ∀ (V : Type) (n : ℕ) (C : EFLConfig V n), C.graph.chromaticNumber = ↑n
sorry All goals completed! 🐙open scoped Classical inThe Erdős–Faber–Lovász conjecture holds for $n \le 3$.
@[category test, AMS 5]
theorem erdos_19.variants.le_three {V : Type*} {n : ℕ} (C : EFLConfig V n) (hn : n ≤ 3) :
C.graph.chromaticNumber = n := by V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3⊢ C.graph.chromaticNumber = ↑n
refine le_antisymm ?_ C.le_chromaticNumber V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3⊢ C.graph.chromaticNumber ≤ ↑n
apply SimpleGraph.Colorable.chromaticNumber_le V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3⊢ C.graph.Colorable n
have hS : C.sharedSet.card ≤ n := by V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3⊢ C.graph.chromaticNumber = ↑n V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ n⊢ C.graph.Colorable n
have h1 := C.card_sharedSet_le V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3h1:C.sharedSet.card ≤ n.choose 2⊢ C.sharedSet.card ≤ n V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ n⊢ C.graph.Colorable n
have h2 : n.choose 2 ≤ n := by V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3⊢ C.graph.chromaticNumber = ↑n V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3h1:C.sharedSet.card ≤ n.choose 2h2:n.choose 2 ≤ n⊢ C.sharedSet.card ≤ n V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ n⊢ C.graph.Colorable n interval_cases n «0» V:Type u_1n:ℕC:EFLConfig V 0hn:0 ≤ 3h1:C.sharedSet.card ≤ Nat.choose 0 2⊢ Nat.choose 0 2 ≤ 0«1» V:Type u_1n:ℕC:EFLConfig V 1hn:1 ≤ 3h1:C.sharedSet.card ≤ Nat.choose 1 2⊢ Nat.choose 1 2 ≤ 1«2» V:Type u_1n:ℕC:EFLConfig V 2hn:2 ≤ 3h1:C.sharedSet.card ≤ Nat.choose 2 2⊢ Nat.choose 2 2 ≤ 2«3» V:Type u_1n:ℕC:EFLConfig V 3hn:3 ≤ 3h1:C.sharedSet.card ≤ Nat.choose 3 2⊢ Nat.choose 3 2 ≤ 3 V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3h1:C.sharedSet.card ≤ n.choose 2h2:n.choose 2 ≤ n⊢ C.sharedSet.card ≤ n V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ n⊢ C.graph.Colorable n <;> «0» V:Type u_1n:ℕC:EFLConfig V 0hn:0 ≤ 3h1:C.sharedSet.card ≤ Nat.choose 0 2⊢ Nat.choose 0 2 ≤ 0«1» V:Type u_1n:ℕC:EFLConfig V 1hn:1 ≤ 3h1:C.sharedSet.card ≤ Nat.choose 1 2⊢ Nat.choose 1 2 ≤ 1«2» V:Type u_1n:ℕC:EFLConfig V 2hn:2 ≤ 3h1:C.sharedSet.card ≤ Nat.choose 2 2⊢ Nat.choose 2 2 ≤ 2«3» V:Type u_1n:ℕC:EFLConfig V 3hn:3 ≤ 3h1:C.sharedSet.card ≤ Nat.choose 3 2⊢ Nat.choose 3 2 ≤ 3 V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3h1:C.sharedSet.card ≤ n.choose 2h2:n.choose 2 ≤ n⊢ C.sharedSet.card ≤ n V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ n⊢ C.graph.Colorable n decide V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3h1:C.sharedSet.card ≤ n.choose 2h2:n.choose 2 ≤ n⊢ C.sharedSet.card ≤ n V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ n⊢ C.graph.Colorable n V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3h1:C.sharedSet.card ≤ n.choose 2h2:n.choose 2 ≤ n⊢ C.sharedSet.card ≤ n V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ n⊢ C.graph.Colorable n
omega V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ n⊢ C.graph.Colorable n V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ n⊢ C.graph.Colorable n
-- colour the shared vertices injectively
let c : V → Fin n := fun v =>
if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩)
else ⟨0, by V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nv:Vh:v ∉ C.sharedSet⊢ 0 < n V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nc:V → Fin n := fun v ↦ if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩) else ⟨0, ⋯⟩⊢ C.graph.Colorable n
obtain ⟨i, hi⟩ := C.cover v V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nv:Vh:v ∉ C.sharedSeti:Fin nhi:v ∈ C.A i⊢ 0 < n V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nc:V → Fin n := fun v ↦ if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩) else ⟨0, ⋯⟩⊢ C.graph.Colorable n
rw [← C.card_eq i V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nv:Vh:v ∉ C.sharedSeti:Fin nhi:v ∈ C.A i⊢ 0 < (C.A i).card V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nv:Vh:v ∉ C.sharedSeti:Fin nhi:v ∈ C.A i⊢ 0 < (C.A i).card V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nc:V → Fin n := fun v ↦ if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩) else ⟨0, ⋯⟩⊢ C.graph.Colorable n] V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nv:Vh:v ∉ C.sharedSeti:Fin nhi:v ∈ C.A i⊢ 0 < (C.A i).card V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nc:V → Fin n := fun v ↦ if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩) else ⟨0, ⋯⟩⊢ C.graph.Colorable n; exact Finset.card_pos.2 ⟨v, hi⟩ All goals completed! 🐙 V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nc:V → Fin n := fun v ↦ if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩) else ⟨0, ⋯⟩⊢ C.graph.Colorable n⟩ V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nc:V → Fin n := fun v ↦ if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩) else ⟨0, ⋯⟩⊢ C.graph.Colorable n
refine C.colorable_of_sharedColoring c ?_ V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nc:V → Fin n := fun v ↦ if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩) else ⟨0, ⋯⟩⊢ ∀ (i : Fin n) (u v : V), u ∈ C.A i → v ∈ C.A i → C.IsShared u → C.IsShared v → c u = c v → u = v
intro i u v hu hv su sv huv V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nc:V → Fin n := fun v ↦ if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩) else ⟨0, ⋯⟩i:Fin nu:Vv:Vhu:u ∈ C.A ihv:v ∈ C.A isu:C.IsShared usv:C.IsShared vhuv:c u = c v⊢ u = v
have mu : u ∈ C.sharedSet := Finset.mem_filter.2 ⟨Finset.mem_biUnion.2 ⟨i, by V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nc:V → Fin n := fun v ↦ if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩) else ⟨0, ⋯⟩i:Fin nu:Vv:Vhu:u ∈ C.A ihv:v ∈ C.A isu:C.IsShared usv:C.IsShared vhuv:c u = c v⊢ i ∈ Finset.univ V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nc:V → Fin n := fun v ↦ if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩) else ⟨0, ⋯⟩i:Fin nu:Vv:Vhu:u ∈ C.A ihv:v ∈ C.A isu:C.IsShared usv:C.IsShared vhuv:c u = c vmu:u ∈ C.sharedSet⊢ u = v simp All goals completed! 🐙 V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nc:V → Fin n := fun v ↦ if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩) else ⟨0, ⋯⟩i:Fin nu:Vv:Vhu:u ∈ C.A ihv:v ∈ C.A isu:C.IsShared usv:C.IsShared vhuv:c u = c vmu:u ∈ C.sharedSet⊢ u = v, hu⟩, su⟩ V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nc:V → Fin n := fun v ↦ if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩) else ⟨0, ⋯⟩i:Fin nu:Vv:Vhu:u ∈ C.A ihv:v ∈ C.A isu:C.IsShared usv:C.IsShared vhuv:c u = c vmu:u ∈ C.sharedSet⊢ u = v
have mv : v ∈ C.sharedSet := Finset.mem_filter.2 ⟨Finset.mem_biUnion.2 ⟨i, by V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nc:V → Fin n := fun v ↦ if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩) else ⟨0, ⋯⟩i:Fin nu:Vv:Vhu:u ∈ C.A ihv:v ∈ C.A isu:C.IsShared usv:C.IsShared vhuv:c u = c vmu:u ∈ C.sharedSet⊢ i ∈ Finset.univ V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nc:V → Fin n := fun v ↦ if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩) else ⟨0, ⋯⟩i:Fin nu:Vv:Vhu:u ∈ C.A ihv:v ∈ C.A isu:C.IsShared usv:C.IsShared vhuv:c u = c vmu:u ∈ C.sharedSetmv:v ∈ C.sharedSet⊢ u = v simp All goals completed! 🐙 V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nc:V → Fin n := fun v ↦ if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩) else ⟨0, ⋯⟩i:Fin nu:Vv:Vhu:u ∈ C.A ihv:v ∈ C.A isu:C.IsShared usv:C.IsShared vhuv:c u = c vmu:u ∈ C.sharedSetmv:v ∈ C.sharedSet⊢ u = v, hv⟩, sv⟩ V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nc:V → Fin n := fun v ↦ if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩) else ⟨0, ⋯⟩i:Fin nu:Vv:Vhu:u ∈ C.A ihv:v ∈ C.A isu:C.IsShared usv:C.IsShared vhuv:c u = c vmu:u ∈ C.sharedSetmv:v ∈ C.sharedSet⊢ u = v
simp only [c, dif_pos mu, dif_pos mv] at huv V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nc:V → Fin n := fun v ↦ if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩) else ⟨0, ⋯⟩i:Fin nu:Vv:Vhu:u ∈ C.A ihv:v ∈ C.A isu:C.IsShared usv:C.IsShared vmu:u ∈ C.sharedSetmv:v ∈ C.sharedSethuv:Fin.castLE hS (C.sharedSet.equivFin ⟨u, mu⟩) = Fin.castLE hS (C.sharedSet.equivFin ⟨v, mv⟩)⊢ u = v
have := C.sharedSet.equivFin.injective (Fin.castLE_injective hS huv) V:Type u_1n:ℕC:EFLConfig V nhn:n ≤ 3hS:C.sharedSet.card ≤ nc:V → Fin n := fun v ↦ if h : v ∈ C.sharedSet then Fin.castLE hS (C.sharedSet.equivFin ⟨v, h⟩) else ⟨0, ⋯⟩i:Fin nu:Vv:Vhu:u ∈ C.A ihv:v ∈ C.A isu:C.IsShared usv:C.IsShared vmu:u ∈ C.sharedSetmv:v ∈ C.sharedSethuv:Fin.castLE hS (C.sharedSet.equivFin ⟨u, mu⟩) = Fin.castLE hS (C.sharedSet.equivFin ⟨v, mv⟩)this:⟨u, mu⟩ = ⟨v, mv⟩⊢ u = v
exact congrArg Subtype.val this All goals completed! 🐙Hindman [Hi81] proved the Erdős–Faber–Lovász conjecture for $n < 10$.
@[category research solved, AMS 5]
theorem erdos_19.variants.lt_ten :
∀ (V : Type) (n : ℕ) (C : EFLConfig V n), n < 10 → C.graph.chromaticNumber = n := by ⊢ ∀ (V : Type) (n : ℕ) (C : EFLConfig V n), n < 10 → C.graph.chromaticNumber = ↑n
sorry All goals completed! 🐙Kahn [Ka92] proved that $\chi(G) \le (1 + o(1))n$.
@[category research solved, AMS 5]
theorem erdos_19.variants.kahn :
∀ ε > (0 : ℝ), ∀ᶠ n in atTop, ∀ (V : Type) (C : EFLConfig V n),
C.graph.Colorable ⌊(1 + ε) * n⌋₊ := by ⊢ ∀ ε > 0, ∀ᶠ (n : ℕ) in atTop, ∀ (V : Type) (C : EFLConfig V n), C.graph.Colorable ⌊(1 + ε) * ↑n⌋₊
sorry All goals completed! 🐙Kang, Kelly, Kühn, Methuku and Osthus [KKKMO21] proved the Erdős–Faber–Lovász conjecture for all sufficiently large $n$.
@[category research solved, AMS 5]
theorem erdos_19.variants.large_n :
∀ᶠ n in atTop, ∀ (V : Type) (C : EFLConfig V n), C.graph.chromaticNumber = n := by ⊢ ∀ᶠ (n : ℕ) in atTop, ∀ (V : Type) (C : EFLConfig V n), C.graph.chromaticNumber = ↑n
sorry All goals completed! 🐙end Erdos19