6. For many applications of matchings, it makes sense to usebipartite graphs. You might wonder, however, whether there is a wayto find matchings in graphs in general.
- For which n does the complete graph Kn have a matching?
- Prove that if a graph has a matching, then |V||V| is even.
- Is the converse true? That is, do all graphs with |V||V| evenhave a matching?
- What if we also require the matching condition? Prove ordisprove: If a graph with an even number of vertices satisfies|N(S)|≥|S||N(S)|≥|S| for all S⊆V,S⊆V,then the graph has amatching.
Please keep straight to the point and short if possible, I givegood ratings on good legible writings and correctness. THANKS!!
