CSC 133 Discrete Structures Quiz 11.1_3 Name:_____________________________________

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

    2.  

    a

    b

    c

    d

    e

    a

    0

    1

    0

    0

    1

    b

    1

    0

    1

    1

    1

    c

    0

    1

    0

    1

    0

    d

    0

    1

    1

    0

    1

    e

    1

    1

    0

    1

    0

  2. Does G (from problem 1) have a Hamiltonian Circuit? If so list one.
    1. Does G have an Euler Circuit? If so list one.
    2. How many 2 walks are there from b to e?
    3. Fill in the missing value for M 22,2.

    M 2=

     

    a

    b

    c

    d

    e

    a

    2

    1

    1

    2

    1

    b

    1

    		  

    1

    2

    2

    c

    1

    1

    2

    1

    2

    d

    2

    2

    1

    3

    1

    e

    1

    2

    2

    1

    3

  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 loops.
    2. Find all parallel edges.
    3. Find the degree of vertex e.
    4. Find the total degree of the graph.
    5. Find a simple path traversing every vertex.
  1. Either draw a graph with the specified properties 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 2, 2, 2, 4, 4.
    3. Simple graph with 5 vertices of degrees 1, 2, 2, 3, 3.
    4. Simple graph with 3 vertices of degrees 4, 3, 3, 2.
  1. Draw K3,2, does an Euler path exist in this graph? Is K3,2 Eulerian?