520
Graphs and Trees
The inductive proof of Example 29 differs in another way from proofs like that
of Example 15 in Chapter 2. In those proofs, there was always a single term in the
series (the last term) whose removal would lead to the “P(k) case,” the inductive hypothesis. In proofs involving trees with k + 1 nodes, which node should be removed
to generate the P(k) case? Usually the node to remove is not unique, but it is not completely arbitrary either. In the proof of Example 29, for instance, removing a non-leaf
node (and the arcs attached to it) from a tree with k + 1 nodes would result in a graph
with k nodes, but not a tree with k nodes, so the inductive hypothesis would not apply.
praCTiCe 23 Prove that in any tree with n nodes, the total number of arc ends is 2n − 2. Of course this
result follows directly from Example 29 because n − 1 arcs means 2(n − 1) = 2n − 2
arc ends, but do a proof by induction on the number of nodes.
example 30
Recall that a tree T can also be constructed recursively by hooking a root node to a
collection of subtrees T 1 , … , T t (see Figure 6.44). This allows us to use structural
induction, discussed in Chapter 3, to prove certain results about trees. We’ll use
structural induction to prove the result of Example 29, namely
A tree with n nodes has n − 1 arcs.
The base case where n = 1 is the same as before. Assume that any subtree T i with
n i nodes has n i − 1 arcs. The tree T constructed from subtrees T 1 , … , T t has n
nodes where
n = 1 + ∙
t
i=1
n i
(The extra 1 is the root node.) Also, T has a arcs where
a = t + ∙
t
i=1
a i
(The extra t counts the arcs from the root of T to the t subtrees.)
By the inductive hypothesis, a i = n i − 1 for each subtree, so
a = t + ∙
t
i=1
a i = t + ∙
t
i=1
(n i − 1) = t + ∙
t
i=1
n i − ∙
t
i=1
1 = t + ∙
t
i=1
n i − t
= ∙
t
i=1
n i = n − 1
■
praCTiCe 24 Prove that in any tree with n nodes, the total number of arc ends is 2n − 2. Use structural
induction.
■
Graphs and Trees
The inductive proof of Example 29 differs in another way from proofs like that
of Example 15 in Chapter 2. In those proofs, there was always a single term in the
series (the last term) whose removal would lead to the “P(k) case,” the inductive hypothesis. In proofs involving trees with k + 1 nodes, which node should be removed
to generate the P(k) case? Usually the node to remove is not unique, but it is not completely arbitrary either. In the proof of Example 29, for instance, removing a non-leaf
node (and the arcs attached to it) from a tree with k + 1 nodes would result in a graph
with k nodes, but not a tree with k nodes, so the inductive hypothesis would not apply.
praCTiCe 23 Prove that in any tree with n nodes, the total number of arc ends is 2n − 2. Of course this
result follows directly from Example 29 because n − 1 arcs means 2(n − 1) = 2n − 2
arc ends, but do a proof by induction on the number of nodes.
example 30
Recall that a tree T can also be constructed recursively by hooking a root node to a
collection of subtrees T 1 , … , T t (see Figure 6.44). This allows us to use structural
induction, discussed in Chapter 3, to prove certain results about trees. We’ll use
structural induction to prove the result of Example 29, namely
A tree with n nodes has n − 1 arcs.
The base case where n = 1 is the same as before. Assume that any subtree T i with
n i nodes has n i − 1 arcs. The tree T constructed from subtrees T 1 , … , T t has n
nodes where
n = 1 + ∙
t
i=1
n i
(The extra 1 is the root node.) Also, T has a arcs where
a = t + ∙
t
i=1
a i
(The extra t counts the arcs from the root of T to the t subtrees.)
By the inductive hypothesis, a i = n i − 1 for each subtree, so
a = t + ∙
t
i=1
a i = t + ∙
t
i=1
(n i − 1) = t + ∙
t
i=1
n i − ∙
t
i=1
1 = t + ∙
t
i=1
n i − t
= ∙
t
i=1
n i = n − 1
■
praCTiCe 24 Prove that in any tree with n nodes, the total number of arc ends is 2n − 2. Use structural
induction.
■