I was reading about how to prove BISECTION WIDTH, the decision problem of deciding whether for a given graph $G$ and an integer $k$, there exists a bisection such that the cut of the graph has at most $k$ crossing edges, when I realized all of the proofs of this problem relied on one remark:
Let $G = (V, E)$ where $|V| = 2n$, then $G$ has a bisection of size $k$ if and only if the complement of G has a bisection of size $n^2 − k$.
Every source said that this was easily verifiable, but I'm at a loss as to how to prove this. Could somebody please explain how to show this?
When you consider the complement of $G$, you add all the possible links from the two parts, i.e. $n^2$ links, but you have to remove the $k$ links that was already between your two parts, giving $n^2-k$.