# 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.

• I just fixed a few confusing typos. Hope that is ok. – almagest May 7 '16 at 7:37
• A good start. In case 1 you need to explain why $n=0$ (answer the graph is connected). In case 2, your argument is somewhat unclear. It might be easier to try removing the vertex with a single edge and use induction. – almagest May 7 '16 at 7:41
• Also have a look at this question and its answers – drhab May 7 '16 at 8:23
• I don't understand what you're trying to do. I know that a tree with $n$ edges has $n+1$ vertices, but that's not what you're saying. What is "the tree of" a connected finite graph?? Your title says that, if you have a connected nonempty finite graph—let's call if $G$—and if $G$ has $n$ edges, then the "tree" of $G$ (whatever that is) has $n+1$ vertices. All right, let $G=K_5,$ that's a connected finite graph. It has $10$ edges, so according to you its tree has $11$ vertices. So whatever tree you're talking about can't be a subgraph of $G,$ which has only $5$ vertices. – bof May 7 '16 at 8:40

## 1 Answer

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$.