Try It Now

Work these exercises to see how well you understand this material.

Exercises

  1. Given the following vertex sets, draw all possible undirected trees that connect them.
    1. Va = {right, left}
    2. Vb= {+, −, 0}
    3. Vc= {north, south, east, west}.

  2. Prove that if G is a simple undirected graph with no self-loops, then G is a tree if and only if G is connected and |E|= |V| − 1.

    Hint. Use induction on |E|.

    1. Prove that any tree with at least two vertices has at least two vertices of degree 1.
    2. Prove that if a tree has n vertices, n ≥ 4, and is not a path graph, Pn, then it has at least three vertices of degree 1.

 

Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.