Mathematics for Computer Science

11.11. Forests & Trees 359

(b)Prove that any final state of must be a tree on the vertices.

(c)For any state,G^0 , letebe the number of edges inG^0 ,cbe the number of con-

nected components it has, andsbe the number of cycles. For each of the derived

variables below, indicate thestrongestof the properties that it is guaranteed to sat-

isfy, no matter what the starting graphGis and be prepared to briefly explain your

answer.

The choices for properties are: constant,strictly increasing,strictly decreasing,

weakly increasing,weakly decreasing,none of these. The derived variables are

(i)e

(ii)c

(iii)s

(iv)es

(v)cCe

(vi)3cC2e

(vii)cCs

(viii).c;e/, partially ordered coordinatewise (theproductpartial order 9.9.1).

(d)Prove that procedurecreate-spanning-treeterminates. (If your proof depends

on one of the answers to part (c), you must prove that answer is correct.)

Problem 11.36.

Prove that a graph is a tree iff it has a unique path between any two vertices.

Homework Problems

Problem 11.37. (a)Prove that the average degree of a tree is less than 2.

(b)Suppose every vertex in a graph has degree at leastk. Explain why the graph

has a path of lengthk.

Hint:Consider a longest path.

Problem 11.38. (a)Show that every minimum spanning tree of a graph can be the

result of Algorithm 1.