# How would you formulate this graph problem?

I am having a really hard time explaining a problem to some fellow coders and specially to computer scientists, could you please help me formalizing the following problem:

Lets assume that we have a non weighted, undirected Graph with Vertices A,B,C,D,E

A --- B
|   / | \
|  /  |  C
| /   | /
D --- E


Which means its 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 will accept the first one found.

I'm sure that theres a formal way to state this problem, and I will very much appreciate your help in doing that.

(I apologize in advance, I'm self taught so I have some major knowledge gaps)

• This is not cross posted, Question on CS is aimed at algorithmic solution while the one here clearly states is about the problem formulation, meaning, CS ask what to do, and Math asks how to state the problem, anyway I got it now but was worth claryfing Commented Mar 9, 2020 at 5:58

• Oh dear god, thank you! you're a lifesaver! So, if I understand it correctly, In those examples I found minimum k-cut for k=2? Commented Mar 8, 2020 at 14:30