Problem #1

Look at the graph on p.228. All four vertices have odd degree. In order to make all the vertices have even degree, two new bridges need to be built.

Problem #2

Problem #4

b) here is the cycle described as a list of vertices: 01 10 01 11 10 00 00 01

Problem #5

Problem #6

The de Bruijn graph has 1000 vertices, each vertex being a sequence of three digits. From each vertex, there are 10 edges going out with labels 0..9, and 10 edges coming in with labels 0..9 (of course the loop has been counted twice here because it goes out and comes in). So the degree of each vertex is 20. Since 20 is an even number, there does exist an Euler cycle.

Problem #7

Always. The degree of each vertex is 2k, an even number.

Problem #8

a) Yes. Form a complete graph with 7 nodes, and label the nodes 0,...,6. This graph has an Euler cycle because the degree of each vertex is 6. Use this cycle to tell you how to arrange the dominoes.

b) No. This would correspond to a cycle in the complete graph with 6 nodes. Since all vertices have odd degree, no such cycle can exist.