# How many edges are cut in a balanced partition of a graph?

Consider a graph on n nodes and e edges that is partitioned into k "balanced" subgraphs in the sense that each block has an equal number of nodes and the number of cut edges is minimized. Is there a formula for the number of cut edges in this situation?

• Your question is not well defined. Graph partitioning algorithms are based on what you are trying to optimize. For example that could be the cut edges themselves. Jun 30 '15 at 15:36
• You are right on that. I have clarified the question Jun 30 '15 at 21:38

Even in the current updated version of the question, it still remains ill defined. There many different ways by which you can partition a graph into symmetric (or balanced if you like) clusters. One question that you might have in mind but have problem expressing is the minimum multisection (or partition): Given a graph $G$ find a symmetric partition $P$ of its vertices such that it minimizes the edges between different clusters.