in Graph Theory retagged by
458 views
3 votes
3 votes
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.
in Graph Theory retagged by
by
458 views

1 Answer

2 votes
2 votes
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.

Related questions