Solutions

  1. Answer: The number of trees are: (a) 1, (b) 3, and (c) 16. The trees that connect Vc are:



  2. Hint: Use induction on |E|.

  3. Answer:
    1. Assume that (V, E) is a tree with |V| ≥ 2, and all but possibly one vertex in V has degree two or more.

      \begin{align*} 2|E| = \sum_{v \in V} \mathrm{deg}(v)) \geq 2|V|-1 &\Rightarrow |E| \geq |V| - \frac{1}{2} \\ &\Rightarrow |E| \geq |V| \\ &\Rightarrow (v,E) \mathrm{is \; not \; a \; tree} \end{align*}

    2. The proof of this part is similar to part a in that we can infer 2|E|≥ 2|V| - 1, using the fact that a non-chain tree has at least one vertex of degree three or more.