Math 115

March 13, 2013 Name: __ Key __

Quiz 5

A C D

*(**3) * B*(4)**(**4)**(**2)* E*(2)* F*(1)*__All questions relate to the graph shown:__

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 2 ^{nd} edge, and then B to F with a 2^{nd} edge.*