# Split a graph to segments

To solve a programming problem, I need to solve a graph problem, but I am weak at graph theory.

Given an undirected graph $G$ with edges $E$, I need to find $n=2$ subgraphs $G_1$ and $G_2$, so that $G_1 \cap G_2 = \emptyset$ and $G_1 \cup G_2 = G$, and the number of edges, where edge $u - v$ where $u \in G_1$ and $v \in G_2$ are minimal. For extra points I'm interested in alternative partiotions, other cases, where $n>2$, or solution for weighted graphs, but they are not important.

For the curious, the programming problem is to divide a big class into smaller classes.

-
Select a point with minimal degree. This will be $G_1$, the rest is $G_2$. Maybe you state something about the number of vertices inside $G_k$! – draks ... Feb 9 '12 at 11:46
@draks: That need not be minimal, e.g. two triangles joined by an edge. – Chris Eagle Feb 9 '12 at 12:32
Sorry, timed out, and cannot format well, so as a new comment: Suppose I have $G = \{a,b,c,d,e,f\}$ and $E=\{\{a,b\},\{b,c\},\{c,a\},\{d,e\},\{e,f\},\{f,d\}\}$. Your solution will cut 2 edges, but I can have $G_1=\{a,b,c\}$ and $G_2 = \{d,e,f\}$ with 0 cuts. Even if I make this graph connected with an edge $\{c,d\}$, your solution will still miss the optimal solution. – pihentagy Feb 9 '12 at 12:40
Ok, aelguindy answered the question, but I still has some concerns. Given the following graph (that would be the case with many graphs), it is easy to cut one node from the graph with minimal cut. So cut e--h in { a--b b--c c--a d--e e--f f--d a--d a--d e--h } However, it is a bad refactor to split a 100 node graph to 99:1 – pihentagy May 4 '12 at 13:32

What you are looking for is called a graph cut, usually one means a partition of the graph into 2 parts. Computing the minimum cut for a graph can be solved using $n - 1$ max-flow computations, or even faster (see this).
Splitting the graph into $k$ parts with the minimum number of removed edges is NP-complete (see this). If however $k$ is constant, you can compute it in $O(|V|^{k^2})$ (see the same link).