Chapter 14.4, Problem 56E

Vertex/Edge Relationship In this exercise, we explore why the number of edges in a tree is one less than the number of vertices. Because the statement is clearly true for a tree with only one vertex, we will consider a tree with more than one vertex. Answer parts (a)-(h) in order.

(a) How many components does the tree have?

(b) Why must the tree have at least one edge?

(c) Remove one edge from the tree. How many components does the resulting graph have?

(d) You have not created any new circuits by removing the edge, so each of the components of the resulting graph is a tree. If the remaining graph still has edges, choose any edge and remove it. (You have now removed 2 edges from the original tree.) Altogether, how many components remain?

(e) Repeat the procedure described in (d). If you remove 3 edges from the original tree, how many components remain? If you remove 4 edges from your original tree, how many components remain?

(f) Repeat the procedure in (d) until you have removed all the edges from the tree. If you have to remove n edges to achieve this, determine an expression involving n for the number of components remaining.

(g) What are the components that remain when you have removed all the edges from the tree?

(h) What can you conclude about the number of vertices in a tree with n edges?