This really depends on what properties you want want the pieces to have. For example: if you want few pieces of roughly the same size, with few edges crossing between the pieces, then you probably want to do something like k-way graph partitioning. This can easily be done with software packages such as METIS and KaHIP.

If this is overkill, then consider iteratively performing breadth-first searches. Once a search has encountered enough vertices, then call the subgraph induced by those vertices piece 1. Repeat on the remaining graph.

Hello

See this link may help you 

Good Luck

http://stackoverflow.com/questions/17673393/split-graph-into-two-parts-according-to-min-cut-between-s-and-t-vertices

This link may contain some useful information.

https://www.robots.ox.ac.uk/~vgg/rg/papers/parallelgraphcuts.pdf

The operation split needs elaboration. Simple way is to look for minimum degree vertex and cut it. Repeat the same for the remaining graph.

The operation split needs elaboration. Simple way is to look for minimum degree vertex and cut it. Repeat the same for the remaining graph.

One could split a graph into pieces in many ways. The parts of a minimum vertex coloring, a minimum clique covering, supposing it is k-connected -- one could form maximal (k+1)-connected subgraphs. Similarly, one could find vertex or edge cuts (vertices or edges that when removed would increase number of components). Even, if one wanted, you could partition vertices into "large" and "small" degrees, according to one's interpretation of large and small (arbitrarily many such interpretations). So, it is up to you, depending on what you are trying to do, but here are many ideas.

This really depends on what properties you want want the pieces to have. For example: if you want few pieces of roughly the same size, with few edges crossing between the pieces, then you probably want to do something like k-way graph partitioning. This can easily be done with software packages such as METIS and KaHIP.

If this is overkill, then consider iteratively performing breadth-first searches. Once a search has encountered enough vertices, then call the subgraph induced by those vertices piece 1. Repeat on the remaining graph.