# Critical subgraph of the Kneser graph

Let the Kneser graph $$X_{n,k}$$ be the graph of subsets of $$[n]$$ with $$k$$ elements, such that two subsets are considered neighbors if they are disjoint.
One can prove, using some formulations of the Borsuk Ulam theorem, that the Kneser graph has chromatic number $$n-2k+2$$
A vertex critical subgraph is the smallest subgraph (smallest number of vertices) that has the same chromatic number as the full graph.

Question: what is the vertex critical subgraph of Kneser graph?
I read that it is the subgraph generated by the subsets which doesn't contain consecutive numbers, But I don't know how to prove it.

Indeed, Schrijver [Sch78] proved the following:

Theorem (Schrijver). Let $$\text{SG}_{n,k}$$ be the induced subgraph of $$X_{n,k}$$ whose vertices correspond to exactly those $$k$$-element subsets of $$[n]$$ that do not contain two adjacent elements modulo $$n$$. Then $$\text{SG}_{n,k}$$ is a vertex-critical graph of chromatic number $$n - 2k + 2$$.

Proof. See [Mat08, exercise 3.5.1], or [Sch78].

Remarks:

1. Schrijver uses slightly different notation: in his paper [Sch78], $$\text{KG}_{n,k}$$ denotes the Kneser graph $$X_{2n+k,n}$$.

2. Note that we consider subsets that do not contain adjacent elements modulo $$n$$. So if $$A \in V(\text{SG}_{n,k})$$ and $$n \in A$$, then $$1 \notin A$$.

3. The above theorem only proves that the vertex set of $$\text{SG}_{n,k}$$ is inclusionwise minimal among all subsets $$S \subseteq V(X_{n,k})$$ for which the induced subgraph $$X_{n,k}[S]$$ has the same chromatic number as $$X_{n,k}$$, and not that it has minimum cardinality. (I have never seen the term “vertex-critial” refer to smallest number of vertices; as far as I know it always refers to inclusionwise minimal vertex sets.)

References.

[Mat08]: Jiřı́ Matoušek, Using the Borsuk–Ulam Theorem, 2nd corrected printing, Universitext, Springer, 2008.

[Sch78]: A. Schrijver, Vertex-critical subgraphs of Kneser graphs, Nieuw Archief voor Wiskunde, 3rd Series, volume 26, pages 454–461. https://ir.cwi.nl/pub/9898/9898D.pdf