Exercise 1.

Find a matching of the bipartite graphs below or explain why no matching exists.

A bipartite graph with six vertices, in two sets of three. If we call the top vertices a,b,c, and the bottom vertices 1, 2, 3 (left to right), then the graph has the following edges: (a,1), (a,2), (b,1), (b,3), (c,1), (c,3).
A bipartite graph with eight vertices, in two sets of four. If we call the top vertices a,b,c,d and the bottom vertices 1, 2, 3,4 (left to right), then the graph has the following edges: (a,1), (a,3), (a,4) (b,2), (c,1), (c,2), (c,3), (c,4), (d,2).
A bipartite graph with ten vertices, in two sets of five. If we call the top vertices a,b,c,d,e and the bottom vertices 1, 2, 3,4,5 (left to right), then the graph has the following edges: (a,1), (a,2), (a,3), (b,1), (b,3), (c,2), (c,4), (d,3), (d,5), (e,3), (e,4), (e,5).
Solution.
in-context