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

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?

-
Even on a square, the answer depends on which vertices you select--whether they are adjacent or not. Take two corners of a square sharing a common edge vs. two corners of a square with no edge between them. – Andrew Salmon Jun 6 '13 at 8:56
@andewsalmon - I'm interested in the minimum number to cut off any $n$ given vertices, meaning I allow for the case of not being adjacent. Sure, for adjacent cases you may use less cuts, but I need to be able to cut off any $n$ given vertices in $C(m,n)$ cuts. – mchen Jun 6 '13 at 9:00
The example of the square is a counterexample to the conjecture you proposed. Notice that $2$ cuts are needed, which is greater than $m-1 = 1$. – Andrew Salmon Jun 6 '13 at 9:03
Ahh yup - overlooked the obvious - thanks – mchen Jun 6 '13 at 9:03
A generalization of the opposite-corners-in-square: Colour the vertices of the $m$-dimensional hypercube with two colours so that two adjacent vertices are always coloured differently. If you take any $n$-member set of vertices of the same colours, my intuition suggests you'll need all $n$ cuts (i.e. every vertex will need its own cut) opposite-corners case. Of course, if you take more than half of the vertices, you will be able to reduce the number of cuts. Maybe the number of cuts required would be $\min{n,2^n-m}$? – Peter Košinár Jun 6 '13 at 9:18