A matching in a graph is a set of edges such that there is at most one edge on each vertex. For example, the red dashed edges in these two graphs each form a matching.

However, the second matching is a maximum matching since no more edges can be added. In the first graph, there is at least one more edge that can be added. Can you find a matching in the first graph with more than one more edge? Answer

We say a specific vertex is covered by the matching if one of the edges of the matching ends at that vertex. We call the matching perfect if every vertex is covered by the matching. 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. Answer

Look back at the games of Slither you have played. Do you see any ways that matchings might relate to the games? If you had a graph with a perfect matching could it help you win? What if a graph can't have a perfect matching? Answer