and also we double everything inside this subtrees.

So how to construct in the Eulerian cycle in this double tree?

Well, we can do this just recursively, we started the root,

we then go into this subtree.

And then we find an Eulerian cycle recursively in this subtree and

then we get back using this edge.

Then we go to the second subtree find an Eulerian cycle as it traverses all edges

inside this subtree and then we will come back using this tree.

Great, and then we proceed to the zero subtree find in Eu;erian cycle and

get back.

For example, for these three shown here in

an Eulerian cycle will look like as follows.

So let's start from this vertex, then we first traverse this edge.

Then we traverse this edge.

Then this edge.

Then this one.

Then this one and finally this one.

So we've traversed all six edges.

This is our cycle C.

Now we need to return a cycle that visits every vertex in this graph.

For this we are going to do the following.

Let's start in the same vertex.

We first use the same edge, then we use the second edge in our cycle C.

But then the third edge in our cycle C visits the same

vertex that was already visited.

Instead of doing this, we go directly to vertex four.

From this vertex,

the fifth's edge of our cycle goes to the vertex which we already visited.

So instead of doing this, we go to the initial vertex.

So the metric property of our graph implies that instead of edges three and

four, we use this just the direct edge from three to four.

Then we can only decrease the total length of the resulting cycle.

Okay, we now proceed to a more complete example.

In this example, our vertices are just points on a plane.

And we assume that the distance between two vertices

is just the distance between the corresponding points on a plane.

In this case of course, the edge weights or

the edge distances satisfy the triangle inequality.

So in this case, we're given then points which

define implicitly a complete graph on end vertices.

So the first thing to do is to construct a minimum spanning tree in this case.

It looks as follows.

Now with double every edge.

Now it looks as follows and now we find an Eulerian cycle in the results in graph.

For example, we start from this vertex and then we start traversing it like this.

This is first one, the second one, the third one, the fourth one,

the fifth one and so on.

So 6, 7, 8, 9, 10, 11, 12, 13, 14,

15, 16 and we will count back to the initial vertex.

Now, this cycle I'm sorry, visits this vertex for

example several times and also this vertex several times.

So what am I going to do.

It's where I'm going to bypass some parts of this cycle.

Namely, this is the final cycle that was constructed

by our algorithm, let me show you how it was constructed.

So from here we go to here because this vertex was not visited before.

From here we go to here, from here we to go here.

And from here we go to this vertex.

But now, instead of using the fifth's edge, we go directly to this vertex.

Because the fifth's edge visits the vertex that was already visited by our cycle.

Then we go here because this vertex have not been visited before.

Then we go here.

Then we go here.

And then again, instead of using the edge 10, 11, 12,

13 and so on, we go directly to the initial vertex.

And now we visited all the edges.