Proving a graph doesn't have a perfect matching

Question

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?

Answer 1

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.

Answer 2

As Daniel Mathias gave the hint;

The graph $G$ is disconnected. Subgraph generated by $\{a_2,b_2,b_3,a_5,a_6,b_5,b_6\}$ is one component and subgraph generated by $\{a_1,a_3,a_4,b_1,b_4\}$ is another component.

Now if $G$ has a perfect matching then both components also have perfect matching. But none of the components have perfect matching because each has odd number of vertices (Reason: A graph has perfect matching with $M$ edges then it necessarily has $2M$ vertices).

Answer 3

Hall's Marriage Theorem can be used to prove that the above bipartite graph does not admit a perfect matching.

Hall's Marriage Theorem: Let $G$ be a bipartite graph with $A$ and $B$ as partite sets. Then $G$ contains a perfect matching if and only if:

$1 . |A| = |B|$

$2 . |S| \leq |N(S)|,$ $\forall$ $S$ $\subseteq$ $A$

where $S$ is any subset of $A$ consisting of vertices of $A$, and $N(S)$ (read: neighbors of $S$) is the set of vertices in $B$ that are adjacent to the vertices of $S$. Formally, $N(S) = $ {$b_{i}$ $\in$ $B:$ $a_{i}$ ~ $b_{i}$ for all $a_{i}$ $\in$ $S$}

In the given graph, the first condition is clearly satisfied, as the cardinality of both the partite sets is the same (which is 6).

However, the second condition is violated. Choose $S$ $=$ {$a_{1}$, $a_{3}$, $a_{4}$}. Then $N(S)$ = {$b_{1}$, $b_{4}$}. Clearly in this case, $|S| > |N(S)|$, thus violating the second condition of Hall's Marriage Theorem.

As it is a necessary condition for a bipartite graph to admit a perfect matching, it follows that the given bipartite graph has no perfect matching.