The Art and Craft of Problem Solving

112 CHAPTER 4 THREE IMPORTANT CROSSOVER TACTICS

In a tree, we call the vertices with degree 1 leaves.^3

It certainly seems plausible that trees must have leaves. In fact,

Every tree with two or more vertices has at least two leaves.

Informally, this is pretty obvious. Since a tree has no cycles, it has to have paths where

the starting and ending vertex are different. These two vertices will have degree 1.

But this is a little vague. Here is a rigorous proof that uses the extreme principle and

argument by contradiction:

Given a tree, pick any vertex. Now consider all paths that include this vertex and

pick the longest one, i.e., the path that contains the most vertices. Since the graph is

a tree, there are no cycles, so there is no ambiguity here-no path can cross back on

itself. And also, since trees are connected, we are guaranteed that there are paths to

begin with.

Let P := XlX 2 .. 'Xn denote this longest path, where the Xi are vertices. We claim

that Xl and Xn must have degree 1. Suppose that X l had degree more than 1. Then Xl

has among its neighbors the vertices X2 and y. Observe that y cannot be any of the

vertices X 3 ,X 4 , ... ,Xn, because that would create a cycle! But if y is not one of these

vertices, then we could create a longer path YXlX 2 .. 'Xn which contradicts the maxi­

mality of P. Thus d(xJ ) = 1, and a similar argument shows that d(xn) = 1. •

When is a connected graph a tree? Intuitively, it seems clear that trees are rather

poor in edges relative to vertices, and indeed, experimentation (do it!) suggests very

strongly that

For trees, the number of edges is exactly one less than the number of

vertices.

This conjecture is a natural candidate for mathematical induction. We shall induct

on the number of vertices v, starting with v = 2. The only tree with two vertices con­

sists of a single edge joining the two vertices, so the base case is true. Now, assume

that we know that all trees with v vertices contain v-I edges. Consider a tree T with

v + 1 vertices. We will show that T has v edges. Pick a leaf (we know that T has

leaves). Remove this vertex, along with the edge emanating from it. What is left? A

graph with v vertices that is still connected (since T was connected, and plucking a

(^3) This tenninology is not quite standard. It is customary to designate one of the degree-l vertices as a "root,"
and indeed there is a whole theory about so-called "rooted trees" that is quite important in computer science, but
will not be discussed here. See [43] for details.