Assignment help 3842

1. Leaf is a vertex of degree one. Let T be a tree with 2n vertices in which no vertex has degree 2. Show that T has at least n leaves.

2. Give an example of an infinite tree which has paths of arbitrarily large finite length but no infinite path

3. Construct all semi-Eulerian and semi-Hamiltonian trees on 100 vertices.

4. Let T1,T2,T3 be subtrees of a finite tree T such that Ti ? Tj ?  {null} for all 1<= i < j <= 3 show that T1 ? T2 ? T3 ? {null}

5. Let 2 <= k <= n-1. Show that there is a tree with n vertices and k leaves.

6. Let T be a tree on 101 vertices. Show that every isomorphism of T fixes some vertex.

7. A Binary tree is a rooted tree in which each node has at most two children. Let T be a binary tree with 2^n – 1 vertices where n >=2. Show that T has a path of length n-1.