Let G be a tree, and let $k$ be the number of vertices in G whose degree is at least 3. Prove that G has at least $k+2$ leaves. I assume that I need to use the theorem that states that the sum of the degrees of the vertices is equal to twice the number of edges. Then, because $k$ must be greater than or equal to 3, the there must be 1.5 edges, but that is impossible. How else can I continue this proof, using the stated theorem?
 A: Suppose there are $n$ vertices and $l$ leaves. Then there are $n - k - l$ vertices of degree 2. So the sum of the degrees of vertices is at least $3k + 2(n - k - l) + l$, which simplifies to $k + 2n - l$.
Using the theorem you mention,
$$
2n - 2 ≥ k + 2n - l
$$
so
$$
l ≥ k + 2.
$$
A: Assuming you made a typo and what you call F in the statement is actually G, then via Induction on the total number of vertices of the graph (let's call this $n$):
Note: You will need the fact that every tree on 3 or more vertices has at least 2 leaves, this is easily proven if you have never seen it before
Base case: $n = 3$
For a tree on 3 vertices, there are no vertices of degree 3, so $k = 0$ and so the result holds as the tree has 2 leaves
Assume the result holds for any tree on $r < n$ vertices,
Consider now a tree $G$ on $n$ vertices such that the number of vertices of degree 3 is $k$, since $G$ is a tree then it has at least 2 leaves, pick one of them and call it $v$
Consider now the graph $G - \{v\}$ obtained by removing $v$ and the edge incident to it from $G$ 
This new graph is a tree on $n - 1$ vertices, and the number of vertices of degree 3 is $k$ (as we have only removed a vertex of degree 1), so by induction, $G - \{v\}$ has at least $k + 2$ leaves
Thus we see that $G$ itself has at least $k + 2$ leaves (as the number of leaves of $G \geq G - \{v\}$)
A: There is already a solid solution, but at OP's request here is an induction argument (IMO the simplest argument).
Every tree on $n+1$ vertices is a tree on $n$ vertices with a leaf attached.  So take an arbitrary tree on $n$ vertices and by induction assume the result holds for this tree.
Attach a leaf.  If you attach it to a vertex with degree one you create 0 new leaves and 0 new vertices of degree higher than $3$, leaving the inequality satisfied.
If you attach it to a vertex of degree two, you create one new leaf and one new vertex of degree 3, leaving the inequality satisfied.
If you attach it to a vertex of degree three or higher you create one new leaf and no new vertices of degree three or higher, so you satisfy the inequality even more strongly.
