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?).
in-context