Answer to Problem 19

We will prove it by induction on , the (finite) number of vertices.

(Base case): If , then the number of edges, , is , and the statement holds.

(Inductive step): Let the statement hold true for any tree with vertices, , and let be a tree with vertices.

If the degree of every vertex in were , then we would be able to construct a cycle as follows:

  1. Start at any vertex and select a vertex adjacent to it.
  2. Then select a vertex adjacent to but different from .
  3. Continue this way by selecting a new vertex which is different from the one selected just before. (This is possible if the degree of every vertex is ).
  4. Since the graph is finite, at some moment we will have to select a vertex which has already been selected more than one step previously. Such a selection creates a cycle, which a tree cannot have.

Now, let be a vertex of degree 1 in . If we remove together with the edge incident to it from , then the remaining graph has no cycles and is connected (be sure you are convinced of this before proceeding).

Thus, is a tree. By induction, the statement is correct for :



Equation 7

But, and .

Therefore, .