Results 1 to 3 of 3

Math Help - Dominoes - Graph theory

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    308

    Dominoes - Graph theory

    A domino is a rectangle divided into two squares with each square numbered one of 0,1,2,3,4,5,6. Two squares on a single domino can have the same number. Show that distinct dominoes can be arranged in a circle so that touching dominoes have adjacent squares with identical numbers.

    This is how I interpreted this question. But the solution says something else and I don't know how they got it.

    This is my diagram



    Now we can turn this into a graph, G, by letting the dominoes be the edges and each of the numbers be vertices.

    Clearly, G is a connected graph and each vertex's degree is 2. Thus G has a Euler's cycle, therefore the dominoes can be arranged in a circle so that touching dominoes have adjacent squares with identical numbers.

    Now the solutions says this: (My questions are in brackets)

    "We model the situation as a graph G with seven vertices labeled 0,1,2,3,4,5,6. The edges represent the dominoes. There is one edge between each distinct pair of vertices (Why do you connect every single vertex to each other?) and there is one loop at each vertex (Why do you have a loop at each vertex?). Notice that G is connected. Now the dominoes can be arranged in a circle so that touching dominoes have adjacent squares with identical numbers iff G contains an Euler cycle (Why does G have to contain an Euler cycle so that adjacent squares will have identical numbers?). Since the degree of each vertex is 8, then G has an Euler cycle. Therefore, the dominoes can be arranged in a circle so that touching dominoes have adjacent squares with identical numbers."

    Many thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    first u should know the rocks of Dominoes it has all combination between the seven numbers
    0-0,0-1,0-2,0-3,...

    since the repetition is occurred u will have loops for example u have a rock with 0-0 so 0 is joint with it self same thing for all the vertices and every vertex is joined to all the other ones since all combination found

    if u find the Euler cycle u are done since Eulerian cylce pass through all edges without repetition, and u want to order the Dominoes in a cycle
    there is a theorem that said if all vertices in the graph has an even degree then the graph is Eulerian so it has a cycle that pass through all edges once
    the graph will look like this

    Dominoes - Graph theory-graph.jpg
    Last edited by Amer; July 22nd 2010 at 11:33 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2009
    Posts
    308
    Thanks, that is very helpful, I understand it now!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory, bipartite Graph
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 10th 2012, 05:47 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 03:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM

Search Tags


/mathhelpforum @mathhelpforum