Given a walk in a graph, find a path and an odd cycle contained in the trail.

Question

Given this graph:

And given the $1-8$ walk $$C_1=(1,3,2,3,4,5,3,6,7,6,8),$$ find a $1-8$ path. Note: trails do not repeat edges, paths do not repeat vertices.

Lastly, given this closed odd-length walk $$C_2=(1,3,6,5,3,4,5,6,8,7,6,3,2,1),$$ find an odd cycle (a cycle is a closed path).

I am completely lost, and I seem to find it very difficult to obtain proper references on the required algorithms, mostly due to notation differences in textbooks and internet resources, arising from the different usages authors attribute to "path", "trail", "circuit", and "walk".

Thanks in advance.

Answer 1

Given a walk, just remove all cycles in it and you are left with a path. By cycles, I mean you can always replace $$a,a_1,a_2,\dots, a_n, a, b$$ with $a,b$.

Answer 2

My answer is not so different to the one above by 5xum. But I'm going to post it anyway because you are the victim of a slight misunderstanding, I believe. A cycle or a path contained in a trail does not necessarily mean the cycle or path is explicitly part of your trail It just means you traverse the said path or trail and maybe other places in your walk.

So in $C_1$, Going from $1 - 4$ through $1, 3, 2, 3, 4$ is the same as taking the path $1, 3, 4$ excluding the traversal to $2$ and back. So removing such unnecessary traversals your required path is (1,3,4,5,6, 8). (I'm assuming you are asked to find a path from $1$ to $8$)

Even in $C_2$ there is a trivial triangle and you should be able to see it.

As for the terminology issue.. It is something you are never going to overcome. So many authors use a variety of terms and notations to introduce their subject. The definitions for walks and cycles and paths are the worst. My suggestion is to have a few close books and read them from the beginning to have a proper grasp on each authors terminology. I'm going to stop short of recommending some because I think your course is principally algorithm-based whereas I studied from a more theoretic perspective. Hope this helped.