Question 4 (25 marks) (a) (b) First, define what a tree is. And then state the hand-shaking theorem. Finally, decide whether there exists a tree with six vertices of the following degrees shown below. Either draw such a tree with the specific properties or explain why such tree does not exist. (i) 2, 1, 2, 1, 1, 2 (ii) 1,3, 1, 2, 1, 2 (8 marks) The complete 3-partite graph K n, m, p, with n, m, p 21, is a simple graph that has its vertex set partitioned into 3 disjoint non-empty subsets of n, m and p vertices, respectively. Two vertices are adjacent if and only if they are in different subsets in the partition. (i) Draw K1, 2, 2. Give the definition of Euler circuit. (iii) Find a Euler circuit on K1, 2, 2 if it exists. If not, justify your conclusion