AFTD Auto-Formalizing Theoretical Domains

op_193_covering_color_obstruction

theoremverified

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

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.

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

    lines 7–13

    uses Finset.coe_map

        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⟩
  2. 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$.

    lines 19–35

    uses Finset.card_insert_of_notMem, Finset.card_map

        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⟩
  3. 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))$.

    lines 47–48

      rintro ⟨C⟩
      let c : {S : Finset (Fin m) // (SimpleGraph.cycleGraph m).IsNIndepSet k S} → Fin q := fun U => C (lift m k U)
  4. 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)$.

    lines 49–57

    uses Finset.disjoint_map, Finset.map_injective, congrArg, Subtype.val, Finset.card_pos.mp, Finset.disjoint_left.mp

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

    line 58

      obtain ⟨F, hc, hi, hcolors⟩ := hcover c hp
  6. Construct 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)$.

    lines 59–60

      let V := extra m k hk F hc hi
      obtain ⟨U, heq, hd⟩ := hcolors (C V)
  7. 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.

    lines 61–75

    uses Finset.disjoint_left.mpr, Finset.disjoint_map, Finset.mem_insert, Finset.disjoint_left.mp, congrArg, Subtype.val

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

    line 76

      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

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