CSC 133 Discrete Structures Quiz 11.4_6

Name:______________________________

Either draw a graph with the given specifications or explain why no such graph exists.

  1. Binary tree, height 4, 8 terminal vertices.

    Binary tree height 4, 8 terminal vertices (one solution of many possible)
  2. Simple graph, connected, 5 vertices, five edges.
    a simple connected graph with 5 vertices and 5 edges
  3. Are these two graphs isomorphic? If so label their vertices so that the isomorphism is apparent. If not, list an isomorphic invariant that is violated.
    5 vertices, 6 edges

Order and size are the same for both graphs. Their score sequences are (starting at the top of each and working clockwise): 2, 2, 2, 4, 2 and 2, 3, 2, 3, 2. So these two graphs are not isomorphic.