CODEWITHSUNDEEP
mathgraphgraph-theory
jack klompus
jack klompus

Reputation: 244

Confused about Matching vs Perfect Matching?

My T.A. defined a Matching as an independent set of vertices (meaning there are no common edges between them). I'm a bit confused about that as I thought that was an independent set, while a Matching was the same thing as an independent edge set?

Additionally, I'm confused about the difference between a Matching and a Perfect Matching. According to the book Applied Combinatorics, This is the definition of a Matching with a companion Problem

According to the definition of an independent edge set, I thought it could just be {Ac, Dd} and that would constitute an independent edge set / Matching, while there a Perfect Matching does not exist.

Could someone please explain where I'm going wrong? Thanks guys!

Upvotes: 1

Views: 308

Answers (1)

WaterGenie
WaterGenie

Reputation: 139

You are correct that a matching is simply a set of independent edges. Your example of {Ac, Dd} is indeed a matching. In the prompt that you've included, the reference to "perfect matching" is far from explicit (emphasis added):

The problem is to find a feasible one-to-one matching of people to jobs, or to show that no such matching can exist.

This excerpt requires you to go through a communication barrier since they forego some pedantry for conciseness. See for instance their description of a bipartite graph:

.. graphs in which all the edges go horizontally between two sets of vertices ..

In your case, since one may not be as interested in applying (as in the name of the book) a non-perfect matching, all matching problems included may implicitly be referring to perfect matching (or at least a maximal one).

As for your T.A., if he/she didn't explicitly said "meaning there are no common edges between them", then it's most likely just a communication error. He/she may just be thinking of pairs of vertices, but the speech didn't come out right.
We can only speculate here, so I suggest simply going to him/her and talk about it. You can easily come up with a counterexample in any case (e.g., using the same graph from the excerpt, the independent set {A, a} is not a matching).

Edit
From James' comment, the question should be post/migrate to math.stackexchange.com. I don't have any rights to do those things at this moment.

Upvotes: 2

Related Questions