Try It Now

Exercises

1. Given the following vertex sets, draw all possible undirected trees that connect them.
   1. V_a = {right, left}
   2. V_b= {+, −, 0}
   3. V_c= {north, south, east, west}.
      
      
3. 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|.
   
   
5. 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, P_n, 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
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.