National University of Computer & Emerging Sciences

MT-3001 Graph Theory

Instructor: Miss Urooj
MATCHING AND FACTORS
In this chapter, we focus on the structure of the graph but from the viewpoint of grouping vertices
based on a variety of criteria, mainly in terms of making viable pairings.
We investigate the optimization of pairings through the use of edge-matchings within a graph, more
commonly known as a matching.
Independent Vertices & Independent Set:
Two vertices are said to be independent if they are not adjacent in G; and a set A of vertices in G is
called an independent set if every two vertices in A are independent in G.
Vertex Cover & Edge Cover:
A set Q of vertices in G is called a vertex cover of G if every edge in G is incident with a vertex in
Q.
A set W of edges in G is called an edge cover of G if every vertex in G is incident with an edge in
W.
Independent Edges & Matching Set:
Two edges are said to be independent if they are not adjacent, that is, they are not incident with a
common vertex.
A set M of edges in G is called a matching if every two edges in M are independent in G.

The most common application of matchings is the pairing of people, usually described in terms of
marriages. Other applications of graph matching are task assignment, distinct representatives, and
roommate selection.

1
Remark:
• With any matching problem, you should ask yourself what the important criterion for a solution is
and how does that translate to a matching.
• In Example 5.1, is it more important for each employee to have a task or for every task to be
completed?
We need a way to describe which vertices are the endpoints of a matched edge.

2
The matching displayed in Example 5.1 has saturated vertices (Dan, Jeff, Kate, Making Cookies,
Bottling Syrup, and Labeling Packages) representing the three tasks that will be completed by the
three employees.
• The unsaturated vertices (Making Candy, Lilah, and Tori) represent the tasks that are not assigned
or the employees without a task assignment.
Question: Is this a good matching?
Answer: No—some items needed for the order are not assigned and so the order will not be
fulfilled.
When searching for matching in a graph, we need to determine what type of matching properly
describes the solution.
Types of Matching:

Note that a perfect matching is automatically maximum and a maximum matching is automatically
maximal, though the reverse need not be true.
Example: Consider the two matchings shown in bold below of a graph 𝐺2 .

The matching on the left is maximal as no other edges in the graph can be included in the matching
since the remaining edges require the use of a saturated vertex (either a for edges ac and ae, or d for
edge bd).
The matching on the right is maximum since there is no way for a matching to contain three edges
(since then vertex a would have two matched edges incident to it).
3
In addition, the matching on the right is an X -matching if we define X = {a, b}. Finally, neither
matching is perfect since not every vertex is saturated.
Depending on the application, we are often searching for a perfect matching or an X -matching.
However, when neither of these can be found, we need a good explanation as to the size of a
maximum matching.

Remark: Above example illustrates that many matchings can have the same size. Thus, when
finding a maximum matching, it is less important which people get paired with a task than it does
that we make as many pairings possible.
MATCHING IN BIPARTITE GRAPHS:
It is often quite clear how to form a matching in a small graph. However, as the size of the graph
grows or the complexity increases, finding a maximum matching can become difficult.
Moreover, once you believe a maximum matching has been found, how can you convince someone
that a better matching does not exist?

4
Intuitive Idea: Consider the graph below with a matching shown in bold.

If you tried to adjust which edges appear in the matching to find one of larger size (try it!), you
would find it impossible.
 We can do this through the use of a neighbor set (A set of vertices S, the neighbor set N (S)
consists of all the vertices incident to at least one vertex from S).
 In graph G3 above, if we consider S = {f, i, j}, then N (S) = {d} and since at most one of the
vertices from S can be paired with d, we know the maximum matching can contain at most 3
edges.
 Since we found a matching with 3 edges, we know our matching is in fact maximum.
The Assignment Problem:
There are m applicants and n jobs, and each applicant is applying for a number of these jobs. Under
what conditions is it possible to assign each applicant to a job for which he/she is applying?
Hall's Matching Condition:
When we are filling jobs with applicants, there may be many more applicants than jobs;
successfully filling the jobs will not use all applicants.
 To model this problem, we consider an X, Y -bipartite graph, and we seek a matching that
saturates X.
 If a matching M saturates X, then for every S ⊂ X there must be at least lSI vertices that have
neighbors in S, because the vertices matched to S must be chosen from that set.
 We use N(S) to denote the set of vertices having a neighbor in S. Thus N(S) ≥ |S| is a
necessary condition. The condition, for all S ⊂ X , N(S) ≥ |S| is Hall's Condition.
 Hall proved that this obvious necessary condition is also sufficient.

This result is named for the British mathematician Philip Hall, who published the original proof in
terms of a set theory result in 1935, as well as the many iterations of the result that are often
described in terms of pairing boys and girls into marriages.

5
6
  Hall’s Marriage Theorem allows us to determine when a graph has a perfect matching or X -
matching for bipartite graphs.
 When the answer to this question is negative, we can still ask for the size of a maximum
matching.
 Hall’s Marriage Theorem does not give a definitive answer about the size of a maximum
matching but rather gives us the tools to reason why an X - matching does not exist.
 The next section uses a specific type of path and a collection of vertices as a way to
determine not only the size but also produce a maximum matching within a bipartite graph.
As an immediate consequence of Hall’s Theorem, we have:

7
8
9