Stony Brook University
MAT 118 Spring 2013


Assignment 5 due in Recitation, week of March 4

Euler circuits and Euler paths

An Euler path in a graph gives a way of traversing all the edges exactly once, but it is not required that you start and end up at the same vertex.

A. Work through mindscapes 18, 19, 20, 21 on page 398, which lead you through exploration of this concept.

B. Explain why the 7 bridges of Königsberg do not admit an Euler path. (This was in fact Euler's original problem, back in 1743).

C. Mindscape 33. This involves making up a story, and will be graded S/U. It must relate somehow to Euler circuits or Euler paths, and must be in your own words.

Planar graphs and the Euler characteristic

Remember in all these problems that the outside of the graph always counts as one of the "regions."

A graph is connected if any two vertices can be joined by a chain of edges (see page 403).

D. Work mindscapes 26, 27, 28 on page 411, which explore what happens if the Euler characteristic is computed for a graph which is not connected.