Reference no: EM13926827

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?