# Struggling with Hamiltonian cycle existence.

Prove/Disprove the following.

If $K_{m,n}$ has both an Euler circuit and a Hamilton cycle, then m = n and n is even.

Should be true: If it has a Euler Circuit m and n must be even as the degree of each $v_n=m$ and degree of each $v_m = n$ hence if either n or m were odd a vertex would have odd degree this is not possible with a Euler circuit.

Without loss of generality (and by convention) $K_{m,n}$ is defined $m \geq n$.

Since $m \geq n$ let $m = n +2k$ where $k \in \mathbb{Z^{+}}$$m,n\in 2\mathbb {Z^{+}}$ we know this is the case as m and n must be even.

Now since $K_{m,n}$ has a Hamiltonian cycle each vertex must have deg at least 2 and for every vertex Let us organize each $v_{m}$ and $v_{n}$ in the following way. $v_{m_{0}}$, $v_{m_{1}}$, $v_{m_{2}}$,...,$v_{m_{m-1}}$ and $v_{n_{0}}$, $v_{n_{1}}$, $v_{n_{2}}$,...,$v_{n_{n-1}}$ this is a list of all vertices in $K_{m,n}$

Let us start at $v_{m_{0}}$ we then move to $v_{n_{0}}$ let us delete each edge as we traverse it. From $v_{n_{0}}$ we move to $v_{m_{1}}$. We proceed in the fashion from each $v_{n_{i}}$ let us move to $v_{m_{i+1}}$ and from each $v_{m_{i}}$ let us move to $v_{n_{i}}$.

Since $m\geq n$ we shall eventually arrive at $v_{n_{n-1}}$ let us move from here to $v_{m_{0}}$ this collection of deleted edges starting at $v_{m_{0}}$ is a cycle including every vertex in $V_{n}$ we shall define this $C_n$

Here we have two options either

1) $v_{m_{n}}$ exists in which case $m > n$ then our cycle doesn't include every vertex in $V_m$ However since there is no edges between these vertices $C_n$ we created is as large a cycle that can be constructed in $K_{m,n}$ so it cannot contain a Hamiltonian cycle.

2) Our cycle contains not only every vertex in $V_{n}$ but every vertex in $V_{m}$ ie $m=n$ in this case we have a cycle that has visited every vertex in $K_{m,n}$ hence our cycle is definition ally a Hamiltonian cycle

Hence $K_{m,n}$ has both an Euler circuit and a Hamilton cycle whenever m = n and n is even.

Q1) My proof regarding a Hamiltonian cycle im not certain that i have show this formally enough for a proof.

Q2) There must be a better way to do this if we know we have a Hamiltonian cycle on $K_{m,n}$ then without loss of generality we should be able to pick $v_{m} \in V_{m}$ and alternate from $V_{m}$ to $V_{n}$ until we have a Hamiltonian cycle which by statement MUST exist but this somehow implies that we can pick ANY $v_{m} \in V_{m}$ which implies that we have at least m unique starting points for our Hamiltonian cycle. this somehow implies that we must have each $v_m$ have degree at least m but by definition we have degree of each $n = m$ since the number of edges in $K_{m,n}=mn$ we have $Deg {V_{m}} + Deg {V_{n}}= 2mn$ This implies that $mm + nm= 2mn$ or $m + n= 2n$ or $m= 2n-n$ or $m=n$

Is possible to prove in the way i have attempted in Q2? could someone help me prove it this way? I feel like it would help my understanding alot if i could do it directly.

## 1 Answer

On showing $m=n$, you could approach the process as follows:

Any path in a bipartite graph alternates between the two parts, and all cycles are of even length. Given the Hamiltonian cycle of length $2k$, we know that all nodes are visited once only and $k$ nodes in each part are visited on alternate steps of the cycle. Therefore $m=k$ and $n=k$ ie. $m=n$.

• That makes much better use of the Hamiltonian property thank you. – Faust Jan 21 '17 at 20:12