1
$\begingroup$

When I google for complete matching, first link points to perfect matching on wolfram.

It defines perfect matching as follows:

A perfect matching of a graph is a matching (i.e., an independent edge set) in which every vertex of the graph is incident to exactly one edge of the matching. A perfect matching is therefore a matching containing $n/2$ edges (the largest possible), meaning perfect matchings are only possible on graphs with an even number of vertices.

However below graph contains even number of vertices (10 vertices), but still I cant guess the perfect matching - in which every vertex of of the graph is incident to exactly one edge. One of the matching can be $\{E_1,E_4,E_6\}$. However not every vertex (here, $\{V_5,V_6,V_9,V_{10}\}$) is incident to exactly one edge in this matching as required by above definition. So this is not definitely a perfect matching as desired by wolfram's definition. Also I cannot add any other edge to this matching as it will make two edges to share a vertex.

Q1. Is perfect matching possible with this graph?

enter image description here

I am also reading the same topic from the book by Narsingh Deo. It defines the complete matching in the context of bipartite graph:

In a bipartite graph having a vertex partition $V_1$ and $V_2$ a complete matching of vertices in set $V_1$ into those in $V_2$ is a matching in which there is one edge incident with every vertex in $V_1$. In other words, every vertex in $V_1$ is matched against some vertex in $V_2$.

I am not able to understand if these two (wolfram's and book's) definitions point to two different concepts or they are one and same.

By my understanding, according to Deo's definition, $V_2$ may contain more vertices than that in $V_1$, thus the size matching may be less than $n/2$. However, wolfram says perfect matching contains $n/2$ edges. For example in above graph the complete matching of vertices in set $P_1$ into those in $P_2$ can be $\{E_1,E_4,E_6\}$ as one edge in this matching is incident with every vertex in $P_1$.

Q2. So the two definitions (wolfram's and book's) must be different concepts. Am I correct?

$\endgroup$
2
$\begingroup$

The graph in your first question has no perfect matching. Since there are only $3$ vertices in $P_1$, a matching using all of those vertices can use at most $3$ of the $7$ vertices of $P_2$ and therefore cannot use all of them.

The two definitions are indeed of two different things. A perfect matching exhausts all of the vertices, so a bipartite graph that has a perfect matching must have the same number of vertices in each part. Deo is defining a directional notion: a complete matching from one part into the other. If $P_1$ and $P_2$ are the parts of a bipartite graph, $P_1$ had $m$ vertices, and $P_2$ has $n$ vertices, then a complete matching of $P_1$ into $P_2$ has $m$ edges, and a complete matching of $P_2$ into $P_1$ has $n$ edges. Thus, the former is possible only if $m\le n$, the latter is possible only if $n\le m$, and a perfect matching (which is automatically a complete matching of $P_1$ into $P_2$ and a complete matching of $P_2$ into $P_1$) is possible only if $m=n$.

$\endgroup$
  • $\begingroup$ Ohh wolfram says "perfect matchings are only possible on graphs with an even number of vertices", I interpreted it incorrectly as "graphs with an even number of vertices (always) have perfect matchings", but they might not have it. Correct? $\endgroup$ – anir123 Dec 6 '15 at 14:35
  • $\begingroup$ @Mahesha999: That’s right. There are many graphs with an even number of vertices that have no perfect matching, but no graph with an odd number of vertices can have one: at least one vertex would always have to be unmatched. $\endgroup$ – Brian M. Scott Dec 6 '15 at 14:36

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.