Define the $n,k$ Kneser Graph $KN(n,k)$ as follows: $V=\binom{[n]}{k}$ and $ E=\{ (a,b) |a,b\in V, a\cap b = \emptyset\} $. In other words, the vertices are the $k$-sets of an $n$-element ground set and we connect them if they are disjoint.
The Kneser–Lovász Theorem showed that $\chi(KN(n,k))=n-2k+2$.
Now define $\mu(n,k)$ to be the minimum number of monochromatic edges in $KN(n,k)$ colored with $n-2k+1$ colors (so one less color).
I have already shown that $\mu(n,k)\leq\binom{2k-1}{k}$. Essentially, I created $n-2k+2$ disjoint independent sets where the first $n-2k+1$ of them had the same smallest element and the last set just had all the rest. Then, I combined the last two independent sets and showed that the corresponding graph had at most $\binom{2k-1}{k}$ monochromatic edges.
$\textbf{QUESTION:}$ I am struggling to show equality holds when (1) $k=2$ and (2) $n=2k+1$.
I fiddled around with it, but I was not able to find any leads on where the proof would be.
Any help is greatly appreciated.
\textbf{UPDATE:}
I have been thinking about (1) for a bit and I speculate that it has to do with the Erdos-Ko-Rado Theorem that states that the largest family of $k$ element subsets of an $n$-set such that each subset is pairwise intersecting has $\binom{n-1}{k-1}$ sets.
This means that the largest independent set in $KN(n,2)$ has size $\binom{n-1}{2-1}=n-1$.
To add a useful fact, each vertex is adjacent to the number of sets it is disjoint from, so $\binom{n-2}{2}$ sets.
This one is tough but here is what I have:
Recall that the Schrijver Graph $SG(n,k)$ is defined similarly to the Kneser graph, but no $k$-set can contain both $i$ and $i+1$ (or 1 and $n$, for that matter). We also have that $\chi(SG(n,k)=n-2k+2$.
(1) $k=2$ means we need to show that $\mu(n,2)=3$. This one is just checking cases, but essentially you need to show that there if you were to delete only two edges, the graph still cannot be properly colored with only $n-2k+1$ colors. So what you can do is show that no matter what two edges you delete (you can fix $\{12,34\}$ WLOG), then there will always be some instance of $SG(n,2)$ in the graph. To do this, you need to come up with a way of reindexing the $k$-sets such that edges are preserved, but the edges you deleted involved a vertex that had consecutive elements in it.
(2) $n=2k+1$ means with need to show $\mu(2k+1,k)=\binom{2k-1}{k}$. Moreover, we just show that to be able to 2-color the graph, $\binom{2k-1}{k}$ edges must be deleted. To do this, you can count the total number of unique $SG(2k+1,k)$'s are in the $KN(2k+1,k)$ and then count the number that uses a fixed arbitrary edge. To do this, you need to count the number of unique ways, up to rotation and reflection, you can rearrange the order of the elements for the former and you can again count the number of ways you can reindex the elements of each vertex such that consecutive elements do not occur for the latter. You should get $\frac{1}{2}(n-1)!$ and $k!k!$ respectively. Hence, by removing an edge, you remove $k!k!$ Schrijver graphs. Therefore, dividing the two quantities should give you the number of edges you need to delete before all Schriver graphs are gone. This gives you $\frac{1}{2}\binom{2k}{k}=\binom{2k-1}{k-1}$.