# graph theory, geometry

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?

-
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

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$?
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