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