Many thanks kompik

I will explain the problem by an example but I cannot insert a figure in this board

Suppose G has vertices 1, 2, 3, 4, 5, 6, 7, 8

The edges are between :

1 & 2 , 1 & 3, 2 & 4, 3 & 7, 5 & 7, 4 & 6, 4 & 8

One solution is divide G into two subgraphs, s1 = {1,2,3} and s2={4,5,6,7,8}

# of edges between the subgraphs is 2

However, another solution is to divide G into two subgraphs, s1={1,3,5,7} and s2={2,4,6,8}

# of edges between the subgraphs is 1

We select the second solution since # of edges is 1..

Of course, we can divide G into two subgraohs different from these.. and we can divide it into three subgraphs, four subgraphs,... (i.e., at least two subgraphs) if we can divide G into k (k=2,3,.., or 8 ) subgraps and the # of edges is, for example, is 0, this will be the best solution.

This is an example. However, dividing G into TWO subgraphs is undesirable especially if the size of G is large because the size of a subgraph will still be large relatively; and the ultimate goal of graph decomposition is to reduce the size into small sizes whenever possible..

Hopefully the problem is clear now..