1
$\begingroup$

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

enter image description here

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?

$\endgroup$
3
  • $\begingroup$ What do you mean by "I converted this to a bipartite graph?". The graph that you showed IS bipartite. $\endgroup$
    – Steven
    Jun 21, 2021 at 9:39
  • $\begingroup$ @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. $\endgroup$
    – barry
    Jun 21, 2021 at 9:43
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Jun 21, 2021 at 9:50

2 Answers 2

1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

counterexample

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$:

matching

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.