Claim : Suppose we have a complete binary tree of height $h$. We introduce a cut to partition this tree into two sets of vertices of size $x$ and $2^h - 1 - x$ for some $x$. For any $x$, we define the optimal cut size of to be the minimum number of edges crossing from one side of the cut to the other side. For all values of $x$, we see what's the optimal cut size, and take the maximum of these values. Let's call that to be $m$. Then, there is no $x$ for any $h$ such that the optimal cut size for both $x$ and $x+1$ vertices is $m$.
Note : I don't know if this claim is true.
Can anyone prove this?
Consider the complete tree with 3 vertices. Clearly when $x = 1$, the optimal cut is 1. However, when $x=2$, the optimal cut will just be the same, but with the partitions reversed, so the claim is false.