op_193_covering_color_obstruction
If every proper q-coloring of the cycle-stable k-set graph has a stable (k-1)-set whose disjoint stable k-sets realize all q colors, then the stable k-set graph of the cycle plus an isolated vertex is not q-colorable.
Statement
theorem op_193_covering_color_obstruction (m k q : ℕ) (hk : 1 ≤ k)
(hcover : ∀ c : {S : Finset (Fin m) // (SimpleGraph.cycleGraph m).IsNIndepSet k S} → Fin q,
(∀ U W, Disjoint U.1 W.1 → c U ≠ c W) →
∃ F : Finset (Fin m), F.card = k-1 ∧ (SimpleGraph.cycleGraph m).IsIndepSet (↑F : Set (Fin m)) ∧
∀ i : Fin q, ∃ U, c U = i ∧ Disjoint F U.1) :
¬ (GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).Colorable q- Source
- The final coloring obstruction in arXiv:2610.17884 Theorem 1.4.
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- GStableKneserFor a simple graph G and a natural number k, the G-stable Kneser graph KG(G, k) is the simple graph whose vertices are the independent…
- Used by 2
- op_193_cubic_noncolorable_if_cycle_lowerFor k at least 3 and m at least k((k-1)²+1), if the cycle-stable k-set graph is not (m-2k+1)-colorable, then adding an isolated vertex…
- op_193_noncolorable_if_stable_anchor_avoidanceIf the cycle-only stable k-set graph is not (m-2k+1)-colorable and every family of m-2k+2 stable k-sets can be met in at most one point by…
The proof, explained
To show that the stable Kneser graph of the disjoint sum of an m-cycle and an isolated vertex is not q-colorable, we assume for contradiction that a proper q-coloring C exists. By lifting stable k-sets of the cycle into the sum graph, C induces a proper q-coloring c of the cycle's stable Kneser graph. The covering hypothesis then provides a stable (k-1)-set F whose disjoint stable k-sets achieve every color. Adding the isolated vertex to F yields a stable k-set V whose color C(V) must be matched by some stable k-set U disjoint from F, which creates two adjacent vertices V and lift(U) sharing the same color, contradicting that C is proper.
Embedding a stable k-set of the cycle graph into the disjoint sum with an isolated vertex produces a stable k-set.
The constructor `lift` maps a stable $k$-set $U$ of $C_m$ via `Sum.inl` into $C_m \oplus K_1$. Edges in the sum graph between elements of $C_m$ are exactly edges of $C_m$, so independence is preserved; since `Sum.inl` is an embedding, cardinality $k$ is also preserved.
uses
Finset.coe_maprefine ⟨?_, ?_⟩ · rw [Finset.coe_map] rintro _ ⟨u, hu, rfl⟩ _ ⟨v, hv, rfl⟩ hne dsimp [SimpleGraph.sum] intro h exact U.2.isIndepSet hu hv (by simpa using hne) h · simpa using U.2.card_eq⟩
Adding the isolated vertex to the embedded image of a stable (k-1)-set yields a stable k-set of the sum graph. automation
The constructor `extra` inserts the isolated vertex `Sum.inr ()` into the image of a stable $(k-1)$-set $F$. It is independent because $F$ has no internal edges, the isolated vertex has no edges, and the sum graph contains no edges between components. Its cardinality is $(k-1) + 1 = k$ since $k \ge 1$ and the isolated vertex is disjoint from the embedding of $C_m$.
uses
Finset.card_insert_of_notMem,Finset.card_maprefine ⟨?_, ?_⟩ · intro x hx y hy hne hadj cases x with | inl x => cases y with | inl y => have hx' : x ∈ F := by simpa using hx have hy' : y ∈ F := by simpa using hy exact hi hx' hy' (by simpa using hne) hadj | inr y => cases hadj | inr x => cases y with | inl y => cases hadj | inr y => cases x; cases y; exact hne rfl · rw [Finset.card_insert_of_notMem] · rw [Finset.card_map, hc]; omega · simp⟩
Assume for contradiction that the stable Kneser graph of $C_m \oplus K_1$ is q-colorable, and pull back the coloring to stable k-sets of $C_m$.
Suppose there exists a proper $q$-coloring $C$ of $KG_{\text{stab}}(C_m \oplus K_1, k)$. We define an induced coloring $c$ on the stable $k$-sets of $C_m$ by setting $c(U) = C(\text{lift}(U))$.
rintro ⟨C⟩ let c : {S : Finset (Fin m) // (SimpleGraph.cycleGraph m).IsNIndepSet k S} → Fin q := fun U => C (lift m k U)
The induced coloring c is a proper coloring of the stable Kneser graph of the cycle graph.
If $U$ and $W$ are disjoint stable $k$-sets of $C_m$, their lifted images under `Sum.inl` are disjoint by `Finset.disjoint_map`. Since $k \ge 1$, $U$ is nonempty, so disjointness implies $U \neq W$, hence $\text{lift}(U) \neq \text{lift}(W)$ by injectivity. Thus the two lifted sets form an edge in the stable Kneser graph of $C_m \oplus K_1$, which means $C(\text{lift}(U)) \neq C(\text{lift}(W))$, i.e., $c(U) \neq c(W)$.
uses
Finset.disjoint_map,Finset.map_injective,congrArg,Subtype.val,Finset.card_pos.mp,Finset.disjoint_left.mphave hp : ∀ U W, Disjoint U.1 W.1 → c U ≠ c W := by intro U W hd apply C.valid refine ⟨(Finset.disjoint_map Function.Embedding.inl).mpr hd, ?_⟩ intro h have heq : U.1 = W.1 := Finset.map_injective Function.Embedding.inl (congrArg Subtype.val h) have hp : U.1.Nonempty := Finset.card_pos.mp (by rw [U.2.card_eq]; omega) obtain ⟨x, hx⟩ := hp exact (Finset.disjoint_left.mp hd) hx (by rw [← heq]; exact hx)
There exists a stable (k-1)-set F whose disjoint stable k-sets realize all q colors under c.
Applying the covering hypothesis `hcover` to the proper coloring $c$ yields a stable $(k-1)$-set $F$ of $C_m$ such that for each color $i \in \{0, \dots, q-1\}$, there is a stable $k$-set disjoint from $F$ with color $i$.
obtain ⟨F, hc, hi, hcolors⟩ := hcover c hpConstruct a stable k-set V containing the isolated vertex and find a disjoint stable k-set U in the cycle with the same color.
Let $V = \text{extra}(F)$ be the stable $k$-set obtained by adding the isolated vertex to $F$. Its color is $C(V)$. By the property of $F$, there exists a stable $k$-set $U$ in $C_m$ disjoint from $F$ such that $c(U) = C(V)$.
let V := extra m k hk F hc hi obtain ⟨U, heq, hd⟩ := hcolors (C V)
The vertices V and lift(U) are adjacent in the stable Kneser graph.
$V$ and $\text{lift}(U)$ are disjoint because any element in $V$ is either the isolated vertex (which is not in the image of $U$) or in the image of $F$ (which is disjoint from $U$). They are distinct because $V$ contains the isolated vertex while $\text{lift}(U)$ does not.
uses
Finset.disjoint_left.mpr,Finset.disjoint_map,Finset.mem_insert,Finset.disjoint_left.mp,congrArg,Subtype.valhave he : (GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).Adj V (lift m k U) := by refine ⟨?_, ?_⟩ · apply Finset.disjoint_left.mpr intro x hx hy have hmapped : Disjoint (F.map (Function.Embedding.inl : Fin m ↪ Fin m ⊕ Unit)) (U.1.map (Function.Embedding.inl : Fin m ↪ Fin m ⊕ Unit)) := (Finset.disjoint_map (Function.Embedding.inl : Fin m ↪ Fin m ⊕ Unit)).mpr hd simp only [V, extra, Finset.mem_insert] at hx rcases hx with hx | hx · subst x; simp [lift] at hy · exact (Finset.disjoint_left.mp hmapped) hx hy · intro heq' have hmem : (Sum.inr () : Fin m ⊕ Unit) ∈ V.1 := by simp [V, extra] rw [congrArg Subtype.val heq'] at hmem simp [lift] at hmem
The coloring C assigns the same color to the adjacent vertices V and lift(U), yielding a contradiction.
Since $V$ and $\text{lift}(U)$ are adjacent, $C$ must assign them distinct colors by properness. But $C(\text{lift}(U)) = c(U) = C(V)$ by construction, which contradicts properness. Thus no proper $q$-coloring exists.
exact C.valid he (by simpa [c] using heq.symm)
Finset.coe_map- The coercive image of a mapped finset equals the image under the embedding of the coerced finset.
Finset.card_insert_of_notMem- Inserting an element not in a finset increases its cardinality by 1.
Finset.card_map- Mapping a finset along an embedding preserves its cardinality.
Finset.disjoint_map- Two mapped finsets under an embedding are disjoint if and only if the original finsets are disjoint.
Finset.map_injective- Mapping by an embedding is an injective operation on finsets.
congrArg- Congruence: applying a function to equal arguments yields equal values.
Subtype.val- Extracting the underlying value from a subtype.
Finset.card_pos.mp- A finset with strictly positive cardinality is nonempty.
Finset.disjoint_left.mp- If two sets are disjoint, any element of the first does not belong to the second.
Finset.disjoint_left.mpr- If no element of the first set belongs to the second, the two sets are disjoint.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
namespace Inbox777Bridgevariable (m k q : ℕ)def lift (U : {S : Finset (Fin m) // (SimpleGraph.cycleGraph m).IsNIndepSet k S}) : {T : Finset (Fin m ⊕ Unit) // ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)).IsNIndepSet k T} := ⟨U.1.map Function.Embedding.inl, by refine ⟨?_, ?_⟩ · rw [Finset.coe_map] rintro _ ⟨u, hu, rfl⟩ _ ⟨v, hv, rfl⟩ hne dsimp [SimpleGraph.sum] intro h exact U.2.isIndepSet hu hv (by simpa using hne) h · simpa using U.2.card_eq⟩def extra (hk : 1 ≤ k) (F : Finset (Fin m)) (hc : F.card = k-1) (hi : (SimpleGraph.cycleGraph m).IsIndepSet (↑F : Set (Fin m))) : {T : Finset (Fin m ⊕ Unit) // ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)).IsNIndepSet k T} := ⟨insert (Sum.inr ()) (F.map Function.Embedding.inl), by refine ⟨?_, ?_⟩ · intro x hx y hy hne hadj cases x with | inl x => cases y with | inl y => have hx' : x ∈ F := by simpa using hx have hy' : y ∈ F := by simpa using hy exact hi hx' hy' (by simpa using hne) hadj | inr y => cases hadj | inr x => cases y with | inl y => cases hadj | inr y => cases x; cases y; exact hne rfl · rw [Finset.card_insert_of_notMem] · rw [Finset.card_map, hc]; omega · simp⟩end Inbox777Bridgeopen Inbox777Bridgetheorem op_193_covering_color_obstruction (m k q : ℕ) (hk : 1 ≤ k) (hcover : ∀ c : {S : Finset (Fin m) // (SimpleGraph.cycleGraph m).IsNIndepSet k S} → Fin q, (∀ U W, Disjoint U.1 W.1 → c U ≠ c W) → ∃ F : Finset (Fin m), F.card = k-1 ∧ (SimpleGraph.cycleGraph m).IsIndepSet (↑F : Set (Fin m)) ∧ ∀ i : Fin q, ∃ U, c U = i ∧ Disjoint F U.1) : ¬ (GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).Colorable q := by rintro ⟨C⟩ let c : {S : Finset (Fin m) // (SimpleGraph.cycleGraph m).IsNIndepSet k S} → Fin q := fun U => C (lift m k U) have hp : ∀ U W, Disjoint U.1 W.1 → c U ≠ c W := by intro U W hd apply C.valid refine ⟨(Finset.disjoint_map Function.Embedding.inl).mpr hd, ?_⟩ intro h have heq : U.1 = W.1 := Finset.map_injective Function.Embedding.inl (congrArg Subtype.val h) have hp : U.1.Nonempty := Finset.card_pos.mp (by rw [U.2.card_eq]; omega) obtain ⟨x, hx⟩ := hp exact (Finset.disjoint_left.mp hd) hx (by rw [← heq]; exact hx) obtain ⟨F, hc, hi, hcolors⟩ := hcover c hp let V := extra m k hk F hc hi obtain ⟨U, heq, hd⟩ := hcolors (C V) have he : (GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).Adj V (lift m k U) := by refine ⟨?_, ?_⟩ · apply Finset.disjoint_left.mpr intro x hx hy have hmapped : Disjoint (F.map (Function.Embedding.inl : Fin m ↪ Fin m ⊕ Unit)) (U.1.map (Function.Embedding.inl : Fin m ↪ Fin m ⊕ Unit)) := (Finset.disjoint_map (Function.Embedding.inl : Fin m ↪ Fin m ⊕ Unit)).mpr hd simp only [V, extra, Finset.mem_insert] at hx rcases hx with hx | hx · subst x; simp [lift] at hy · exact (Finset.disjoint_left.mp hmapped) hx hy · intro heq' have hmem : (Sum.inr () : Fin m ⊕ Unit) ∈ V.1 := by simp [V, extra] rw [congrArg Subtype.val heq'] at hmem simp [lift] at hmem exact C.valid he (by simpa [c] using heq.symm)