stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

Eulerian circuits (paths on a graph which traverse every edge once and start and end at the same vertex) are impossible on every platonic solid except for the octahedron (since every vertex has to have even degree for an EC to exist, and the other platonic solids have degree 3 or 5 vertices).

However, if you double the edges in a platonic solid, then you can create an EC that traverses every edge twice. In fact, with a little ingenuity, its possible to find ECs that traverse every edge once in each direction. For example, in the tetrahedron, let the vertices be A, B, C, and D. Then A->B->C->A->D->C->B->D->A->C->D->B->A traverses every edge twice, once in each direction and ends where it started.

However, this EC has an annoying feature: a u-turn (B->A->B). Its not quite as obvious in this case since its split up at the beginning and the end of the cycle, but its there, and I want it gone. I'm pretty sure that its impossible to find a "non-u-turn double EC" for the tetrahedron (although I don't have a hard proof, I think I've tried all the interesting possibilities), but I haven't tried to find one on the cube, octahedron, dodecahedron, or the icosahedron. So, my challenge is this: I'll pay 3 mod points for the first correct cycle on each platonic solid, or 5 points for a proof of impossibility for that solid. In the eventuality of impossibility, I'll pay an additional 3 points for a solution in which you traverse every edge four times, twice in each direction, with no u-turns. In the event that this problem has been solved previously, I'll pay 2 points for a link to the solution.

____________________________
Progress Quest Progress

calamarain
Level: Smitemaster

Rank Points: 933
Registered: 03-25-2007
IP: Logged

File: tetra.jpg (7.9 KB)
Downloaded 66 times.
License: Public Domain

It helps if you visualise it like this... pardon the quick diagram...

That's the one for a tetrahedron.

Then you can travel...

A D B C D A C D B A C B A (using my notation)

Thus doing the whole tetrahedron twice, without having to U-turn around and go back along the same line after you've just done it.

____________________________
My Holds

---

[Last edited by calamarain at 11-04-2007 03:44 PM]

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

You did C->D twice instead of C->D and D->C once each.

Edit:
Also, B->A twice

____________________________
Progress Quest Progress

---

[Last edited by stigant at 11-04-2007 07:41 PM]

Maurog
Level: Smitemaster

Rank Points: 1501
Registered: 09-16-2004
IP: Logged

It is impossible for a tetrahedron.
I have drawn a solution, but not gonna redraw it in paint, so here is the non-graphic explanation:

There are 4 points, A B C and D, each connected to each other and we want to make sure you only go on each line once in each direction. Therefore, each point can be drawn as a box with three pairs of input and output, corresponding to each other point.

Draw the boxes, connect the inputs and outputs (make sure they are in pairs, as in, if the first input of C if from A, the first output is to A - it's important). The trick now is drawing lines inside the boxes to connect inputs to outputs. Now, we don't want to have any loops, therefore any paired input and output can't be connected, because it would make a loop like ACA.

Therefore, if we look at D the only possible way to connect its insides is either A's output to B's input, B's output to C's input and C's output to A's input. Or the other way around - A's output to C's input, C's to B's and B's to A's.

Symmetry: since the graph as of now is completely symmetrical, and the letters have no real significance, it currently doesn't matter whether you do it this or other way. Do this, connect the lines inside D in one of the ways.

Now, make D redundant, leaving only 3 boxes and connecting the lines that used to go through D to the corresponding next box. Mark these lines with "d". As you can see, the inputs and outputs are still paired - the ones that used to lead to D now lead to others, but that line is marked with "d". Furthermore, we still have symmetry - every box has the same set of inputs/output pairs, one to every other box, and one marked with "d" from one to another.

Now make C redundant in the same way, and then B. You will be left only with A. Look at A's inputs and outputs and marks, and you will see these exact three strings:

1. A-D-C-B-A
2. A-B-D-A
3. A-C-D-B-C-A

It could be that your C is my B for example, but that's not important, you will still always get these.

And therein lies the problem. You cannot connect them to make a full loop. You can't connect one to itself because it would make a separate loop from the two others. You can't connect 1 to 2 because they are in the same pair (it would make a BAB loopback). You can't connect 2 to 1 for the same reason. Therefore you must connect both of them to 3, which is impossible.

QED.

____________________________
Slay the living! Raise the dead!
Paint the sky in crimson red!

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

Maurog's proof is accepted: 5pts

I have written a program which searches for possible paths.
There are none on the tetrahedron (of course). I have found several quadruple EC's on the tetrahedron. I will leave that problem open for 2 more days before posting a solution.

There are none on the cube. An elegant proof of this (ie one that doesn't rely on checking too many combinations) can still earn the reward here. I have also found several quadruple EC's on the cube. I will that problem open for 2 more days before posting a solution.

There are many on the octahedron. I pretty much suspected this since you can start with any simple EC, and with some minor tweaks find a second EC which can be appended to the first to create a double EC with no uturns. (this is a bit vague, but I think the reasoning is valid).

As I write this, I'm waiting for results on the dodecahedron. It doesn't look promising. As with the cube, I'll still reward an elegant proof. I'm also using my program to search for quad EC's, but I haven't found one yet. I suspect that there are some, but with a search depth of 120 and a branching factor of 2, its going to take some time to find one.

I haven't looked at the icosahedron yet (for reasons of computational complexity), but it will be my next victim. I think that there's still a small chance that a double EC exists on this graph since the branching factor will be 4 instead of 2 which gives a considerable amount more freedom. But I won't be surprised to not find any double EC's either.

(EDIT: Yep, I've found some double EC's for the icosaheron. I'll leave this one open for 2 more days)

Two additional problems to think about:
Does any graph with a single EC (ie a graph with all even vertices) necessarily have a double EC with no u-turns?

What are the necessary/sufficient conditions for a graph to have a double EC with no u-turns?

____________________________
Progress Quest Progress

---

[Last edited by stigant at 11-05-2007 07:13 PM]

Maurog
Level: Smitemaster

Rank Points: 1501
Registered: 09-16-2004
IP: Logged

Uh, these last two are easy... any strictly circular graph can't be made without u-turns. I think the necessary condition is being able to split into two or more EC's at some point, and then it's easy to arrange them so that they go once this way and once the other way.

____________________________
Slay the living! Raise the dead!
Paint the sky in crimson red!

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

Yeah, you're right about the strictly circular graph.

But I don't think you're correct about the splitting into 2 EC's being a necessary condition. For example, a triangular prism (two triangles ABC and DEF with AD, BE and CF connected) has no single EC (since it has 6 odd-degree vertices), but does have double ECs: ABCADEBACFEDFCBEFDA is one.

I would posit that having a single EC and at least one vertex of degree 4 or more should be sufficient, but as noted above, not necessary.

____________________________
Progress Quest Progress

---

[Last edited by stigant at 11-05-2007 09:27 PM]