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