hamiltonian and eulerian tour?

Question

So, let's say I have a complete bipartite graph with vertex set V into two sets V1 and V2.

The question is: for which values of m and n does a complete bipartite graph have an Eulerian tour that starts and ends at different vertices?

I know I need to have m=n or absolute values of m-n should be 1 to have a Hamiltonian tour, but Im not quite sure about Eulerian tour question above. Also, what is the difference between Eulerian tour and Hamiltonian tour??

ps. m and n are the numbers of vertices in V1 and V2

Answer 1

So, from the comments, this has evolved into the following question:

Why does a connected graph contain an Eulerian tour beginning and ending on different vertices iff it has exactly two vertices of odd degree?

One direction first: If there is such a tour, then the degrees of the vertices are all even, apart from exactly two. The reason is that apart from the initial and terminal vertices, we pass through all other vertices, which means every time we pass a specific vertex we expend two of the edges connected to that vertex (one edge on the way in, and one edge on the way out). This is valid even for the vertices we pass through multiple times. That means that any vertex apart from the initial and terminal ones must have an even number of edges connected to it, which means exactly that it has even degree.

As for the initial and terminal vertices, we either begin or end our tour there, which accounts for use of one edge connected to that vertex. Apart from that, the same as above means for every addidional time out tour takes us past that vertex, we use exactly two edges connected to that vertex. That means the degree of those two vertices must be odd.

---

Now for the other direction: If there are exactly two vertices of odd degree, then there is an Eulerian tour. Start with all the edges of the graph painted red. We will successively construct a tour by painting more and more edges blue as we include them, and when all edges are painted blue, we will have our Eulerian tour. This proof relies heavily on one fact: NO graph can have an odd number of odd-degree vertices. Specifically, there cannot be exactly one odd-degree vertex. For non-connected graphs, this goes for each separate connected component

First, the graph is connected, so we find some tour from one of the odd degree vertices to the other. Paint all the involved edges blue. Then repeat the following until there are no more red edges. Note that after each full repetition, the subgraph of remaining red edges (which might not be connected) has only vertices of even degree.

Since the original graph was connected, the blue path must go through a vertex $v$ which is also connected to a red edge. We shall now use that to add a loop to our tour. What I mean is that where the old tour went through the vertex, after this it will enter the vertex along the old tour, go through the loop, and then exit on the old tour.

Say the red edge connects $v$ to another vertex $u$. Start by painting that edge blue. Now the subgraph of red vertices has exactly two vertices ($u$ and $v$) of odd degree, which means that they must be connected by a red path (other than the one edge we just painted blue). This means that there is a loop on $v$ that uses no edges from the old tour. Paint the rest of that loop blue, and include it in the tour.

After a finite number of repetitions, the above will have painted all the edges blue, and thus included them in our tour. The finished tour is therefore an Eulerian tour.