Show that the tree of a connected, nonempty finite graph with $n$ edges has $n+1$ vertices. I am working on the following problem in my Topology class. While I do have an idea of how this proof should work I am having a hard time making into a nice proof. Here is the question and my attempt
A finite graph is called a tree if it is nonempty, connected and contains no cycles. Use the fact that a finite graph with no cycles contains a vertex with $\leq 1$ edges.
Attempt:
Since our graph is nonempty there exists at least one vertex. Let this vertex be a point in a tree such that it has $\leq1$. Then we know this vertex has either 0 edges extending from it or 1 edge extending from it.
case 1. this vertex has 0 edges extending from it. This gives us the single vertex so we have $n=0$ edges and $n+1$ vertices.
case 2. this vertex has one edge extending from it. In this case the edge must end a point that is not the original vertex (no cycles). Thus, we have a single edge connected by 2 vertices. We may also see that for any edge added to a vertex on this tree we must have a new endpoint (again there are no cycles). So, for every edge added there is also a vertex added. Continue adding edges and vertices to obtain our tree. Thus, for $n$ edges we have $n+1$ vertices.
 A: Perhaps a cleaner way of presenting your argument is as follows: we'll build your graph vertex-by-vertex.
So pick a vertex somewhere in your tree, since it's non-empty. This gives us 1 vertex and no edges, as we'd hope! Call this $\Gamma_1$, and call your tree $T$.
Now suppose we've already got $\Gamma_n$, a connected, non-empty finite graph with $n$ vertices and $n-1$ edges. If $\Gamma_n$ is all of $T$, then we're done. If not, then there's some vertices or edges in $T$ we haven't added to $\Gamma_n$ yet.
We should never reach the case where there are only edges missing, because $T$ has no cycles ($\Gamma_n$ is itself a tree, so if we add another edge between two of its vertices then we've made a cycle). So we can focus on just the case where there are more vertices to add.
There must be a vertex that has an edge joining it to $\Gamma_n$, since $T$ is connected. So add this vertex and this edge to $\Gamma_n$ to form $\Gamma_{n+1}$, which has $n+1$ vertices and $n$ edges.
Since $T$ is finite, this will eventually terminate, with $\Gamma_n$ being all of $T$.
