2
$\begingroup$

A textbook written by my discrete mathematics teacher defines a "perfect matching" in a bipartite graph as a matching that covers at least one side of the graph (i.e. for $G = (V_1, V_2, E)$ with $V_1$ and $V_2$ as the two sets of vertices and $E$ as the set of edges, the number of edges in the "perfect matching" should be equal to the number of vertices in $V_1$ or $V_2$).

However, other sources (including Wikipedia) define a "perfect matching" as containing all vertices of a graph.

Do these definitions of the term conflict? If yes, which is the correct one?

$\endgroup$
3
$\begingroup$

A perfect matching has a $1$ to $1$ correspondence between both sides of the bipartite graph.

$\endgroup$
  • $\begingroup$ So, this means that both sides should have all of their vertices in the matching? $\endgroup$ – Mints97 Feb 16 '15 at 10:29
  • 1
    $\begingroup$ @Mints97: The term is usually defined as in Wikipedia, so that a bipartite graph cannot have a perfect matching unless $|V_1|=|V_2|$, but I have seen the more general definition as well, requiring that only one part be completely matched. $\endgroup$ – Brian M. Scott Feb 16 '15 at 10:40
  • $\begingroup$ @BrianM.Scott: ah, I see. So there are two different officially accepted definitions of the term? $\endgroup$ – Mints97 Feb 16 '15 at 10:41
  • $\begingroup$ @Mints97: Officially isn’t really appropriate, since there is no officiating body, but yes, there are two definitions in actual use. However, the one in Wikipedia is in my experience much more commonly used. $\endgroup$ – Brian M. Scott Feb 16 '15 at 10:44
  • 3
    $\begingroup$ @Mints97 I agree with Brian, I've seen both in use. The terminology I've seen that is the most clear is to define a bipartite matching as perfect only if $|V_1| = |V_2|$, and say there is a matching saturating $V_1$ when a matching meets all vertices of $V_1$, where $|V_1| \leq |V_2|$. $\endgroup$ – Perry Elliott-Iverson Feb 17 '15 at 17:49

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.