Try It Now

Work these exercises to see how well you understand this material.

Exercises

  1. Locate a map of New York City and draw a graph that represents its landmasses, bridges, and tunnels. Is there an Eulerian path through New York? You can do the same with any other city that has at least two landmasses.

  2. Write out the Gray Code for the 4-cube.

  3. The Euler Construction Company has been contracted to construct an extra bridge in Koenigsberg so that an Eulerian path through the town exists. Can this be done, and if so, where should the bridge be built?

  4. Formulate Euler's theorem for directed graphs.

  5. Prove that the number of vertices in an undirected graph with odd degree must be even. Hint. Prove by induction on the number of edges.

    1. Under what conditions will a round-robin tournament graph be Eulerian?
    2. Prove that every round-robin tournament graph is Hamiltonian.

 


Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.