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?

Question 2

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

Question 3

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

Question 4

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

Question 5

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




Submit Reset

 

 

Return to top