Hamilton,Euler circuit,path

It is well-known that a connected graph $G$ 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 $K_{m,n}$ has degree $m$ or $n$, so $K_{m,n}$ has an Euler circuit if and only if $m$ and $n$ are both even. $K_{m,n}$ has exactly two vertices of odd degree if one of the following is true:

• $m=n=1$;
• $m$ is odd and $n=2$; or
• $n$ is odd and $m=2$.

Let the set of vertices of $K_{m,n}$ be $V=V_0\cup V_1$, where $|V_0|=m$, $|V_1|=n$, and all edges are between $V_0$ and $V_1$. A path in $K_{m,n}$ must alternate between vertices in $V_0$ and vertices in $V_1$. A circuit necessarily has $2k$ vertices for some positive integer $k$; $k$ of these vertices are in $V_0$, and the other $k$ are in $V_1$. Thus, if $m\ne n$ it is impossible for a circuit in $K_{m,n}$ to hit every vertex, and therefore $K_{m,n}$ can have a Hamilton circuit only if $m=n$. Conversely, it’s easy to show by induction that $K_{m,m}$ has a Hamilton circuit for for all $m\ge 2$.

A Hamilon path in $K_{m,n}$ that cannot be extended to a Hamilton circuit must have both ends in $V_0$ or both ends in $V_1$. Suppose that both ends are in $V_0$. Then the path has $2k$ edges and $2k+1$ vertices for some $k$; moreover, $k+1$ of the vertices are in $V_0$, and $k$ are in $V_1$. But this is a Hamilton path, so it reaches every vertex exactly once, and therefore $m=k+1$ and $n=k$, i.e., $m=n+1$. If both ends of the path are in $V_1$, then $n=m+1$. And as in the case of Hamilton circuits, it’s not hard to show by induction that $K_{m,m+1}$ has a Hamilton path for every $m\ge 1$.

It is easy to show that $K_{m,n}$ has a Hamiltonian cycle for $m=n$. Partition the graph into it's natural bipartition, labelled $X=\left\{x_1,\ \cdots,\ x_m\right\}$ and $Y=\left\{y_1,\ \cdots,\ y_n\right\}$. Then the cycle $$\left(x_1,\ y_1,\ x_2,\ y_2,\ \cdots,\ x_m,\ y_m,\ x_1\right)$$ is the desired Hamiltonian cycle. Conversely, suppose that $m \neq n$. The Hamiltonian path must traverse the vertices of each bipartition alternately, therefore $m + n$ must be even and $|m - n| \le 1$. The only possibility is for $m=n$.

If only a Hamiltonian path is desired, then we can relax the conditions a bit. Again, it's not difficult to explicitly give a construction for the Hamiltonian path. Conversely suppose that a Hamiltonian path exists and that without loss of generality that is starts on the partition labelled $x$ with $m$ members. Then it can either end on $x$ in which case we have $m = n+1$ or end on $y$ in which case $m = n$.

Finally, it is necessary and sufficient that a graph have all vertices be of even degree to admit an Euler circuit. Therefore we require $m$ and $n$ to both be even. For a graph to admit an Euler walk, we require $2$ vertices of odd degree. Therefore we can also admit $K_{2,n}$ for odd $n$.