Department of Mathematics

Colorado State University

Math 301: Trees, II

Class date: Friday, November 22, 2019
  1. Explain why the Prufer code 01274 is invalid.

  2. Write the Extended Prufer code and draw the corresponding tree:

    1. 01264

    2. 02020

    3. 54321

    4. 7634244

    5. 333333

  3. Write the Prufer code for the trees on the side whiteboard.

  4. Use a random number generator (ex: Google “roll a die”) to draw a random labeled tree with 10 vertices. Justify why your tree really is random.

  5. Show that a graph \(G\) is a tree if and only if it contains no cycles, but adding any new edge creates a cycle.