Prove by induction on $n$ that $K_n$ (the complete graph on n vertices) has a Hamiltonian cycle for all $n \geq 3$.
I understand this can be done not using induction, however I am very new to induction and need as much practice as possible. I have not properly attempted this question yet as I struggle with induction and the best way for me to learn and practice is by reading through examples as that helps me alot. If someone could show me how this is done by induction it would go a long way to helping me understand induction. Thank you
This problem should be trivial, I do not see why it would require induction. Let the vertices of $K_n$ be $v_1,v_2\dots v_n$ . Then $v_1,v_2,v_3,\dots v_n,v_1$ is a hamiltonian cycle.
Why?
It clearly repeats no vertices except for $v_1$ and every vertex appears. We also have that every pair of consecutive vertices are adjacent because the graph is complete. Finally if an edge was repeated then one of the vertices of the edge would be repeated, however the only vertex that is repeated is $v_1$ and the only two edges that connect $v_1$ are different (Notice that in $K_2$ this is not true when we consider $v_1v_2v_1$).