Graph Theory37 sections · 1633 units
Open in Course

Quiz: Hall's Marriage Theorem

Knowledge check

Check Your Understanding

You have 44 left nodes with neighbor sets {1,2}\{1,2\}, {1,2}\{1,2\}, {1,2}\{1,2\}, {3}\{3\}. Does a perfect matching exist?

  1. A.Yes, because every left node has at least one neighbor
  2. B.Yes, Hall's condition holds for all subsets
  3. C.No, because node 44 has only 11 neighbor
  4. D.No, the first 33 nodes share only 22 neighbors, violating Hall's condition
Start the roadmap to answer the quizzes and solve the challenges