Marks: /18 DGD (circle one): DGD1 (in DMS1120 ) DGD2 (in STEB0138 ) MAT 1348B (Prof. P. Scott) Tenth Homework Assignment (Updated) Due Friday, April 10 by 9:00 AM. Instructions: Print out this document and staple the pages. You may write on both sides of the paper or insert additional pages if necessary. Submit a nished, presentable product. Drafts and illegible papers will not be marked. Show all relevant work to receive full credit. Submit the assignment to your TA in the DGD or in the submission box labeled MAT 1348B in the Department of Mathematics and Statistics. Late assignments will not be accepted. Additional instructions: This is a group assignment. Form a team of up to 3 members, and submit one paper for the team. All members of the team will receive the same mark. Each member is fully responsible for the assignment and may be asked to reproduce it on short notice. If any member is unable to satisfactorily defend the assignment, the whole assignment may receive a mark of 0. Each member must write his/her name below and sign to conrm that they have read and understand the above instructions. Team Members: 1. LAST NAME (in capitals): Student number: 2. LAST NAME (in capitals): Student number: 3. LAST NAME (in capitals): Student number: First Name: Signature: First Name: Signature: First Name: Signature: 1. Let (a0 , a1 , a2 , . . .) be a sequence of real numbers dened recursively as follows: a0 = 1 a1 = 2 an = 4an1 4an2 for n 2 Using Strong Induction, prove that an = 2n n2n+1 for all integers n 0. Clearly dene the proposition P (n) to be proved.. [5pts] 2. Does there exist (i) a graph, (ii) a simple graph with the following degree sequence? If so, draw a picture of such a graph. If not, explain why. (a) (2, 2, 2, 3, 3, 5, 5) (b) (1, 1, 3, 3, 5, 5, 5) (c) (0, 2, 2, 2, 3, 5, 6) [5pts] 3. Determine all (labelled) subgraphs of the graph below that have at least 2 vertices and are bipartite. Draw a gure representing each of these graphs, and be sure to label the vertices. Note for example, that subgraphs ({a, b}, ) and ({a, c}, ) are distinct, though isomorphic, and should both be listed. a c b [4pts] 4. Let G be a graph with 6 vertices and 10 edges such that every vertex of G has odd degree. If the number of vertices of degree 3 is one more than the number of vertices of degree 5, how many vertices of each degree does G have? [4pts]