Try It Now

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


  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,
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.