Problem 10 - 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

We prove the formula $e = n - 1$ for any tree, using mathematical induction. Base case: For a tree with one vertex (n = 1) and no edges (e = 0), the formula holds true, as 0 = 1 - 1. Inductive hypothesis: Assume the formula holds for a tree with n vertices. Inductive step: Adding a vertex to the tree increases the number of vertices by 1 and adds exactly one edge. Thus, for the new tree with (n + 1) vertices, we have $e + 1 = (n + 1) - 1$. Since e = n - 1 by the inductive hypothesis, this simplifies to n = n, which verifies the inductive step. By mathematical induction, the formula $e = n - 1$ holds for all trees, showing that the number of edges in a tree is always equal to the number of vertices minus one.

Step 1: Base case

First, we need to prove that the formula holds true for the base case, which is a tree with a single vertex. In this case, n = 1 and there are no edges, so e = 0. We want to verify if e = n - 1.

Step 2: Base case verification

Since there is only one vertex (n = 1) and no edges (e = 0), the left side of the equation is e = 0. The right side is n - 1 = 1 - 1 = 0. Thus, both sides of the equation are equal, 0 = 0, and the base case holds true.

Step 3: Inductive hypothesis

Assume that the formula holds for a tree of n vertices. We will now show that the formula holds true for a tree with n + 1 vertices.

Step 4: Adding a vertex to the tree

In a tree with n vertices, let's add a new vertex (v) connected to one of the existing n vertices. This results in a tree with (n + 1) vertices.

Step 5: Inductive step

As we connected vertex v to the tree, we added exactly one edge. The number of edges for the new tree is e + 1. Now, we substitute this into the formula and check if e + 1 = (n + 1) - 1.

Step 6: Inductive step verification

According to the inductive hypothesis, e = n - 1. So, the left side of the equation is e + 1 = (n - 1) + 1. The right side is (n + 1) - 1, which simplifies to n. Simplifying the left side gives n, as well. Therefore, both sides of the equation are equal, n = n, and the inductive step holds true.

Step 7: Conclusion

By the principle of mathematical induction, the formula e = n - 1 holds for all trees. This proves that the number of edges in a tree is always equal to the number of vertices minus one.