Let t be a set of subtrees of a tree t and k isin nshow

Question

1. Let T be a set of subtrees of a tree T, and k ∈ N.

(i) Show that if the trees in T have pairwise non-empty intersection then their overall intersection Π T is non-empty.

(ii) Show that either T contains k disjoint trees or there is a set of at most k-1 vertices of T meeting every tree in T.

Hint: The easiest solution is to apply induction on |T|. What kind of vertex of T will be best to delete in the induction step? 

2. Show that every automorphism of a tree fixes a vertex or an edge.

Hint: Induction on |T| is a possibility, but not the only one.

3. Prove or disprove that every connected graph contains a walk that traverses each of its edges exactly once in each direction.

Hint: Try to imitate the proof of Theorem 1.8.1.

Answer 1

Solve the following questions by showing all the concepts and methods used to solve it. Question 1: Suppose T be a set of subtrees of a tree T, and k ? N. (a) Verify that if trees in T encompass pair-wise non-empty intersection then their overall intersection ? T is non-empty. (b) Verify that either T includes k disjoint trees or there is a set of at most k-1 vertices of T meeting each and every tree in T. Question 2: Verify that each and every automorphism of a tree fixes a vertex or the edge.