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 |