# Graph Problems(Euler,Hamilton,Color)

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.

-
What have you tried? –  Aryabhata Mar 5 '11 at 23:52
There is a well-known criterion for when graphs are Eulerian. It should be easy to apply here. For Hamiltonian and 4-coloring, try some examples and you'll figure it out. –  aaron Mar 6 '11 at 0:01
A graph G contains an Eulerian circuit if and only if the degree of each vertex is even.I also think that the graph Gn1,n2 is complete and bipartite. –  Nick Mar 6 '11 at 0:07
The graph $G_{n1,n2}$ is not complete unless $n1$ and $n2$ are less than 4, as it is missing the diagonals of the two cycles. –  Ross Millikan Mar 6 '11 at 0:11
I think each of n1,n2 has to be even or else not all the degree of each vertex of Gn1,n2 will be even thus no euler..so in mathimatical terms how to prove the above if it is right of course –  Nick Mar 6 '11 at 0:13

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.

-
Well i made some progress and i would be gratefull to let me know if i am on the right road.. –  Nick Mar 6 '11 at 17:38
In order to have Gn1,n2 a Euler cycle n1 and n2 have to be even so the degree of every vertex is even....If n1 is odd and the degree of it's every vertex is even then the degree of every vertex of Gn2 must be odd and n2 is even and vice versa.AS for hamilton cycle i can find any n1 or n2 for which there IS NOT a hamilton cycle.Finally for the chromatic number i believe that one of Gn1 , Gn2 must be 3-colorable and the other 2-colorable.What do you think? –  Nick Mar 6 '11 at 17:55