Prove theorem 151 theorem 151 the following assertions are

Question

1. Prove Theorem 1.5.1. Theorem 1.5.1.

The following assertions are equivalent for a graph T:

(i) T is a tree;

(ii) Any two vertices of T are linked by a unique path in T;

(iii) T is minimally connected, i.e. T is connected but T − e is disconnected for every edge e ∈ T;

(iv) T is maximally acyclic, i.e. T contains no cycle but T + xy does, for any two non-adjacent vertices x, y ∈ T.

Hint: Show (i) ⇒ (ii) ⇒ (iii) ⇒ (iv) ⇒ (i) from the definitions of the relevant concepts.

2. Show that every tree T has at least ?(T) leaves.

Hint: How can we turn distinct neighbors into distinct leaves?

3. Show that a tree without a vertex of degree 2 has more leaves than other vertices. Can you find a very short proof that does not use; induction?  

Answer 1

1. Explain theorem with all assortment using as 1.5.1. The given assertions are balanced for a graph T: (i) T is a tree; (ii) Any 2 vertices of T are linked via a exclusive path in T; (iii) For T is minimally joined, that is T is joined but T - e is disconnected for every edge e ? T; (iv) For T is maximally acyclic, i.e. T encloses no cycle but T + xy does, for any 2 non-adjacent vertices x, y ? T. As giving Suggestion that: demonstrate (i) ? (ii) ? (iii) ? (iv) ? (i) from the definitions of the relevant concepts. 2. Illustrate that every tree T has at least?(T) that is departs.