For which values of m and n does Km n have an Euler circuit

For which values of m and n does K_m, n have an Euler circuit? Provide adequate justification for your answer.

Solution

Solution:

We see that a graph has an Euler cycle if and only if each vertex has even degree.

Split the vertices of Km,n into two groups: put the vertices from the group of m vertices on the left and put the vertices from the group of n vertices on the right.

Each vertex on the left is connected to each vertex on the right; therefore, the degree of each vertex on the left is n.

Similarly, the degree of each vertex on the right is m.

Using the fact that a graph has an Euler cycle if and only if each vertex has even degree, this means that Km,n has an Euler cycle if and only if m and n are both even

And

It is well-known that a connected graph has an Euler circuit if and only if all of its vertices have even degree;

it has an Euler path but no Euler circuit if and only if it has exactly two vertices of odd degree.

Each vertex in Km,n has degree m or n, so Km,n has an Euler circuit if and only if m and n are both even.

Km,n has exactly two vertices of odd degree if one of the following is true: