¿Is there a way to know when does a complete bipartite graph $K_(n,m) $ contains a Hamiltonian cicle? I was trying to figure a secure way to prove a Hamiltonian Cycle on those kind of Graphs, using some theorems:
$ \bullet \quad \forall v \exists V \quad d(v)\ge 2 $ (degrees of every vertex must me $\ge $ 2)
$ \bullet \quad \forall S \subset S ,S \neq V, S \neq \varnothing \quad comp(G-S) \le \left\lvert S \right\rvert $
$ \bullet \quad$ G=(X,Y) Bipartite $\quad \left\lvert X \right\rvert =\left\lvert Y \right\rvert$
But every one of those theorems have Counter-Cases where they are not valid, so i just want to know if there is a secure way to determinate if a complete bipartite Graph is Hamiltonian.
Help really aprecciated!
Best Answer
Yes when $n=m$.
No when $n\ne m$. A Hamiltonian cycle must alternate between vertices on each "side" of the bipartition, so there must be an equal number of each, that is $m=n$, for such a cycle to exist.