# Soundness of a simple tree edge count proof by induction

I'm trying practice and get better at proofs. Here is my attempt at a proof of the following simple statement:

There are $n-1$ edges in a $n$ vertex tree.

We will prove this by induction on $n$ vertices. Consider the base case, $n=1$, then we clearly have 0 edges.

Let's assume that the claim holds for $n=k$ vertices, and we'll try to show that it must then also hold for a $k+1$ vertices. For $k$ vertices we have then $k-1$ edges according to the claim. Consider adding a vertex. Now, we have a graph with $k + 1$ vertices. Since we are dealing with a tree, it must be connected by definition, so we must add least one edge to connect it to the $k$-vertex tree. Thus, we have a graph with with $k + 1$ vertices and $k$ edges. This new graph $G'$ must also be a tree, because adding a vertex and a single edge cannot produce a new cycle, as moving via the edges we can only enter the newly added vertex, but not leave it.

Finally, we must show that there cannot be any more than $k$ edges in the new graph $G'$. Consider adding an edge $e$ between any pair of nodes $u$ and $v$. Now, we can move from $u$ to $v$ via both the edge $e= (u,v)$ and also via a simple path (using a fact about trees: there is only a single simple path between any two vertices $u$ and $v$), connecting $u$ and $v$. This will form a cycle, which is a contradiction, since trees cannot contain cycles. Thus there cannot be any more than $k$ edges. This completes the proof of the step.

Therefore the total number of edges for a tree of $n$ vertices is exactly $n-1$.

Is this sound?

Edit:

Improved version:

Let's assume that the claim holds for $n=k$ vertices, and we'll try to show that it must then also hold for a $k+1$ vertices. Consider the Tree $T'$ which has $k+1$ vertices. Since every tree has at least one leaf node $v$, we can remove it from $T'$, this obtained tree $T$ now has one node less than $T'$, particularly it has $k$ vertices. According to the induction hypothesis, this $k$-vertex tree must have $k-1$ edges. But then the tree $T'$ must have one edge more, namely $k$ edges. And this is what we wanted to show.

• Your improved version is pretty good. One point you might clarify: When you remove a leaf vertex from $T'$, why can you say that the resulting graph $T$ is a tree? You simply call $T$ the “obtained tree” without giving a reason. (It is true that $T$ is a tree; can you give a clear justification?) – Steve Kass Oct 20 '14 at 4:11
• Maybe I ought to add something like: The obtained graph must also be a tree. Why? Firstly, it must be connected since the degree of a leaf is one, but to break a graph into more than one component it should be adjacent to at least 2 vertices. Secondly, the graph must be acyclic, because a cycle cannot form by removing a leaf node. – LearnToMath Oct 20 '14 at 4:36

It is not a priori valid to assume that a tree on $k+1$ vertices is obtained by adding an edge to a $k$-vertex tree. Instead, you should start from an arbitrary* $(k+1)$-vertex tree and then e.g. investigate what happens upon removing an edge.
• I'm not sure I understand. The only way to get from a $k$ vertex graph to $k + 1$ vertex graph (regardless of the structure of the graph) is to add a vertex. the only thing the proof is saying is that to preserve the property of the tree (connectedness), at least one edge must be added. could you please elaborate where I am going wrong :(? – LearnToMath Oct 19 '14 at 18:18
• The induction step requires us to show that all trees with $k+1$ vertices has $k$ edges. Starting with the induction assumption (a tree with $k$ vertices) is "dangerous" because it is not immediately obvious if all trees with $k+1$ vertices can be obtained starting from such a "smaller" tree. Hence a better start point will be to first assume we have an arbitrary tree with $k+1$ vertices. We remove an appropriate vertex and then apply our induction hypothesis – Kelvin Soh Oct 19 '14 at 18:32