Question

6. Prove by induction on n that Kn (the complete graph on n vertices) has a Hamil tonian cycle for all n23. (Do not use Theorem 2.6 to do this.)

Answer 1

Given Base case = implies n = 3 Let, k_3 = Now 1 - 2 - 3 - 1 is a Hamiltonian cycle in k_3 Assume that n greaterthanorequalto u and result is true for n - 1 Consider the graph k_n on the vertex{1, .... , n} The induced sub graph on{1, ..... , n - 1} is complete graph on n - 1 vertices Therefore, By induction, this graph has a Hamiltonian cycle, say a_1 - a_2 - a_3 - ....... - a_n-1 - a_1 now, consider the cycle, a_1 rightarrow a_2 rightarrow a_3 rightarrow -....-a_n - 1 rightarrow n rightarrow a_1 in k_n This is a Hamiltonian cycle \r\n Hence by induction: for n greaterthanorequalto 3, k_n has Hamiltonian cycle