# Finding the perfect matching

This the following graph where I want to find the perfect matching and a maximum matching

I converted this to an bipartite graph, and found that the perfect matching exists and also found an maximum matching, but I am unable to justify that it is indeed maximum. How can you justify that a given matching is indeed maximum?

• What do you mean by "I converted this to a bipartite graph?". The graph that you showed IS bipartite. Jun 21, 2021 at 9:39
• @Steven Yeah, that was what I meant, I meant that to find it the perfect matching, I found that it is bipartite and would have a perfect matching. but now I am unable to justify that the given matching is maximum. Jun 21, 2021 at 9:43
• Can you show the matching that you found? I don't think that the graph admits a perfect matching. At least one of the 3 inner edges must be selected in any perfect matching. Then two of the edges going from a vertex that is a corner of the triangle towards the center must be selected as well. This means that there are two edges (lying on a "side" of the triangle) that cannot be selected. Since these two edges are exactly the ones incident to a vertex of the graph (the vertex at the center a the side of triangle), this vertex cannot be matched. Jun 21, 2021 at 9:50

To show that a certain matching $$M$$ is maximum in a graph $$G$$, it is necessary and sufficient to show that there is no augmenting path relative to $$M$$: a path in $$G$$ that starts and ends on free (unmatched) vertices, and alternates between edges in and not in $$M$$.
The graph admits no perfect matching. Look at the following figure and notice that any perfect matching must match vertex $$x$$. By symmetry suppose it does so with the blue edge $$(x,y)$$. Then, since $$u$$ and $$v$$ need to be matched, the matching must necessarily contain the two remaining blue edges. However, in this situation, vertex $$w$$ cannot be matched anymore. Therefore any matching has at least one unmatched vertex.
From the above discussion we know that the maximum size of a matching one can hope for is $$\left\lfloor\frac{10-1}{2}\right\rfloor = 4$$.
Here is a possible (maximum) matching of size $$4$$: