# How to find a path that traverses each edge of a graph exactly twice?

I have a question regarding a graph traversal problem. This is the graph I am working with:

Graph[{1 <-> 2, 1 <-> 3, 2 <-> 3, 2 <-> 4, 3 <-> 4}]


My Problem is following:

I want to find a cycle on this graph such that after completion of the cycle I will have traversed each edge of the graph exactly twice and will have ended at my starting point.

I saw that Mathematica 9 has a built-in function: FindEulerianCycle[g] which does just want I want except that each edge is traversed exactly once. So my idea was to "double" the edges i.e. add a new edge between 2 nodes:

Graph[{
1 <-> 2, 1 <-> 2, 1 <-> 3, 1 <-> 3, 2 <-> 3, 2 <-> 3, 2 <-> 4, 2 <-> 4, 3 <-> 4, 3 <-> 4
}]


But then I get the following error message:

Graph::supp: Mixed graphs and multigraphs are not supported.

Apparently Multigraphs are still not supported in Mathematica 8 & 9: Multigraphs in Mathematica 8

Is there a way to implement a solution to the above mentioned problem in Mathematica? (I am using Mathematica 9)

Note: The graph shown above is just a simple example. I need to solve the above mentioned problem on a much bigger undirected graph which has vertices of odd degree.

-

You could convert your graph to directed graph by doubling your edge and give directions (opposite each other):

g = Graph[{1 <-> 2, 1 <-> 3, 2 <-> 3, 2 <-> 4, 3 <-> 4}];
dg = DirectedGraph[g]


path = FindEulerianCycle[dg][[1]]


{1 [DirectedEdge] 2, 2 [DirectedEdge] 1, 1 [DirectedEdge] 3, 3 [DirectedEdge] 2, 2 [DirectedEdge] 3, 3 [DirectedEdge] 4, 4 [DirectedEdge] 2, 2 [DirectedEdge] 4, 4 [DirectedEdge] 3, 3 [DirectedEdge] 1}

once you found path you can convert edges back to undirected:

UndirectedEdge @@@ path


{1 <-> 2, 2 <-> 1, 1 <-> 3, 3 <-> 2, 2 <-> 3, 3 <-> 4, 4 <-> 2, 2 <-> 4, 4 <-> 3, 3 <-> 1}

Note: this will just work on new version of Mathematica (tested on wolframcloud): https://www.wolframcloud.com/objects/4b9a4eea-4577-4799-844b-85da34f7550f

-
I don't understand how using 2 oppositely directed edges like this is guaranteed to work. As you "use up" the edges whilst building a (potentially) Eulerian path, the directedness of the "unused" edges constrains the remaining possible routes for the path by MORE than if the edges are undirected. Is there something rather subtle going on in your proposed approach? Unfortunately, I can't think of a counterexample, which is why I am asking this question. –  Stephen Luttrell Jun 27 '14 at 14:10
@StephenLuttrell if a graph is directed and has equal in and out degree at each vertex, then graph is eulerian. So by replace edge with 2 oppositely directed edges, we guarantee satisfying this condition. –  halmir Jun 27 '14 at 14:42
So that's why I couldn't think of a counterexample! It's now obvious to me how this property is true - i.e. an inductive proof where the graph is built up one vertex/edge-pair at a time. –  Stephen Luttrell Jun 27 '14 at 15:14
I tested this on Mathematica 9. It also works there. –  user3780157 Jun 28 '14 at 8:48

Mathematica 10 now supports multigraphs, so you can simply use FindEulerianCycle.

-
This is better than the other answer because this allows the second traversal to occur in either direction. –  anorton Jun 26 '14 at 20:10
@anorton The only problem is that at this moment Mathematica 10 is not released yet, so the only option to use this method is using the Programming Cloud. –  Szabolcs Jun 26 '14 at 20:11
Oh. Well, that is a problem... now I see why the other answer is popular, too. –  anorton Jun 26 '14 at 20:13

just perform dfs (depth first search) on the graph. store vertices as they are explored and when returning from the vertex. like, a---b---c is a graph. on dfs, vertices will be stored as (a,b,c,b,a) . hence it is the desired path.

-

I think the easiest solution is to just solve for the single traversal and then just reverse it. You should cover each edge exactly once on your "trip back" and wind up where you originally started. Then you don't need to double any edges or anything (which I imagine would greatly increase the complexity as n gets bigger and bigger.

-
1. How would you solve for the single traversal? 2. In some cases the double traversal is possible, but the single traversal is not. Example: {1 <-> 2, 1 <-> 3, 1 <-> 4}. –  Szabolcs Jun 26 '14 at 22:16
OP has a solution for single traversal in the post itself, FindEulerianCycle. As for the double being possible where the single is not, point taken: but OP specifically stated that FindEulerianCycle, quote, "does just want I want except...". –  corsiKa Jun 26 '14 at 22:18
FindEulerianCycle will only find cycles, which is not possible in many many cases (1 <-> 2). I thought that "by single traversal" you meant finding a path that taverses every edge once, but is not necessarily a cycle, and you're not realizing that even with lifting the restriction that we're looking for a cycle (FindEulerianCycle) it is not always possible to do this. –  Szabolcs Jun 26 '14 at 22:20
I'm not concerned about the limitations of FindEulerianCycle because OP already stated that it is sufficient for his needs. If it's good enough for his needs, it's good enough for me to solve his problem. –  corsiKa Jun 26 '14 at 22:26
It sounds like you misunderstood the OPs statement. He said that FindEulerianCycle would work if multigraphs were supported. Do you know what Eulerian cycle means? Did you understand why the graphs I mentioned are counterexamples that cannot be solved with your method? –  Szabolcs Jun 26 '14 at 22:29