Consider the following graph:
Find a perfect matching or prove one doesn't exist.
I don't think a perfect matching exists here, as the vertices $a_2, a_3$ and $a_4$ are problematic to us, but I'm having some trouble proving this. Using Hall's theorem, we can prove that a matching of a certain cardinality doesn't exist, but how am I supposed to know the cardinality of the perfect matching in order to prove my claim? Can someone give me a hint how to apply the theorem here?
EDIT: Can I assume that the cardinality of the perfect matching $|M| = 2$, as the smallest vertex cover is {$a_5, a_4$}, and then find two vertices that break Hall's condition?
Best Answer
Suppose a perfect matching $M$ exists. Note that $b_2$ has degree $2$, so either $\{b_2,a_2\}\in M$ or $\{b_2,a_5\}\in M$.
Case I. $\{b_2,a_2\}\in M$. Then, $\{b_3,a_5\}\in M$. Hence, $\{b_5,a_6\}\in M$. Now, $b_6$ cannot be paired.
Case II. $\{b_2,a_5\}\in M$. Hence, $\{b_5,a_6\}\in M$. Now, $b_6$ cannot be paired.