How to combine bin packing with graph theory?

edit

I have a number of undirected graphs, where each vertex has a unique ID, each edge a non-unique weight, and every edge connects two different vertices, so no vertex is connected to itself.

These graphs can either be valid or invalid. A graph is invalid, if there's any loop of an odd numbered length. For example, if A connects to B, B connects to C, and C connects back to A, it's a loop of length 3, and thus invalid. This also means that any loop of an even numbered length is valid.

And this is where bin packing comes into the picture. At first, no matter how many graphs I have, they're all in one bin, but I need to split them up such that each bin only contains valid graphs, and that I end up with a minimum number of bins.

The way to make an invalid graph into a valid one, is to simply move one edge into another bin, while copying the two vertices. For example, I could choose to move the edge between A and C into another bin, thus making the first bin having a graph that connects A to B and B to C, and the second bin would contain a graph that connects A to C.

If there's already bins containing graphs where one of the two vertices exists, the edge must be added to one of those graphs, but only if it does not make an invalid loop in the process, this is the bin packing part of the problem.

The weights of the edges also matter. If for example the edge between A and B, and A and C, have a weight of 2, but the edge between B and C have a weight of 1, it is this one that must be removed. If there's more than one edge that can be moved, and both result in the same number of bins, then the edge with the lowest weight is the one that must be removed.

It is easy enough for me to describe the problem at hand, but where I hit my head against the wall, is simply in how to go about solving this problem. I know it's a bin packing problem, involving graph theory, but I haven't the faintest idea about how to solve this in Sagemath. And this is where I hope some can be helpful by providing some code and some knowledge, so that I can get started on this and figure out how a problem like this is supposed to be solved.