TITLE: Struggling with Hamiltonian cycle existence.
QUESTION [2 upvotes]: 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.

REPLY [2 votes]: 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$.
{"set_name": "stack_exchange", "score": 2, "question_id": 2107800}