Seien \(v_1,\ldots,v_m\),\(w_1,\ldots,w_n\) die Knoten der beiden Partitionskomponenten des \(K_{m,n}\). Pfade sind dort durch Bipartitheit von der Form "VWVWVW...", der einzige Weg, einen Hamiltonkreis zu kreieren ist also, wenn du einen Zykel der Form \(v_i-WVWVWVWVW-v_i\) hast, der alle Knoten außer \(v_i\) genau einmal und \(v_i\) zweimal enthält, dafür notwendig ist \(m=n\) und \(m,n\geq 2\) (da du mit \(m=n=1\) garkeine Zykel hast).
Dass das ausreicht ist auch recht einfach, da der Graph bipartit-vollständig ist, du kannst einen Hamiltonkreis einfach angeben: \(v_1w_1v_2w_2\cdots v_mw_nv_1\). Beachte wieder, dass du hier gleichzeitig mit beiden Komponenten "fertig wirst", da \(m=n\).
