$3.$ Introduction to Trees $(7$ points$)$

$(1)(2$ points$)$ Which of the graphs G$1,$ G$2,$ G$3,$ and G$4$ above are trees? $($briefly justify your

answers$)$

$(2)(5$ points$)$ Use induction on l to show that for all l $>=1,$ a full binary tree with l leaves has

$2$l $1$ vertices total.