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$

1 Answer 1

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$
3
  • $\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$
    – Mahesha999
    Dec 6, 2015 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$ Dec 6, 2015 at 14:36
  • $\begingroup$ "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" how it is relatable with Hall's marriage theorem which tell "The bipartite graph $G=(P,E)$ with bipartition $(P_1,P_2)$ has a complete matching from $P_1$ to $P_2$ if and only if $|N(A)|\geq|A|$ for all subsets $A$ of $P_1$". I know it is super late but i will appreciate if you response @BrianM.Scott Sir $\endgroup$
    – emonHR
    Oct 26, 2019 at 17:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .