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 \( K_5 \) or \( K_{3,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 \( \frac12 n \), \( 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 \)
- \( n^m \)
- \( \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 |