5

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?

Phrogz
  • 1,800
  • You should be able to get all $12$ edges of an octahedron. What's a tesseract, a $4$-dimensional hypercube? Why did you leave out the dodecahedron? – bof May 14 '14 at 22:17
  • @bof I left out the dodecahedron due to lazy thinking. And yes, I was referring to a 4-dimensional hypercube. You are right that the octahedron is fully traversible; just didn't find the right path before. – Phrogz May 14 '14 at 22:18

3 Answers3

10

In general you are trying to create an Eulerlian path (see http://en.wikipedia.org/wiki/Eulerian_path) 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.

user2566092
  • 26,142
  • 11
    I believe the classical theorem states that a connected graph has an Euler path if and only if there are exactly two, OR exactly zero vertices of odd degree. (In the case of no odd-degree vertices, there's an Euler circuit, which is a closed Euler path; when there are exactly two such vertices, the necessarily-non-closed path must start at one and end at the other.) – Blue May 14 '14 at 22:28
5

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.

xivaxy
  • 802
3

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.

Caleb Stanford
  • 45,895