This is second in a series of node your homework! writeups
The proof is by reduction from max-cut (see Garey and Johnson). The
series of reductions goes this way:
max-cut --> max bisection --> (minimum) Graph Bisection.
First given the input graph to max-cut of n vertices and e
edges, we transform it by placing n additional independent
vertices. We note that given the original
input, we can always distribute the n additional vertices among the two subsets
such that the number of vertices in the subsets are equal.
So now, solving the max-bisection problem on the transformed
input is equivalent to solving the max-cut problem.
From max bisection, we can transform the input by getting the complement of the
input to max bisection (the complement is obtained by adding edges where there was
none, and removing edges if they originally existed in the source graph). Now,
since the min bisection of the transformed graph is actually the max bisection of
the original graph.
Thus, any algorithm solving the min-bisection solves the max bisection problem,
which in turn solves the max-cut problem, which is NP-complete.
This is based heavily on the proof from