Problem 11 - Discrete Mathematics with Applications

Question

Let \(n\) denote the number of vertices of a tree and \(e\) the number of edges. Verify that \(e=n-1\) for each tree. IMAGE IS NOT AVAILABLE TO COPY

Step-by-Step Solution

Answer

By mathematical induction, we have shown that for any tree with \(n\) vertices, the number of edges \(e\) is equal to \(n-1\). This holds for the base case of a single vertex, and for a tree with \(k+1\) vertices, given our inductive hypothesis that it holds for a tree with \(k\) vertices.

Step 1: Base Case

First, let's consider the base case with a simple tree, where the number of vertices, \(n\), is equal to 1. In this case, there are no edges in the tree since there is only one vertex. Since \(n = 1\), \(n-1 = 0\), and thus \(e = n-1\), which means the property holds in the base case.

Step 2: Inductive Hypothesis

Assume that the property holds for some tree with \(k\) vertices, such that the number of edges, \(e_k\), equals \(k-1\). This will be our inductive hypothesis.

Step 3: Inductive Step

Now we need to prove that the property holds for a tree with \(k+1\) vertices. Let's consider a tree with \(k+1\) vertices. To create this tree, we need to add one vertex and an edge connecting it to a tree with \(k\) vertices, which we have assumed to hold the property according to the inductive hypothesis. Since there are \(k-1\) edges in the tree with \(k\) vertices, when adding one vertex and one edge, the number of edges \(e_{k+1}\) is equal to \((k-1) + 1 = k\). Thus, for a tree with \(k+1\) vertices, we have: \[e_{k+1} = k\] Since \(e_{k+1} = (k+1)-1 = k\), the property holds for a tree with \(k+1\) vertices as well.

Step 4: Conclusion

By mathematical induction, we have shown that the property holds for a tree with any number of vertices \(n\). Therefore, we can conclude that for any tree, the number of edges \(e\) is equal to \(n-1\).