5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$ $\endgroup$ – Thomas Andrews Oct 26 '12 at 13:16
  • 1
    $\begingroup$ Hint: For a Eulerian circuit, every vertex has even degree. $\endgroup$ – Shahab Oct 26 '12 at 13:17
  • $\begingroup$ 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. $\endgroup$ – World Oct 26 '12 at 13:21
14
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It can also be said that $(m,n)-bipartite$ has exactly two odd vertices if $|E|$ is odd and is equal to $m$ or $n$. $\endgroup$ – wulfgarpro Sep 30 '19 at 21:18
4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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