Let $n>1$ be an integer. We consider the line graphs of $K\_{2n}$ and $K\_{2n+1}$.


Since $\chi(L(K\_{2n})) = \omega(L(K\_{2n})) = 2n-1$ we get that removing a point from $L(K\_{2n})$ wouldn't change its chromatic number. (By $\omega(\cdot)$we denote the [clique number](https://en.wikipedia.org/wiki/Clique_(graph_theory)).)


But since $\chi(L(K\_{2n+1})) = 2n+1$ and $\omega(L(K\_{2n+1})) = 2n$, the above argument does not apply, and this raises the question: is $L(K\_{2n+1})$ [vertex-critical](https://en.wikipedia.org/wiki/Critical_graph) for all integers $n$? 



Is $L(K_{2n+1})$ vertex-critical?
It is not vertex-critical for $n>1$, since we may have at most $n$ edges of the same color, thus at most $2n^2<n(2n+1)-1$ edges totally of $2n$ colors.


