Name:_____________________________________

  1. Draw a graph, G, associated with the following adjacency matrix M.

    2.  M

    a

    b

    c

    d

    e

    a

    0

    1

    1

    1

    0

    b

    1

    0

    1

    1

    1

    c

    1

    1

    0

    1

    0

    d

    1

    1

    1

    0

    0

    e

    0

    1

    0

    0

    0
  2. G from problem 1.
    1. Does G have an Euler Circuit? If so list one.
    2. How many 2 walks are there from d to c?
    3. Fill in the missing values for M 22,2 and M 22,5.

    M 2

    a

    b

    c

    d

    e

    a

    3

    2

    2

    2

    1

    b

    2

    		  

    2

    2

    c

    2

    2

    3

    2

    1

    d

    2

    2

    2

    3

    1

    e

    1

    1

    1

    1
  3. Given the following graph G(5, 6) with V = {a, b, c, d, e}, E = {1, 2, 3, 4, 5, 6}:
    1. Find all cut-points.
    2. Find all bridges.
    3. Find the total degree of this graph.
    4. Find a simple path traversing every vertex.
  1. Either draw a graph with the specified properties in the labeled vertices below (next page) or explain why no such graph exists.
    1. Simple graph with 5 vertices of degrees 2, 2, 2, 3, 3.
    2. Graph with 5 vertices of degrees 1, 2, 3, 4, 5.
    3. Simple graph with 5 vertices of degrees 1, 2, 2, 3, 3.
    4. Simple connected graph with 5 vertices of degrees 1, 1, 2, 2, 2.
  1. Use either Kruskal's or Prim's Algorithm to find a minimum spanning tree. Specify the algorithm you use and show your work. What is the weight of your spanning tree?