Investigate!

Given a bipartite graph, a matching is a subset of the edges for which every vertex belongs to exactly one of the edges. Our goal in this activity is to discover some criterion for when a bipartite graph has a matching.

Does the graph below contain a matching? If so, find one.

$A bipartite graph with 12 vertices, in two sets of six. If we call the top vertices a0 through a5, and the bottom vertices b0 to b5 (left to right), then the graph has the following edges: (a0,b0), (a0,b1), (a0,b5), (a1,b0), (a1,b3), (a2,b1), (a2,b2), (a2,b3), (a3,b0), (a3,b5), (a4,b2), (a4,b3), (a4,b4), (a4,b5), (a5,b4).$

Not all bipartite graphs have matchings. Draw as many fundamentally different examples of bipartite graphs which do NOT have matchings. Your goal is to find all the possible obstructions to a graph having a perfect matching. Write down the necessary conditions for a graph to have a matching (that is, fill in the blank: If a graph has a matching, then ). Then ask yourself whether these conditions are sufficient (is it true that if , then the graph has a matching?).