Exercise 6.

For many applications of matchings, it makes sense to use bipartite graphs. You might wonder, however, whether there is a way to find matchings in graphs in general.

  1. For which \(n\) does the complete graph \(K_n\) have a matching?

  2. Prove that if a graph has a matching, then \(\card{V}\) is even.

  3. Is the converse true? That is, do all graphs with \(\card{V}\) even have a matching?

  4. What if we also require the matching condition? Prove or disprove: If a graph with an even number of vertices satisfies \(\card{N(S)} \ge \card{S}\) for all \(S \subseteq V\text{,}\) then the graph has a matching.

in-context