Usage of the term "perfect matching" for bipartite graphs

756 Views Asked by At

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?

1

There are 1 best solutions below

8
On BEST ANSWER

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