# Chromatic number of graph obtained from complete graph, by removing one Hamiltonian cycle

I need to find chromatic number of graph $$G$$ obtained from $$K_{2019}$$ , by removing one Hamiltonian cycle from it. I already did this example for even $$n$$. Now if $$V(G)=\{1,2,...,n\}$$, and if $$n$$ is even, "odd" vertices are forming graph $$K_{\frac{n}{2}}$$, so chromatic number was $$\ge \frac{n}{2}$$. Then it was easy to find one proper coloring with $$\frac{n}{2}$$ colors. But now, for $$2019$$, "even" vertices are forming graph $$K_{1009}$$ so chromatic number is $$\ge 1009$$. Now, I am not sure that there exists proper coloring with $$1009$$ colors, so chromatic number should be $$1010$$. But how to prove that there is not proper coloring with $$1009$$ colors?

Let the vertices of the complete graph $$K_n$$ be located at the vertices of a regular $$n$$-gon. Then the edges of $$K_n$$ are all possible diagonals of $$n$$-gon and all its sides. Now remove all sides of the $$n$$-gon. We obtain our graph $$G$$. Let $$n=2019$$. Suppose the vertices of $$G$$ are painted in $$1009$$ colors. Then we find three vertices colored in the same color. But then this coloring is not proper.