The chromatic number of the cycle graph $C_n$ is $2$ if $n$ is even and $3$ if $n$ is odd. A proof attempt

Question

The following theorem is well known. However, I am trying to get better at proofs in graph theory, so I use every opportunity to practice. I would be very happy about verifications and/or any improvements.

Theorem: The chromatic number $\chi$ of the cycle graph $C_n$ is $2$ if $n$ is even, and $3$ if $n$ is odd.

Proof: We set $C_n=P+v_{n-1}v_0$ with $P=v_0v_1v_2\cdots v_{n-1}$ being a path. For a simple graph with at least one edge, $\chi$ is at least $2$. Since a path is a non-empty graph, whereby all its vertices are distinct and linked by edges, we can find a valid colouring for $P$ by alternating two colors, say $1$ and $2$. Starting with $v_0$, we colour vertices with an even index with $1$ and vertices with an odd index with $2$. For $v_{n-1}$ we have two options. If $n$ is even, $n-1$ is odd, hence $v_{n-1}$ is coloured with $2$. If $n$ is odd, $n-1$ is even, hence $v_{n-1}$ is coloured with $1$. But in $C_n$, $v_{n-1}$ is adjacent to $v_0$, which is also coloured with $1$. Hence, the colouring is not valid. Therefore, if $n$ is odd, we need $3$ colours.

Answer 1

The chromatic number, like many other graph parameters, is the solution to an optimization problem, which means you need to get into the habit of giving two proofs for every value you compute: an upper bound (a coloring) and a lower bound (an argument for why you can't do better).

In your solution:

1. Most of your proof is an argument for why $\chi(C_{2k}) \le 2$: that we can color an even cycle with two colors. I'd emphasize a bit more that for every edge $v_iv_{i+1}$, as well as for the final edge, the two endpoints receive different colors when you do this. That's why we alternate, and that's the thing we need to check to know the coloring is proper.
2. You are careful to show that $\chi(C_{2k}) > 1$: that one color is not enough, because we have an edge. This is good!
3. As the comments already mention, you need to argue that $\chi(C_{2k+1}) \le 3$: that we can color an odd cycle with three colors.
4. You do try to show that $\chi(C_{2k+1}) > 2$, but I'm not entirely satisfied with your proof, and this is possibly because you're trying to do it at the same time as you're doing step 1. It would go better if you kept these two distinct steps separate.

Regarding your proof that $\chi(C_{2k+1}) > 2$: it is important to say that no matter how you try to color $C_{2k+1}$ with two colors, you'll fail. Your proof reads a lot more like saying "if you try to color $C_{2k+1}$ in the same way that we tried to color $C_{2k}$, you'll fail". That's bad logic - what if there's a different approach that does work?

The missing piece is subtle, and since the problem is easy I feel bad for criticizing you, but getting into good habits is important. Your proof would be fixed if you noted that the coloring where we alternate colors $1$ and $2$ is essentially the only way to try to color a cycle with two colors. (More precisely, there's two colorings, depending on if $v_0$ gets color $1$ or color $2$, and the argument is identical for both.)

Once we know that this coloring strategy is the only way to proceed, if we show that it fails for the odd cycle, this implies that two colors are not enough.