ACE ACADEMY BOOKLET

Question

Which of the following is $\textbf{not}$ TRUE?

(a) In a complete graph $K_n$ ($n$ $\geq$ $3$), Hamiltonian cycle exists for all n.

(b) In a complete bipartite graph $K_{m,n}$ (m $\geq$ 2 and  n $\geq$2), Hamiltonian cycle exists $\Leftrightarrow$ $m$ $=$ $n$.

(C) In a cycle graph $C_n$($n \geq$3), Hamiltonian cycle exits for all $n$

(d) In a wheel graph $W_n$ ($n \geq 4$), Hamiltonian cycle exits $\Leftrightarrow$ $n$ is even.

Answer 1

Hamiltonian cycle will exist in all of the above mentioned graphs. It won't exist in star graph or complete bi-partite graph with minimum number of edges. But as it is mentioned m=n and m,n >=2, hamiltonian cycle will be existing in all graphs. But by going on conditions Option D can be considered as false because it says that wheel graph has hamiltonian cycle if and only if n is even but it will exist in n is odd case also. By going this analogy, I think option:D will be false.

Comments

for wheel graph $W_n$ hamiltonian cycle exist for all value of $n$.