Question

3. Given graph G-(V, E), prove that the following statements are equivalent. [Note: the following statements are equivalent definitions of a "tree graph".]

Answer 1

Theorem: Let T be a graph with n vertices. Then the following statements are equivalent: (i) T is a tree: (ii) T contains no cycles, and has n - 1 edges: (iii) T is connected, and has n - 1 edges: (iv) T is connected, and each edge is a bridge: (v) any two vertices of T are connected by exactly one path: (vi) T contains no cycles, but the addition of any new edge creates exactly one cycle. pf. We assume that n greaterthanorequalto 2. (Otherwise trivial) (i) implies (ii) Induction on n. Clear for n = 2. Assume n vertices and remove an edge. Disconnects T into 2 trees (T_1, T_2) with n_1, n_2 vertices. (n = n_1 + n_2) By induction, T_1 has n_1 - 1 vertices, and T_2 has n_2 - 1 vertices. It follows that T has (n_1 - 1) + (n_2 - 1) + 1 = n - 1 verices. (ii) implies (iii) If T is disconnected