# Thread: Dominoes - Graph theory

1. ## 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.

2. 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

3. Thanks, that is very helpful, I understand it now!

,

,

,

,

,

,

,

,

,

,

,

,

,

,

# why there is a loop in dominoz problem in graph theory

Click on a term to search for related topics.