- Determine whether there exist Euler trails in the following graphs
- Determine the number of Hamiltonian cycles in K2,3 and K4,4
My approach:
A1. After observing graph 1, 8 vertices (boundary) have odd degrees.
It is contradictory to the definition (exactly 2 vertices must have odd degree).
In graph 2, there exists euler trails because exactly 2 vertices (top left- outer region and top right- outer region) have odd degrees.
A2. Hamiltonian cycle: contains every vertex one and only one time or proving by Dirac's theorem.
Following the Dirac's theorem:
For K2,3, number of vertices, n= 5, n/2= 2.5
For 2 vertices, deg (v)= 3; for the other 3 vertices, deg (v) = 2 (which is less than 2.5)
To satisfy Dirac's condition, for every vertex, v, deg (v)>=n/2.
Hence, no hamiltonian cycle.
For K4,4, number of vertices, n=8, n/2 =4
For all the veritces, deg (v)= 4;
Hence, hamiltonian cycle exists.
But I am not sure how to find the total number of hamiltonian cycles.
Best Answer
For $K_{4,4}$ you can refer to this question.
For $K_{2,3}$, Suppose that you have an Hamiltonian cycle $(v_1v_2v_3v_4v_5)$.
Your graph is composed of two independent set of vertices $A$ and $B$, with $\vert A\vert=3$ and $\vert B\vert = 2$. Without loss of generality, we can suppose that $v_1\in A$ (otherwise look at the the cycle $(v_2v_3v_4v_5v_1)$).
Then $$v_1\in A \Rightarrow v_2\in B \Rightarrow v_3\in A \Rightarrow v_4\in B \Rightarrow v_5\in A \Rightarrow v_1\in B $$ Hence a contradiction. In general, for any $n\neq m$, $K_{n,m}$ is not Hamiltonian (but Dirac's theorem is not a proof)