Add a minimum of edges to make the graph Hamiltonian We have graph $G=K_{9,15}$. I need to add some edges to it for make Hamilton Graph. So, we know:
$$V(G) = 24,\
E(G) = 135.
$$
Every vertex has to be equial or more than 12. (24 / 2).
So the question is, how can I find the minimum number of edges I need to add to my original graph without draw?
I can't find it in google, maybe I did it wrong?

Suppose we add a few edges such that the graph $G$ becomes Hamiltonian. Let us color the edges of the Hamiltonian cycle as follows. If an edge connects vertices of different parts of $G$, then color it black, the rest are white. It is clear that the added edges are white. But there are at most $18$ black edges in our cycle  (at most two edges can be used from each vertex of a smaller part). So the white edges are at least $24-18=6$.
Well, it remains to be seen that 6 edges is sufficient.
