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?

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?
