Bounty: 50
I have a weighted undirected graph G0, from which I want to derive weigthed undirected graphs G1 and G2.
 All nodes in G0 have a degree of at least one.
 G1 and G2 can contain the same node but not the same edge.
 All nodes in both G1 and G2 should have a degree of at least one.
 All edges from G0 should be contained in either G1 or G2
 Both G1 and G2 are subgraphs of G0 and cannot contain additional nodes.
Let’s assume that the sum of all the edges in G0 = x.
I need to find the pair of G1 and G2 for which the sum of all edges in G1 is closest to x/2
How would you go about solving that?
Edit: After much hassle due to my lack of explanatory powers, here is a better explanation of the problem (this is for an unweighted graph, but it will at least point me in the general direction of a suitable algorithm, also it avoids technical terms because is obvious that I struggle understanding them at the moment)
Lets assume that we have an undirected Graph with Vertices A,B,C,D,E
A  B
 / 
 /  C
 /  /
D  E
Which means an adjacency matrix like this one:
A B C D E
A  1 0 1 0
B 1  1 1 1
C 0 1  0 1
D 1 1 0  1
E 0 1 1 1 
Assuming all edges are undirected, we have the following edges:
(a,b) (a,d) (b,d) (b,e) (b,c) (e,d) (e,c)
What I want is that through AI, I can take that graph and generate two groups of edges of roughly the same size. (In this particular case, since we have 7 edges, we would get a group of 3 edges and another one of 4 edges.
Group 1: (a,b) (a,d) (b,d) (e,d)
A  B
 /
 /
 /
D  E
Group 2: (b,e) (b,c) (e,c)
B

 C
 /
E
Notice that all edges in each group are connected by at least one node, that is a requirement.
Another valid solution could be, for example:
Group 1: (d,a) (a,b) (b,c) (c,e)
A  B

 C
 /
D E
Group 2: (d,b) (b,e) (e,d)
B
/ 
/ 
/ 
D  E
And so on, as you see there are many valid solutions but I want to know if there’s an algorithm to find one.