March 13, 2013 Name: Key
A(3) B(4) C(4) D(2) E(2) F(1)
D(2) E(2) F(1)
1. Next to each vertex, write its degree
See in red
2. Does this graph have any bridges?
If so, where?
Yes, AB and BF are bridges
3. Find 2 different circuits (not necessarily Euler circuits) on this graph
There are several to choose from. Some options include ACDA, CC, BEB, etc.
4. Does this graph have an Euler path? Either find one, listing the vertices in the order they are visited, or carefully explain why one does not exist.
Yes, it does. One possibility is ACCDABEBF
5. Find an eulerization of this graph. Carefully draw the duplicate edges on the graph.
You need to draw edges making A and F even (and leaving all of the others even). The easiest way to do this is connecting A to B with a 2nd edge, and then B to F with a 2nd edge.