The following matching is a perfect matching:

What can keep a graph from having a perfect matching? Look at the graphs above and the graphs you have played Slither on.

Here are a few simple observations about when a graph can and cannot have a perfect matching:

• If a graph has a perfect matching, the number of vertices must be even.
• If there are two vertices with only one edge and those edges go to the same vertex (as in Graph B3) the graph cannot have a perfect matching.
• (Generalization of above) If a set of vertices only has edges to vertices outside the set and this second set is smaller, then there is no perfect matching.