THE UNIVERSITY OF SYDNEY SCHOOL OF MATHEMATICS AND STATISTICS Discrete mathematics and graph theory Semester 1, 2020 MATH2069 Quiz 2 – Sample Student Number: Signature This is the Sample Quiz for the topology component of Math2069. The real quiz contributes 15% towards your final assessment in Math2069. The sample quiz will give you an idea of the sorts of questions that you might be asked in Quiz 2. The real quiz will be similar to this one in difficulty but the questions will be different. Quiz 2 covers material from Lecture 7-1 to Lecture 11-3. The style of the quiz will be similar to the Replacement Quiz for Quiz 1. You will be asked to enter answers to the questions, rather than having to select from different multiple choice options. There will be 8-10 questions with most questions having multiple parts as this gives you more opportunities to gain marks. The solutions to the Sample Quiz will be made on Monday in week 11. It is strongly recommended that you try and to complete this quiz without looking at the solutions. Quiz 2 will be run in canvas during the Practice class in week 12. That is, the quiz will run 2-3pm, Friday May 22. Precise details of how to access the quiz will be given on the day. You will have 50 minutes to complete the quiz. This quiz paper has four pages and 10 questions. MATH2069: Quiz 2 – Sample © 2020 The University of Sydney Discrete mathematics and graph theory MATH2069 Time allowed: 40 minutes 1. Consider the graphs Which of the following is true? a) All of these graphs are isomorphic. b) 퐺 is isomorphic to 퐺′, but is not isomorphic to 퐺′′. c) None of these graphs are isomorphic. d) 퐺′ is isomorphic to 퐺′′, but is not isomorphic to 퐺. 2. Consider the graph Which of the following is true? a) 퐺 is a forest, and Δ(퐺) = 2. b) 퐺 is a tree, and Δ(퐺) = 2. c) 퐺 is isomorphic to 푃5, and Δ(퐺) = 2. d) 퐺 is bipartite, and Δ(퐺) = 0. 3. Which of the following is true? a) Both (0, 2, 2, 2, 4, 4, 4, 4, 4) and (0, 1, 1, 2, 2, 4, 5, 5) are graphic. b) (0, 2, 2, 2, 4, 4, 4, 4, 4) is graphic, but (0, 1, 1, 2, 2, 4, 5, 5) is not graphic. c) (0, 2, 2, 2, 4, 4, 4, 4, 4) is not graphic, but (0, 1, 1, 2, 2, 4, 5, 5) is graphic. d) Neither (0, 2, 2, 2, 4, 4, 4, 4, 4) nor (0, 1, 1, 2, 2, 4, 5, 5) are graphic. 4. Consider the following graph 퐺. Which of the following is true? a) 퐺 has an Eulerian trail, and is Hamiltonian. b) 퐺 has an Eulerian trail, but is not Hamiltonian. c) 퐺 does not have an Eulerian trail, but is Hamiltonian. d) 퐺 does not have an Eulerian trail, and is not Hamiltonian. 5. Consider the tree MATH2069: Quiz 2 – Sample Page 2 of 4 MATH2069 Quiz 2 – Sample 1 2 3 4 5 6 What is the Prüfer sequence of this tree? a) (2, 4, 5, 3) b) (6, 1, 3, 3) c) (1, 6, 3, 3) d) (6, 3, 3, 1) Questions 6 and 7 concern the following weighted graph: 1 3 2 2 1 2 2 3 2 1 2 1 2 2 2 6. What is the weight of a solution of the Chinese Postman Problem? a) 28 b) 32 c) 33 d) 18 7. What is the weight of a minimal spanning tree? a) 14 b) 26 c) 18 d) 28 8. Consider the graph How many spanning trees does this graph have? a) 8 b) 1 c) 3 d) 4 9. Consider the two graphs: MATH2069: Quiz 2 – Sample Page 3 of 4 Discrete mathematics and graph theory MATH2069 Which of the following is true? a) 휒(퐺) = 2, 휒(퐻) = 2 b) 휒(퐺) = 3, 휒(퐻) = 3 c) 휒(퐺) = 4, 휒(퐻) = 2 d) 휒(퐺) = 3, 휒(퐻) = 2 10. Which of the following is true? a) 휒(푃5) = 2, 휒(퐶5) = 2, and 휒(퐾5) = 5.b) 휒(푃5) = 2, 휒(퐶5) = 3, and 휒(퐾5) = 4.c) 휒(푃5) = 2, 휒(퐶5) = 3, and 휒(퐾5) = 5.d) 휒(푃5) = 4, 휒(퐶5) = 3, and 휒(퐾5) = 4. This is the last page of the quiz paper. MATH2069: Quiz 2 – Sample Page 4 of 4
