Our next search problem is a Hamiltonian Cycle Problem. The input of this problem is a graph directed on, directed without weights and edges and the goal is just to check whether there is a cycle that visits every vertex of this graph exactly once. For example, for this graph, the research cycle. It is shown here on this slide. It is not difficult to check that it indeed, visits every vertex exactly once. And for this reason, in general, this problem is a search problem. Given some sequence of vertices, it is easy to check that each vertex appears in this sequence exactly once and that there is a match between any two consequent vertices in this sequence. The Eulerian cycle problem looks very similar to the Hamiltonian cycle problem. In this problem, we're given a graph again and our goal is to find a cycle that visits every edge exactly once. So in the Hamiltonian cycle problem, we need a cycle that visits every vortex exactly once. In that Eulerian cycle problem, we're looking for a cycle that visits every edge exactly once. It turns out that the Eulerian cycle problem can be solved very efficiently. Namely, there is a very simple check whether the input graph is Eulerian or not. That is whether it contains a Eulerian cycle or not. This is given by the following theorem. So, it deals with undirected graph. Assumes that way given an undirected graph and it contains a Eulerian cycle if and only if, it is connected and the degrees of all its vertices is even. We now give two toy examples that in particular will shut some light on how to prove the just mentioned serum. Our first example is a graph in which there is no Eulerian cycle, that is a non-Eulerian graph. There is no way Eulerian cycle in this graph in particular, because the degree of this vertex is equal to 3. Let's prove that it is a degree of a vertex in a graph is equal to 3 and this graph does not have a non-Eulerian cital for sure. First, assume as such in cycle existed and assume that it visited this vertex, which is denoted by me. For example, exactly once. So, this is a cycle that visits every edge of our graph exactly once and goes through v exactly once. But in this case, v would have our degree exactly two. There are two edges. We used one of them to go out of v and we used another of them to come back to this galaxy. But in our case, the degree of v is equal to 3. Now, assume that there is an Eulerian cycle that visits the galaxy at least two times. So, let's start our cycle from the vertex v. So, we walk through our graph. We get back to v and then we walk again, and then we get back to v again. But since in our cycle we visit each edge exactly once, in this case, we see that there are at least four edges adjacent to v. So, which means that either the our degree of v is equal to 2 or it is at least 4. And in general, it is not difficult to see that if we have an Eulerian cycle, then the degree of each vertex is must be even. Because each time when we come in to some vertex, we need to have a match in edge, which we use to go out from this vertex. I'm going to show an example of an Eulerian cycle in a graph and I'll also show how to define it quickly. This is the same graph we stood as a set of three. And in this graph, we can see that the degrees of all vertices are even. Namely, the degree of this vertex is 2, the degree of this vertex is 4. This is also 4, this is 6, this is 2, this is 4. So all of them are even and this graph is connected, which means that this graph contains an Eulerian cycle. Let's try to find it. Well, for concreteness, let's start from this vertex and let's just walk through this graph. We first traverse this edge, then we traverse this edge, then we get back to this, to this vertex. At this point, we return to the vertex for which there are no more unused edges. However, there are still some unused edges in our graph. Let's just take and let me also mark this cycle, as the first one. So we constructed some cycle, but still there are some unused edges. Let's just start traversing the unused edges from some vertex. For example, a couple from this one was in might might traverse this edge and then again get back to the initial vertex and this is cycle number two. In case there are still some unused cycles, some unused edges, so let's extend, for example, let's start from the vertex and let's traverse another cycle. So, this is a set site we're currently constructing the third cycle. So we go here, then here, then we get back here and then we get back here. So at this point, we used all the edges. However, what we have is not just one single cycle, but a bunch of cycles. But the nice property is that if we have several cycles, it is easily to glue them together into a single cycle. Schematically, it can be shown as follows. So assume that we have some cycle and we have some other cycle and then in some other point, we have other cycle, then what we can do is to traverse these cycles as follows. So we first go here, then we go this way, then we go this way. And finally, we go this way. Let me illustrate how to do this on our example graph. We first go on this edge, then we use this cycle, then we continue in our first cycle, then we triggers this cycle, the third cycle. And finally, we get back to the initial vertex. And this is how we, in general, an Eulerian cycle can be constructed. We just work in the graph and when we turn back to vertex which has no unused edges, we just start traversing another cycle from some vertex. The fact that the initial graph is connected ensures that then all the constructed cycles are connected to each other and then we can glue them easily to construct a single cycle, visiting each edge exactly once. Let's now summarize. We have two similarly looking problems. In the first one in the Eulerian cycle problem, we need to find a cycle that visits every edge of a given graph exactly once. This problem can be solved efficiently in linear time in the size of the input graph. In the second problem, in the Hamiltonian cycle problem, we are looking for a cycle that visits every vertex of our graph exactly once. For this problem, we have no polynomial time algorithm.
