Graph Theory Lessons

Answers to Lesson 20

  1. Depth first tree. . Breadth first tree

    Another spanning tree. . Yet another spanning tree.

  2. An example of a graph on five vertices that is not a tree but such that all of its spanning trees are isomorphic is the circuit C5.

  3. The star Sn (which is isomorphic to the complete bipartite graph K1,n - 1) is isomorphic to the breadth first spanning tree of the complete graph Kn.

e-mail: C. Mawata
© C. Mawata