0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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?) $\endgroup$ – Steve Kass Oct 20 '14 at 4:11
  • 2
    $\begingroup$ 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. $\endgroup$ – LearnToMath Oct 20 '14 at 4:36
2
$\begingroup$

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 if "arbitrary" counts as a pun in this context (arbor is latin for tree)

$\endgroup$
  • $\begingroup$ 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 :(? $\endgroup$ – LearnToMath Oct 19 '14 at 18:18
  • $\begingroup$ 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 $\endgroup$ – Kelvin Soh Oct 19 '14 at 18:32
  • $\begingroup$ Thank you for the clarification, Kelvin. In general, for a proof by induction the proof strategy would be to move "backwards" from the step then? One more question. Why does Hagen suggest removing an edge. Shouldn't it rather be removing a vertex? $\endgroup$ – LearnToMath Oct 19 '14 at 18:44
  • $\begingroup$ I've updated the answer with an alternative proof. Thank your for your feedback. $\endgroup$ – LearnToMath Oct 20 '14 at 4:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.