I had the desire to create a cube out of a single piece of string, where each edge is represented only once. Through experimentation it appears that this is impossible, and the closest you can get is to create a cube missing 3 of the 12 edges.
A tetrahedron leaves 1 left over. An octahedron leaves none. Why is the limit 3 for a cube, and 1 and 0 for those? Is there a general rule that predicts this? What about an icosahedron, or a tesseract?
$\endgroup$ 23 Answers
$\begingroup$In general you are trying to create an Eulerlian path (see ) out of the edges of a polytope. According to the classical theorem about Euerlian paths, you can only create one if you have exactly two vertices that have odd degree. But the cube has all 8 vertices with odd degree, so you cannot hope to create an Euerlian path. As for the maximum number of edges you can include and why that number is what it is, I'd have to think some more.
$\endgroup$ 1 $\begingroup$As already mentioned, in order to have a Eulerlian path you need to have at most one pair of odd degree vertices (nodes in the corresponding graph). You have 4 such pairs (8 vertices) in a cube, so you need to delete at least 3 edges, just as you said in your question. For tetrahedron you have 4 (2 pairs of) odd degree vertices, hence you need to delete (miss) 1 edge. For octahedron you don't have odd degree vertices, so you don't need to miss anything. Dodecahedron has 20 odd degree vertices (10 pairs) -- need to miss 9 edges. Icosahedron has 12 odd degree vertices (6 pairs) -- need to miss 5 edges. In tesseract all 16 vertices have degree 4, so no odd degrees, and we don't miss anything.
$\endgroup$ $\begingroup$A cube has $8$ vertices, and each has an odd number of edges coming out and going in. Notice that except for the start vertex and end vertex, any string goes in an out of each vertex an even number of times. Thus the best you can possibly do is $2$ of the $3$ edges for $6$ of the vertices and $3$ for the other two, total $\frac{2 \cdot 6 + 3 \cdot 2}{2} = \frac{18}{2} = 9$ edges. $3$ left over.
In general, if the structure you are working with has an odd number of edges for each vertex, and there are $n$ vertices, you will have at least $\frac{(n - 2)}{2}$ edges left out. If there are an even number of edges for each vertex, you can probably cover all the edges with a single string.
$\endgroup$
