Processing math: 0%

Algorithmic Combinatorics

Winter 2018-19

FU Berlin, Mathematics and Informatics

Week 3 Quiz

Use this quiz to test your knowledge and understanding of this week's lectures.

Question 1

If $α'$ is the matching number and $β$ the vertex cover number of an arbitrary graph, then which of the following is true?

• $α' = β$
• $2α' ≤ β$
• $α' ≤ β$
• none of the above

Question 2

Let S be a set of vertices saturated by a matching M in the graph. Which of the following is true?

• every maximum matching saturates S
• there is a maximum matching which saturates S
• there is a maximum matching which does not saturate S
• none of the above

Question 3

What is the total number of perfect matchings in a complete graph on $2n$ vertices?

• $(2n)!$
• $\frac{(2n)!}{n!}$
• $\frac{(2n)!}{n! 2^n}$
• $\frac{ (2n)!}{2^n}$

Question 4

Let $G$ be a graph on $2n$ vertices that has a unique perfect matching. Which of the following is true?

• $G$ is a tree in which removal of each vertex creates a unique odd component
• $G$ has at most $n^2$ edges
• $G$ is bipartite
• none of the above

Question 5

Which of the following conditions is sufficient for a graph $G$ of even order to have a perfect matching?

• $G$ is $k$-regular
• $G$ has no cut-edges
• $G$ is $k$-regular and has at most $k - 2$ cut edges
• none of the above

---

Submit

Reset