Hamiltonian and Euler Circuits and Paths – Graph Theory

graph theory

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

Best Answer

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

Related Question