Page 278-9 Exercise 8


The definition in the text states that "A tree is a finite set of one or more nodes such that 1) there is a specially desig­
nated node called the root; 2) the remaining nodes are partitioned into n ≤ 0 disjoint sets T1, ... ,Tnwhere each of these sets is a
tree. T1, ... ,Tn are called the subtrees of the root."

This definition is equivalent to statement c since the condition that T1, ... ,Tn be disjoint sets means that there can be only one path between any two vertices.  Since the sets are disjoint there can be no cross-edges in the graph. This means that
there can not be multiple paths between vertices.

Statement c implies statement d because a connected graph with cross-edges must have more than n edges, and hence is cyclic.  Therefore, the graph must be acyclic, and contain n-1 edges.

Statement d implies statement b because removing an edge from a  cyclic graph produces a connected graph.  Since the graph is not cyclic, removing an edge must produce a graph that is not connected.  In essence, all nodes except leaf nodes are articula­
tion points.