# 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. – Konstantinos Koiliaris Jun 30 '15 at 15:36
• You are right on that. I have clarified the question – fokatsar 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.