Results 1 to 2 of 2

Math Help - Graph problem(euler,hamilton,color)

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    15

    Graph problem(euler,hamilton,color)

    I would like a little help on that pleace..

    Let be n1,n2 such natural numbers that n1>=3 and n2>=3 and let be C(n1,n2) a graph that takes shape by taking Cn1, the circle of n1 vertices, and Cn2 the circle of n2 vertices, and linking all of Cn1 vertices with all of Cn2 vertices.
    a) For which values of n1,n2 has the graph C(n1,n2) an Euler circle ?
    b) For which values of n1,n2 has the graph C(n1,n2) a Hamilton circle ?
    c) For which values of n1,n2 is the graph C(n1,n2) a 5 -colorable but no 4-colorable?
    Indication: Show first that in each legal coloration C (n1, n2), the sets of colours that are used for Cn1 vertices and Cn2 vertices they have to to be foreign from each other.
    Last edited by nick1978; March 3rd 2011 at 08:37 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Dec 2009
    Posts
    9
    Just look up the definitions of your problem. So as an example, to find a Hamiltonian cycle, you want to find a tour which visits each vertex once and which starts and ends in the same vertex. So somehow you need to pass through all the vertices in the outer cycle, as well as the vertices in the inner cycle, without passing through a vertex twice. So basically you can walk over all the vertices in the outer cycle, than move to the inner cycle, walk over the inner cycle and return to the outer cycle. At least, this should be possible because you state that all vertices of the outer graph are connected with all vertices in the inner graph?

    Ps. usually you talk about cycle's and not about circles afaik.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. cayley hamilton theorem problem...
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: April 24th 2011, 12:23 PM
  2. Euler path and Euler circuit problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 19th 2010, 08:18 PM
  3. Replies: 0
    Last Post: February 20th 2010, 08:26 AM
  4. Euler and Hamilton circuits
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 5th 2008, 11:58 PM
  5. another eye color problem
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: September 15th 2008, 12:13 AM

Search Tags


/mathhelpforum @mathhelpforum