## Try It Now

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

### Exercises

- Given the following vertex sets, draw all possible undirected trees that connect them.
*V*= {right_{a}*,*left}*V*= {+_{b}*,**−**,*0}*V*= {north_{c}*,*south*,*east*,*west}.

- 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*|. -
- Prove that any tree with at least two vertices has at least two vertices of degree 1.
- Prove that if a tree has
*n*vertices,*n**≥*4, and is not a path graph,*P*, then it has at least three vertices of degree 1._{n}

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.