Math 115

March 13, 2013                       Name:                          Key                                                                 

Quiz 5              

 

    A(3)                                           B(4)

 

 

 

 

 

 C(4)

                      D(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 2nd edge, and then B to F with a 2nd edge.