Week 0 Quiz
Use this quiz to test your knowledge of some background material from Discrete Maths I.
Question 1
Suppose G is a non-planar graph with n vertices. Which of the following must be true?
- G must have chromatic number at least 5
- G must contain either K5 or K3,3 as a subgraph
- G must have more than 3n−6 edges
- None of the above
Question 2
Adding an edge to a tree must
- decrease the number of leaves by one
- create exactly one cycle
- create at least two cycles
- make the graph 2-connected
Question 3
If G has n vertices and minimum degree greater than 12n, G must have
- a Hamiltonian cycle
- a triangle
- both of the above
- none of the above
Question 4
The number of labelled graphs on n vertices with m edges is
- nm
- nm
- \binom{n}{2}^m
- \binom{\binom{n}{2}}{m}
Question 5
The Ramsey number R(3,3) is
- 6
- 17
- 42
- still unknown
Submit | Reset |