Graph Problems(Euler,Hamilton,Color)

Question

Let be $n_1$, $n_2$ such natural numbers that $n_1\geq 3$ and $n_2\geq 3$ and let be $G_{n1,n2}$ a graph that takes shape by taking $G_{n_1}$, the cycle of $n_1$ vertices, and $G_{n_2}$ the cycle of $n_2$ vertices, and linking all of $G_{n_1}$ vertices with all of $G_{n_2}$ vertices.

a) For which values of $n_1,n_2$ has the graph $G_{n1,n2}$ an Euler cycle ?

b) For which values of ${n_1,n_2}$ has the graph $G_{n1,n2}$ a Hamilton cycle ?

c) For which values of ${n_1,n_2}$ is the graph $G_{n1,n2}$ a 5-colorable but not 4-colorable?

Indication: Show first that in each legal(valid) coloration of $G_{n1,n2}$ the sets of colours that are used for $G_{n_1}$ vertices and $G_{n_2}$ vertices they have to to be foreign from each other.

Answer 1

For b), with high connectivity it is hard to avoid Hamiltonian cycles. For c) have you proved what the hint asks? How many colors are required for a cycle?

Added after the first two comments: The description of Euler cycle is just a restatement of one of the comments to the question, and is correct. For the Hamiltonian cycle, it is true there always is one. To prove it, you should be able to describe one. For example, if $n1=n2$, you could number the vertices in each cycle from 1 to n in order around the cycle. The Hamiltonian cycle is from vertex $i$ in $G_{n1}$ to vertex $i$ in $G_{n2}$, then from vertex $i$ in $G_{n2}$ to vertex $i+1$ in $G_{n1}$ and finally from vertex $n$ in $G_{n2}$ to vertex $1$ in $G_{n1}$. Can you find a construction that works if $n1 \ne n2$?

Did you figure out how many colors it takes just for a single cycle as a function of the number of vertices?

Further addition, now that the due date has probably passed: For b) there is always a Hamiltonian cycle. Start at one vertex of $G_{n1}$ and follow the cycle to the last vertex before you close. Then go to a vertex of $G_{n2}$, traverse the $G_{n2}$ cycle until the last vertex and go back to the vertex you started at. This is a Hamiltonian cycle. For c), coloring a cycle takes $2$ colors if the cycle is even and $3$ if it is odd. As the colors in the two cycles must be distinct, the whole graph takes $4$ if $n1, n2$ are both even, $5$ if one is even and one is odd, $6$ if they are both odd.