Math 115

October 14, 2009                     Name:                          Key                                                                 

 

 

                                                               A (3)

                                                                                          

                          B(2)

C(2)                    D(4)                       E(4)                               

                                                                                  F(4)

 

 

 

 

 

 

 

    G(2)                   H(3)                                          I(2)
 
Quiz 5              

 

 All questions elate to the graph shown:

1. Next to each vertex, write its degree

  (see graph)

 

2.  Does this graph have any bridges?

     If so, where?

 

Yes, DE is a bridge

 

 

 

3.  Find 2 different circuits (not necessarily Euler circuits) which start at A

 

 

AEA and ABFIEA.  There are others, including, for example, ABFFIEA

 

 

 

 

4.  Does this graph have an Euler path?  If it does, find one (listing the vertices in the order they are visited).  If it does not, carefully explain why not.

 

Yes it does, as there are only 2 odd vertices.  There are many, one of which is:

HGDHCDEAEIFFBA

 

 

 

 

5.  Find an eulerization of the graph. Carefully draw the extra edges on the graph.

(For simplicity I will describe it instead of drawing it.  Draw a 2nd edge between H and D, then between D and E, and finally between E and A.  All degrees would then be even).