Add a minimum of edges to make the graph Hamiltonian

Question

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?

Answer 1

Another way to think about it: create a bracelet with 9 red beads and 15 blue beads, minimizing the number of pairs of adjacent beads that are the same color.

If two red beads are adjacent, can you improve the count of adjacent pairs of the same color?

Answer 2

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.