Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.)

share|improve this question
1  
I don't really follow what the "or" is doing in (1). Both statements are true. Also, if a graph has a Hamilton circuit, it has a Hamilton path, so really the conclusion ought to be that $K_{m,n}$ has a Hamilton path if and only if $|m-n|\leq 1$ –  Thomas Andrews Oct 26 '12 at 13:16
1  
Hint: For a Eulerian circuit, every vertex has even degree. –  Shahab Oct 26 '12 at 13:17
    
i know Km,n has a Hamilton path if and only if |m−n|≤1 is obvious but i don not know proof of it. –  World Oct 26 '12 at 13:21

2 Answers 2

up vote 3 down vote accepted

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$.

share|improve this answer

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.