1
$\begingroup$

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.

  • 1
    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.2011-03-06
  • 0
    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.2011-03-06
  • 0
    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.2011-03-06
  • 0
    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 course2011-03-06
  • 0
    @Ross i believe you are 100% didn't see it...So what about for having an Euler Cycle that both Gn1 ,Gn2 have to be even Cycles?Is there a way to prove it if i am right?2011-03-06
  • 0
    Sure, count the edges at each vertex. In $G_{n1}$ you have 2 from the cycle and $n2$ from the other graph and similarly for the reverse. So you are right about the Euler cycle. But it is not bipartite (unless $n1=n2=1$) as you will have odd cycles.2011-03-06

1 Answers 1