[proofplan] We prove the upper bound by giving an explicit coloring: most vertices are colored by their least element, while all vertices whose least element lies in the final block receive one additional color. For the lower bound, we assume a coloring with too few colors and use [Gale's lemma](/theorems/6487) to place the ground set on a sphere so that every open hemisphere contains a $k$-set. The coloring then produces an open cover of the sphere by color-detecting sets, and the Lyusternik-Schnirelmann form of Borsuk-Ulam forces one color to appear in two antipodal hemispheres. Those hemispheres determine two disjoint $k$-sets of the same color, contradicting properness. [/proofplan] [step:Color each $k$-set by its least element outside the final block] Let $[n] := \{1,\dots,n\}$, and let $V$ denote the vertex set of $KG(n,k)$: \begin{align*} V := \{A \subset [n] : |A| = k\}. \end{align*} Define a coloring map \begin{align*} \varphi: V \to \{1,\dots,n - 2k + 2\} \end{align*} by \begin{align*} \varphi(A) := \min A \quad \text{if } \min A \leq n - 2k + 1, \end{align*} and \begin{align*} \varphi(A) := n - 2k + 2 \quad \text{if } \min A \geq n - 2k + 2. \end{align*} This is well-defined because every nonempty finite subset $A \subset [n]$ has a least element, and every vertex $A \in V$ is nonempty since $k \in \mathbb{N}$. We prove that $\varphi$ is proper. Suppose $A,B \in V$ are distinct vertices with $\varphi(A)=\varphi(B)$. If the common color is $i \leq n - 2k + 1$, then $\min A = \min B = i$, so $i \in A \cap B$ and $A,B$ are not adjacent. If the common color is $n - 2k + 2$, then \begin{align*} A \subset \{n - 2k + 2,\dots,n\} \end{align*} and \begin{align*} B \subset \{n - 2k + 2,\dots,n\}. \end{align*} The final block $\{n - 2k + 2,\dots,n\}$ has cardinality $2k-1$. If $A$ and $B$ were disjoint, then $A \cup B$ would contain $2k$ elements inside a set of size $2k-1$, which is impossible. Hence $A$ and $B$ are not adjacent. Thus $\varphi$ is a proper coloring using $n-2k+2$ colors, so \begin{align*} \chi(KG(n,k)) \leq n - 2k + 2. \end{align*} [/step] [step:Assume a coloring with fewer colors and place the ground set on a sphere] Set \begin{align*} d := n - 2k. \end{align*} Since $n \geq 2k$, we have $d \geq 0$. To prove the reverse inequality, suppose for contradiction that $KG(n,k)$ has a proper coloring with $m$ colors satisfying \begin{align*} m < n - 2k + 2. \end{align*} Since $m$ is an integer, this gives \begin{align*} m \leq d+1. \end{align*} Let \begin{align*} c: V \to \{1,\dots,m\} \end{align*} be such a proper coloring map. We use Gale's lemma for Kneser graphs (citing a result not yet in the wiki: Gale's lemma). It gives points $p_1,\dots,p_n \in S^d \subset \mathbb{R}^{d+1}$ such that for every $x \in S^d$, the open hemisphere \begin{align*} \{y \in S^d : x \cdot y > 0\} \end{align*} contains at least $k$ of the points $p_1,\dots,p_n$. Equivalently, for every $x \in S^d$, the index set \begin{align*} I_x := \{i \in [n] : x \cdot p_i > 0\} \end{align*} satisfies $|I_x| \geq k$. [/step] [step:Convert the coloring into an antipodal open cover of the sphere] For each color $j \in \{1,\dots,m\}$, define \begin{align*} A_j := \{x \in S^d : \text{there exists } S \subset I_x \text{ with } |S|=k \text{ and } c(S)=j\}. \end{align*} Each $A_j$ is an open subset of $S^d$. Indeed, if $x \in A_j$, choose a $k$-element set $S \subset I_x$ with $c(S)=j$. For every $i \in S$, the scalar product $x \cdot p_i$ is positive. Since $S$ is finite, the number \begin{align*} \delta := \min_{i \in S} x \cdot p_i \end{align*} is positive. The map \begin{align*} q_i: S^d \to \mathbb{R} \end{align*} defined by \begin{align*} q_i(y) := y \cdot p_i \end{align*} is continuous for every $i \in [n]$, so there is a neighbourhood $N_x \subset S^d$ of $x$ such that $y \cdot p_i > 0$ for all $y \in N_x$ and all $i \in S$. Hence $S \subset I_y$ for every $y \in N_x$, so $N_x \subset A_j$. The sets $A_1,\dots,A_m$ cover $S^d$. For any $x \in S^d$, Gale's lemma gives $|I_x| \geq k$, so we may choose a $k$-element subset $S \subset I_x$. The vertex $S \in V$ has a color $c(S) \in \{1,\dots,m\}$, and therefore $x \in A_{c(S)}$. [guided] The role of the sets $A_j$ is to translate a graph coloring into geometry on the sphere. A point $x \in S^d$ determines the open hemisphere facing $x$, and $I_x$ records exactly which ground-set labels lie in that hemisphere: \begin{align*} I_x := \{i \in [n] : x \cdot p_i > 0\}. \end{align*} For a color $j$, the set $A_j$ consists of those directions $x$ for which the hemisphere facing $x$ contains some $k$-element vertex of color $j$: \begin{align*} A_j := \{x \in S^d : \text{there exists } S \subset I_x \text{ with } |S|=k \text{ and } c(S)=j\}. \end{align*} We first verify openness. Fix $x \in A_j$. By definition, there is a $k$-element set $S \subset I_x$ with $c(S)=j$. The inclusion $S \subset I_x$ means that $x \cdot p_i > 0$ for each $i \in S$. Since $S$ has finitely many elements, the minimum \begin{align*} \delta := \min_{i \in S} x \cdot p_i \end{align*} is a positive real number. For each $i \in S$, define the continuous map \begin{align*} q_i: S^d \to \mathbb{R} \end{align*} by \begin{align*} q_i(y) := y \cdot p_i. \end{align*} Continuity of the finitely many maps $q_i$ gives a neighbourhood $N_x \subset S^d$ of $x$ on which $y \cdot p_i > 0$ for every $i \in S$. Therefore $S \subset I_y$ for every $y \in N_x$, and the same color-$j$ set $S$ witnesses $y \in A_j$. Thus $A_j$ is open. We next verify that the sets cover the sphere. Let $x \in S^d$. Gale's lemma says that the open hemisphere facing $x$ contains at least $k$ of the points $p_i$, which is precisely the statement $|I_x| \geq k$. Choose a $k$-element subset $S \subset I_x$. Since $S$ is a vertex of $KG(n,k)$, the coloring map assigns it some color $c(S) \in \{1,\dots,m\}$. By the definition of $A_{c(S)}$, the point $x$ lies in $A_{c(S)}$. Hence every point of $S^d$ lies in at least one of $A_1,\dots,A_m$. [/guided] [/step] [step:Use the antipodal covering theorem to force one color into opposite hemispheres] Because $m \leq d+1$, the open cover $A_1,\dots,A_m$ may be enlarged to an open cover of $S^d$ by exactly $d+1$ open sets by repeating one of the $A_j$ if necessary. By the [Lyusternik-Schnirelmann covering theorem](/theorems/6477), equivalently the covering form of the [Borsuk-Ulam theorem](/theorems/6462) (citing a result not yet in the wiki: Lyusternik-Schnirelmann covering theorem), some member of this cover contains an antipodal pair. Therefore there are a color $j \in \{1,\dots,m\}$ and a point $x \in S^d$ such that \begin{align*} x \in A_j \end{align*} and \begin{align*} -x \in A_j. \end{align*} By the definition of $A_j$, there are $k$-element subsets $S,T \subset [n]$ such that \begin{align*} S \subset I_x, \qquad c(S)=j, \end{align*} and \begin{align*} T \subset I_{-x}, \qquad c(T)=j. \end{align*} The sets $I_x$ and $I_{-x}$ are disjoint. If $i \in I_x \cap I_{-x}$, then $x \cdot p_i > 0$ and $(-x) \cdot p_i > 0$. But $(-x) \cdot p_i = -(x \cdot p_i)$, so this would force a real number to be both positive and negative. Hence \begin{align*} I_x \cap I_{-x} = \varnothing. \end{align*} Since $S \subset I_x$ and $T \subset I_{-x}$, it follows that \begin{align*} S \cap T = \varnothing. \end{align*} Thus $S$ and $T$ are adjacent vertices of $KG(n,k)$, but $c(S)=c(T)=j$, contradicting that $c$ is a proper coloring. This contradiction proves \begin{align*} \chi(KG(n,k)) \geq n - 2k + 2. \end{align*} [/step] [step:Combine the two inequalities] The explicit coloring gives \begin{align*} \chi(KG(n,k)) \leq n - 2k + 2. \end{align*} The contradiction argument gives \begin{align*} \chi(KG(n,k)) \geq n - 2k + 2. \end{align*} Combining these two inequalities yields \begin{align*} \chi(KG(n,k)) = n - 2k + 2. \end{align*} This is the desired chromatic number of the Kneser graph $KG(n,k)$. [/step]