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.
 A: 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:

*

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


*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$.


*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
