Hamiltonian cycle in complete bipartite graph

356 Views Asked by At

Let $\Gamma=(V,E)$ be a complete bipartite graph with bipartition $V=R\cup B$.

Show that if $\Gamma$ is hamiltonian then $|R|=|B|$.

My attempt:

Suppose $\Gamma$ is hamiltonian. Put $|R|=m$ and $|B|=n$. For an absurdity, suppose $m<n$. Let $r_1,......,r_m$ be the vertices in $R$ and $b_1,......,b_n$ the vertices in $B$. Since $\Gamma$ is hamiltonian, we have a hamiltonian cycle. Suppose that cycle starts at $r_1$. We may without loss of generality assume the cycle takes the form $$r_1b_1 b_1r_2 r_2b_3 b_3r_3r_3b_4.......r_mb_m.....b_kr_1$$ where $1\leq k \leq n$. If $k>m$ then there must exist some $1\leq j \leq m$ such that $r_jb_k$ is an edge. Since a cycle has distinct vertices, this is a contradiction. Hence $k\leq m$. However, if $k\leq m$, then $k$ is any of $1,2,3,......$. This again implies that the hamiltonian cycle contains repeating vertices and thus we obtain another contradiction.

Is this correct?

2

There are 2 best solutions below

0
On BEST ANSWER

No, your proof is not quite correct. Indeed, it doesn't really use the assumption that $m < n$; but without this assumption there is no contradiction, so something must be wrong.

The problem is that from $k \leq m$ we cannot deduce that your Hamiltonian circuit contains repeated vertices; this would be true for $k < m$, but for $k = m$ you have a problem. You should rather use the observation that a Hamiltonian circuit must contain all vertices of $B$, so, in particular, we must have $\{b_1, \dots, b_k\} = B$. But this implies that $k = n$, contradicting $k \leq m$.

2
On

Suppose Γ is hamiltonian. Put |R|=m and |B|=n. For an absurdity, suppose m<n. Let r1,......,rm be the vertices in R and b1,......,bn the vertices in B. Since Γ is hamiltonian, we have a hamiltonian cycle. since Γ is a complete bipartite graph then from any vertex x in R all the vertices y in B (and vice versa) . we Suppose that cycle starts at r1 (without loss of generality) so r1,b1,r2,b2,...,rm,bm or if we add any vertex x in R because all the vertices in R has all been added to the sequence and since no two vertices in B can be joined by an edge ( Γ is bipartite ) then there isn't a hamiltonien cycle contradiction ( same thing for m > n ) then it's obvious that m=n .