I am trying to find some generic upper bounds on the "standard" graph partitioning problem. Say I have a graph with $|V|$ vertices and $|E|$ edges I want to partition it into two equal $N/2$ (or approximately equal if easier) parts while minimizing the cut i.e. $\min(|C|)$ where $C$ is the set of edges with nodes on either side of the partition (similarly nodes that the cut goes through).
So far this is standard stuff and clearly the optimal solution depends on the details of the graph. However, what I want is an upper bound on $\min(|C|)$ in terms of $|V|$ and $|E|$ without knowing anything else about the graph. If no upper bound then even some type of average case estimate would help.
Also, the same thing for a multigraph.