Hamilton,Euler circuit,path For which values of m and n does the complete bipartite graph $K_{m,n}$ have 1)Euler circuit 2)Euler path 3)Hamilton circuit
I found answers and you
Prove(or show)that:
1)($K_{m,n}$ has a Hamilton circuit if and only if $m=n>2$ ) or ($K_{m,n}$ has a Hamilton path if and only if m=n+1 or n=m+1)
2)$K_{m,n}$ has an Euler circuit if and only if m and n are both even.)
 A: 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$.
A: 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:
squirrel

*

*$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}$ msquirrelust 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 Hamilton 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$.
A: Suppose if possible assume that m < n.
So,  any cycle in the bipartite graph can have atmost 2m vertices (follows from: Any bipartite graph always has an even cycle only). 
Hamiltonian cycle must cover all the vertices, so the cycle covers m + n edges. 
Also, as stated (m < n), so, n + m > 2m. But, from the earlier result, our bipartite graph can have atmost 2m edges.  Which is a contradiction. 
So, m = n. 
A: A Euler circuit can exist on a bipartite graph even if m is even and n is odd and m > n. You can draw 2x edges (x>=1) from every vertex on the 'm' side to the 'n' side. Since the condition for having a Euler circuit is satisfied, the bipartite graph will have a Euler circuit.
A Hamiltonian circuit will exist on a graph only if m = n. That's because if they're unequal, you'll have to revisit at least one vertex on the other side during traversal. But this act violates the Hamiltonian condition that you must visit each vertex only once. So, m = n in a bipartite graph if it has a Hamiltonian circuit.
