4
$\begingroup$

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.

enter image description here

$\endgroup$

2 Answers 2

Reset to default
10
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Nice. Is there any system or guidance for identifying which vertices to consider? $\endgroup$
    – Joffan
    Jan 13, 2015 at 23:17
  • 4
    $\begingroup$ @Joffan If you want to get algorithmic, there's always the blossom algorithm which resolves your question in polynomial time. $\endgroup$
    – user2345215
    Jan 13, 2015 at 23:22
  • $\begingroup$ This graph is bipartite. It would be a mistake to use the blossom algorithm, the Hungarian algorithm is simpler and faster. $\endgroup$
    – Chris Godsil
    Jan 14, 2015 at 21:42
  • $\begingroup$ @ChrisGodsil That's a nice observation, but it's not obvious from OP's post that he wants it only for bipartite graphs and the fastest way for this one concrete graph is O(1) and it's the picture in my answer. $\endgroup$
    – user2345215
    Jan 14, 2015 at 21:51
  • 1
    $\begingroup$ You can actually lose two of the spots - counting L-to-R spots 5 and 8 can be removed without affecting the argument. $\endgroup$
    – Joffan
    Jan 14, 2015 at 21:57
4
$\begingroup$

Consider the two left-most hexagons. Either the edge between them is in a perfect matching, or not. If it is, then the other vertices in these 2 hexagons need to form up pairwise for a perfect matching. If the middle edge is not in the matching, then the perimeter must be alternately involved in the matching all around the two hexagons.

Either way, we remove those two hexagons and have a series of forced edges to include before we have to omit one of the vertices on the second top hexagon.

No perfect matching.

I was trying to translate my demonstration into the vertex-removal proof form used by user2345215, because I knew that I didn't need both sides of the graph... and here it is:

enter image description here

The left three marked vertices determine that the two LH hexes must be self-contained to make a matching, then the next four marked vertices attach to the "forced moves". The split of the graph is 7 vertices removed to leave 9 odd-vertex-count sections, including the 21-vertex section on the right.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.