Question

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 Kn have a matching?
2. Prove that if a graph has a matching, then |V||V| is even.
3. Is the converse true? That is, do all graphs with |V||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 |N(S)|≥|S||N(S)|≥|S| for all S⊆V,S⊆V,then the graph has a matching.

Please keep straight to the point and short if possible, I give good ratings on good legible writings and correctness. THANKS!!

Answer 1

In a simple graph, a matching is a set of edges such that no two edges have a common vertex.

The terminology in the entire question is flawed: Every non-trivial graph has a matching. Any single edge is a matching. In the case of perfect matching, we can discuss the said questions.

1 & 2. For the proof of these, we note that matching is a perfect matching if all vertices are incident to a unique edge in the matching. Now, since one edge includes two vertices, it is clear that the number of vertices must be even. Otherwise, in the odd case, the even vertices will be included in the vertices of matching and one remaining vertex will be left alone. Any edge incident to that vertex must be incident to one of the vertex in the matching and thus we arrive at a contradiction. Now perfect matching will have k number of edges, and each edge is adjacent to two vertices, so the number of vertices will be 2k which are even.

3. Consider two disconnected triangles as a graph. We know a triangle doesn't have a perfect matching, so neither does the considered graph. However, the number of vertices in this graph is 6. The converse is true only for the connected graph.

4. This graph has 16 vertices but doesn't possess a perfect matching.

5. This is just Hall's matching or marriage theorem for general graphs. However, from the given condition |N(S)|≥|S| we can obtain a bipartite subgraph of the given graph, and the theorem states that we will have a perfect matching. Then, this same matching can be used for the given graph.