UGC NET CSE | June 2014 | Part 2 | Question: 23

Question

Consider a complete bipartite graph $k_{m,n}$. For which values of $m$ and $n$ does this, complete graph have a Hamilton circuit 

• A. $m = 3, n = 2$
• B. $m = 2, n = 3$ 
• C. $m = n > 2$
• D. $m = n > 3$ 

Answer 1

K_m,n has a Hamilton circuit if and only if m=n>2

 

Comments

K₂₂  also has Hamilton circuit  then why >2.It can be = also.

---

Neeraj Singh do you know what is circuit?

---

@leensharma. Yes, Neeraj is right. K₂₂ also contains hamiltonian ckt. But the questions asks that which is the most appropriate option. It doesnt state any fact.

---

yes I know. Circuit  is path  similar to a cycle that starts and ends at the same vertex.  K₂₂ also contains hamiltonian ckt.

Answer 2

There should be equal vertices in both the partitions, and the count of each partition should be at least 2.

So for $K_{m,n}$, $m=n\geq 2$

Option C is the closest match.