Mathematics desk
< March 6	<< Feb \| March \| Apr >>	March 8 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 7

going through all edges of the Regular polyhedra?

Is there an easy way to figure out what the minimum number of edges that a path would have go through to trace out all of the edges of each of the Regular Polyhedra? The Octahedron has a Hamiltonian Cycle, so that one is 12, but for the others they all have an odd number of edges at each vertex.Naraht (talk) 15:58, 7 March 2017 (UTC)[reply]

Well, there's a path of length 7 for a tetrahedron, which is one short of being Hamiltonian, so that one must be minimal, but I don't know about the others. Deacon Vorbis (talk) 17:14, 7 March 2017 (UTC)[reply]

Oops, that's an Eulerian path that you're describing, not Hamiltonian. Deacon Vorbis (talk) 17:18, 7 March 2017 (UTC)[reply]

It seems like this is a special case of the route inspection problem. That talks about closed circuits though, and I'm not sure how dropping that restriction would affect the answer (or which case you're looking for). Deacon Vorbis (talk) 18:03, 7 March 2017 (UTC)[reply]

OK progress so far. For the Tetrahedron, the answer is 7, round the bottom, up to the apex and then down and back up one of the other sides and then the last. For the Cube it is between 12 (the number of edges) and 15, as a hamiltonian cycle on the vertices will cover 8 of the edges, with the ability to go out and back on the other four, but one edge will be at the beginning/end so it will only have to be done once. I think that the same logic as the cube can be used on the Dodecahedron which means that the number is between 30 (the number of edges) and 39. Not sure on a whether an icosahedron has two hamiltonian cycles that don't share an edge.Naraht (talk) 16:32, 8 March 2017 (UTC)[reply]

Let's say you have a path which visits each edge at least once. For each time the path follows the same edge twice, split the edge to make two edges, you now have an Eulerian path on graph with more edges. A graph with an Eulerian path can have at most two vertices with odd degree. So if you're doubling edges to make the graph Eulerian, and there are 2k vertices of odd degree, you're going to need at least k-1 additional edges. So for the tetrahedron you need 1 additional edge, cube 3 additional edges, dodecahedron 9 edges, icosahedron 5 edges. (I'm skipping the octahedron because it's already done.) So the minimum length of a path is tetrahedron 6+1=7, cube 12+3=15, dodecahedron 30+9=39, icosahedron 30+5=35. The procedure you give establishes an upper bound for the minimum eldge which is equal to the values given. --RDBury (talk) 18:56, 9 March 2017 (UTC)[reply]

I'm not sure that this quite works. The "at least k-1 additional edges" means that the values that you've set are minima. That seems very different than showing that there is a 35 edge solution for the icosahedron.Naraht (talk) 19:48, 9 March 2017 (UTC)[reply]

What is missing is to find a matching in the graph of that size. This is not hard to do case-by-case. --JBL (talk) 21:05, 9 March 2017 (UTC)[reply]

True, this is certainly something where going through one at a time is just fine as a technique, once the general concepts have been done.Naraht (talk) 20:56, 10 March 2017 (UTC)[reply]