2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

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

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.