This is the problem I have been struggling with for a while (from Discrete Mathematics and its Applications (Rosen) seventh edition):

Suppose that a new company has five employees: Zamora, Agraharam, Smith, Chou, and Macintyre. Each employee will assume one of six responsibilities: planning, publicity, sales, marketing, development, and industry relations. Each employee is capable of doing one or more of these jobs: Zamora could do planning, sales, marketing, or industry relations; Agraharam could do planning or development; Smith could do publicity, sales, or industry relations; Chou could do planning, sales, or industry relations; and Macintyre could do planning, publicity, sales, or industry relations.

a) Model the capabilities of these employees using a bipartite graph.

b) Find an assignment such that each employee is assigned one responsibility.

c) Is the matching you found in part (b) a complete matching? Is it a maximum matching?

I have been struggling with part C for a while. Would the matching I found in part B be considered a complete matching and/or a maximum matching? Here's what I have so far (ignore part C):

I have found many different definitions but none that adequately answer my question. Thanks for you help!


A maximum matching uses the greatest number of edges possible.

The matching in (b) is maximum: in a bipartite graph with partitions $X$ and $Y$ the number of edges in a maximum matching is at most $\min(|X|,|Y|)$. Here this last expression works out to 5, and five edges are used.

A complete matching has every vertex in the graph incident to exactly one edge in the matching.

The matching in (b) is not complete because the planning job is not included in the assignment. Indeed, any graph with an odd number of vertices, like the one here with 11, has no complete matching. This term is rather old, with perfect matching being more common nowadays.

  • $\begingroup$ Crystal clear explanation. Thanks!!! $\endgroup$
    – Drew C
    Jul 15 '17 at 16:50

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.