The Gateway to Computer Science Excellence
+2 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 by Boss | 114 views

1 Answer

+1 vote
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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,215 questions
60,013 answers
94,700 users