Print this chapterPrint this chapter

Try It Now

Solutions

  1. Answer: Using a recent road map, it appears that an Eulerian circuit exists in New York City, not including the small islands that belong to the city. Lowell, Massachusetts, is located at the confluence of the Merrimack and Concord rivers and has several canals flowing through it. No Eulerian path exists for Lowell.

  2. Answer: Gray Code for the 4-cube:

    G_4 = \begin{pmatrix} 0000\\  0001\\  0011\\  0010\\  0110\\  0111\\  0101\\  0100\\ 1100\\ 1101\\  1111\\  1110\\  1010\\ 1011\\ 1001\\ 1000 \end{pmatrix}

  3. Answer: Any bridge between two landmasses will be sufficient. To get an Eulerian circuit, you must add a second bridge that connects the two landmasses that were not connected by the first bridge.

  4. Answer: Let G = (V, E ) be a directed graph. G has an Eulerian circuit if and only if G is connected and indeg(v) = outdeg(v) for all v ∈ V. There exists an Eulerian path from v1 to v2 if and only if G is connected, indeg(v1) = outdeg(v1) − 1, indeg(v2) = outdeg(v2) + 1, and for all other vertices in V the indegree and outdegree are equal.

  5. Hint: Prove by induction on the number of edges.

  6. Answer: A round-robin tournament graph is rarely Eulerian. It will be Eulerian if it has an odd number of vertices and each vertex (team) wins exactly as many times as it loses. Every round-robin tournament graph has a Hamiltonian path. This can be proven by induction on the number of vertices.