Processing math: 75%

Algorithmic Combinatorics

Winter 2016-17

FU Berlin, Mathematics and Informatics

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