Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have some box with dimensions x,y,z. I put a net around it which includes the top and bottom. The net has unit squares on it. Whats the maximum amount of cuts you can make on the net but still have it in one piece?

share|improve this question
    
An initial guess: 2xy+2xz+2yx-1, which is exactly 1 less than half of the edges. This would leave 2xy+2xz+2yz+1 edges remaining, which is the minimum number necessary to connect the 2xy+2xz+2yz+2 vertices of the graph. I believe one could just begin cutting arbitrarily, following the rules that a cut cannot result in a disconnected graph, and a cut must be made if a cycle still exists. No matter how this is done, one should make the same number of cuts. This is only my intuition. –  Jared Mar 6 '13 at 1:49

1 Answer 1

You would want to make enough cuts to reduce the net to a spanning tree. The number of edges in a tree is one less than the number of vertices. So, here's what you do: find the number of vertices, $v$; find the number of edges, $e$, in the uncut net; then you can make $e-v+1$ cuts, leaving $v-1$ edges uncut. Can you work out $v$ and $e$ from $x,y,z$?

share|improve this answer
    
It makes sense that there is $v-1$ edges, however, what is throwing me off is that when you make squares with vertices and edges, you get four vertices and four edges per square. Thus the edges and vertices are the same number. Suppose I had a cube where all the length, width, and height were two. Since the net is made of unit squares, their would be four squares on each face of the cube. This implies their are nine vertices on each face, but also 12 edges. So, the edges are greater then the vertices. –  user64013 Mar 6 '13 at 2:44
    
Some of those vertices are on two, or even three, faces, and some of the edges are on two faces. You have to be careful with your counting. For the case you mention, you would have $26$ vertices and $48$ edges before you start cutting. You could cut $23$ of those edges. –  Gerry Myerson Mar 6 '13 at 3:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.