Out of Class Assignment for 9/4

Math 110 Graph Theory Out of Class Assignment

You should complete each of the problems below on a separate sheet of paper. These problems will be collected in class for a grade on Wednesday, September 9, 2015.

1. For each of the following conditions, draw a graph that satisfies the conditions. If you believe it is impossible, explain your reasoning.
   (a) A simple graph with 4 vertices, two of which have degree 2. (b) A simple graph with 3 odd vertices.
   (c) a connected graph with a bridge. Identify the bridge.
   
2. Sketch a graph with vertices A, B, C, D, E and edges {AB, AE, BD, BC, BE, CE, DE}.
   
3. The following questions deal with the graph below.
   
   
   
   
   
   
   
   1. (a)  Give the degree of vertex F .
      
   2. (b)  What is the length of the path FBCGEF?
      
   3. (c)  Can the graph be colored with four colors? Three? If so, give a coloring (label the vertices with the assigned color).
      
4. The following questions deal with the graph below.
   
   
   
   
   
   1. (a)  Give the degree of vertex C.
      
   2. (b)  Is ABGE a path in the graph?
      
   3. (c)  Give a path of length 4 in the graph, starting at A.
      
   4. (d)  Can you start at one vertex, and trace every edge in the graph exactly once (so no repeating edges), and return to the starting vertex? (ie, Does the graph have an Euler circuit?) Why or why not?
      

1