4
$\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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

These are two different concepts. A perfect matching is a matching involving all the vertices. A bipartite perfect matching (especially in the context of Hall's theorem) is a matching in a bipartite graph which involves completely one of the bipartitions. If the bipartite graph is balanced – both bipartitions have the same number of vertices – then the concepts coincide.

The term bipartite perfect matching is not standard – in fact I just made it up. Usually perfect matching just means a matching involving all the vertices.

Improve this answer
$\endgroup$
2
  • $\begingroup$ +1 for the term "bipartite perfect matching", serves the purpose of distinguishing the two concepts and also gives identity to the this particular concept, though is simple one $\endgroup$ Commented Dec 7, 2015 at 7:43
  • $\begingroup$ Just as an addendum to a sufficient answer, the comparitively more frequent term for the aforementioned 'bipartite perfect matching' is 'X-saturating matching'. $\endgroup$ Commented Apr 26, 2021 at 15:08
1
$\begingroup$

Yuval is right. A perfect matching in a bipartite graph, may be restricted and defined differently as a matching, which covers only one part of the graph. Note that according to such a definition, the number of vertices in the graph may be odd. For example, you can delete say $V_{10}$ of your example, and your matching is still perfect in the restricted sense.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.