How many cuts does it take to remove any $n$ vertices from an $m$-dimensional hypercube?

Question

For instance, in $m=3$ dimensions (cube), the following $n=3$ corners (red) can be cut off with a minimum of $C=2$ planes (blue). (Note you are only allowed to cut off the vertices in red.)

So what about the general case of $n$ vertices on an $m$-dimensional hypercube? What is the minimum number of cuts $C(m,n)$ required to cut off any $n$ given vertices?

Answer 1

Peter Košinár’s conjecture from his comment is true for $n\le 2^{m-1}$. To see this note that each hyperplane cutting off more than one cube vertex is cutting off two adjacent vertices. But the case $n>2^{m-1}$ is more complicated. Nevertheless, the upper bound $C(m,n)\le 2^{m}-n$ can be easily proved by induction by $m$.