I'm practicing for a math challenge and was asked whether the following graph has a perfect matching. I've tried to randomly connect nodes but couldn't find a way to connect the node in such a way that would result in a perfect matching, so I'm assuming it is not possibile.
But how do I know that it's really not possible? Is there a quicker (structured) way to determine whether there is a perfect matching or not, and how?
I only figured out that the number of nodes should be even, which is true in this case as there are 42 nodes.
Best Answer
There's no such pairing:
Observe that when you remove the $12$ red vertices, the graph splits into $14$ components, each of them having an odd number of vertices.
If there was a perfect pairing, each of the components would have a pair connecting it to some red vertex, but there's too few of them.
This condition on odd components in fact characterizes perfect pairings and it's called the Tutte theorem.