Hamiltonian $C_n$ Proof

Question

Prove that the complement of $C_n$ is Hamiltonian for $n\geq5.$

I know that since $C_5$ is Hamiltonian and $C_5$ is isomorphic to it's complement, then the complement of $C_5$ is Hamiltonian. Since $C_n$ is $2$-regular we know that the complement of $C_n$ is $(n-3)$-regular. So by Dirac's Theorem, $n-3\geq {n\over 2}$ for $n\geq6$. Thus the complement of $C_n$ is Hamiltonian for $n\geq5$.

I feel that this proof is satisfying. However, do I have to actually prove/show that $n-3\geq{n\over 2}$ for $n\geq6$? It seems obvious and that actually showing this is pedantic. What are your thoughts?

Answer 1

It depends on your audience. If this was a problem in a second or third year course, then you can probably make do without the proof of the claim. At the same time, if this was for a first year course emphasizing proper proof techniques and mathematical rigor, then I would probably include the proof of the claim.

As a rule of thumb, here is my take regarding situations like this: if you have to ask whether a statement needs proof, then the statement needs proof. The proof is only one line in this case anyways, so its probably worth the effort: $$n - 3 \ge \frac{n}{2} \iff \frac{n}{2} \ge 3 \iff n \ge 6$$

Answer 2

It's not too difficult to give an explicit construction.

For odd $n$, if the vertices are $\mathbb{Z}_n$, then the vertices of difference $1$ form an $n$-cycle, and the vertices of difference $2$ form a disjoint $n$-cycle.

For even $n$, we take the graph for $n-1$ above, and add in a new vertex $\infty$, replacing the edge between $0$ and $1$ with the path $0$ to $\infty$ to $1$, and replacing the edge between $2$ and $4$ with the the path $2$ to $\infty$ to $4$.

This is depicted below for $n=7$: