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 \) edge
- None of the above
Question 2
A graph on \( n \) vertices is a tree if and only if
- it is acyclic
- it is connected and has \( n - 1 \) edges
- addition of an edge creates a unique cycle in it
- all of the above
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 |