Ryerson Crest Ryerson Header

MTH 607 Graph Theory Lab 5

  1. This questions is about the tree T below.
    1. Identify the leaves of T.
    2. Identify the internal vertices of T.
    3. What is the height of T?
    4. Is T a binary tree?
    5. List the vertices of the left subtree of r.
    6. Find a bipartition of T.

  2. Are all trees bipartite? Why?

    1. Find all trees on 4 vertices, up to isomorphism.
    2. Find all binary trees on 4 vertices, up to isomorphism.

  4. Consider graph G below
    1. Find a spanning tree of G.
    2. Identify the fundamental circuits of G with respect to your spanning tree above.
    3. Use your answer to give the number of circuits in G.

    4. Consider the following graphs.
      G1 G2 G3
      1. Find G1 ⊕ G2.
      2. Find G3 ⊕ G2.
      3. Is G1 ⊕ G2 ≅ G1 ⊕ G3?

    5. Is it true that the ring sum of two trees is a tree?

Maintained by: P. Danziger, February 2007.